meepo's Blog

Description

Input

Output

Sample Input

Sample Output

HINT

Source

    这道题特殊的地方就在询问中对数的大小还有限制。。所以我们还要在莫队中套一个维护区间的数据结构。。线段树和树状数组就很不错。。然而因为这道题的数据是加强过的。。我的\(m*\sqrt n*log(n)\)96S才过。。真是惊心动魄。。。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int M = 1000010;
const int N = 100010;
struct data{int l,r,a,b,ans1,ans2,id;} q[M];
int s[N],t1[N],t2[N],pos[N],c[N],n,m,l,r,blk;
int read(){
	int x = 0,f = 1,c = getchar();
	while (c<'0' || c>'9') {if (c=='-') f = -1;c = getchar();}
	while (c>='0' && c<='9') x = x*10+c-'0',c = getchar();
	return x*f;
}
bool cmpid(data a,data b){return a.id<b.id;}
bool cmp(data a,data b){if (pos[a.l]==pos[b.l]) return a.r<b.r;return pos[a.l]<pos[b.l];}
void Add1(int x,int val){for (int i=x;i<=n;i+=i&-i) t1[i]+=val;}
void Add2(int x,int val){for (int i=x;i<=n;i+=i&-i) t2[i]+=val;}
int Query1(int x){
	if (x==0) return 0;
	int res = 0;
	for (int i=x;i;i-=i&-i) res+=t1[i];
	return res;
}
int Query2(int x){
	if (x==0) return 0;
	int res = 0;
	for (int i=x;i;i-=i&-i) res+=t2[i];
	return res;
}
void Update(int p,int val){
	if (val==1){
		s[c[p]]++;
		if (s[c[p]]==1) Add2(c[p],1);
		Add1(c[p],1);
	}
	else {
		s[c[p]]--;
		if (!s[c[p]]) Add2(c[p],-1);
		Add1(c[p],-1);
	}
}
void solve(){
	l = 1,r = 0;
	for (int i=1;i<=m;i++){
		while (r<q[i].r) Update(r+1,1),r++;
		while (r>q[i].r) Update(r,-1),r--;
		while (l<q[i].l) Update(l,-1),l++;
		while (l>q[i].l) Update(l-1,1),l--;
		q[i].ans1 = Query1(q[i].b)-Query1(q[i].a-1);
		q[i].ans2 = Query2(q[i].b)-Query2(q[i].a-1);
	}
}
int main(){
	n = read();m = read();
	blk = (int)sqrt(n);
	for (int i=1;i<=n;i++) pos[i] = (i-1)/blk+1;
	for (int i=1;i<=n;i++) c[i] = read();
	for (int i=1;i<=m;i++){
		q[i].l = read();q[i].r = read();
		q[i].a = read();q[i].b = read();
		q[i].id = i;
	}
	sort(q+1,q+1+m,cmp);
	solve();
	sort(q+1,q+1+m,cmpid);
	for (int i=1;i<=m;i++) printf("%d %d\n",q[i].ans1,q[i].ans2);
}