评测记录

莫队套分块做法，块长均为n/sqrt(m)，试过一些其他块长，也试过莫队分块的块长不同，但是发现这样相对最快，第8个点时限1s，T了，第9个点时限3s，我200ms跑完，88分求调。

#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
inline int rd(){
	char c=getchar();int sum=0,f=1;
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c<='9'&&c>='0'){sum=(sum<<3)+(sum<<1)+(c^48);c=getchar();}
	return sum*f;
}
int sum[N],sump[N],sumr[N];
int n,m,a[N],len,ans[N],res[N],bl[N];
struct node{
	int l,r,a,b,id;
	bool operator<(const node& x)const{
		if(bl[l]==bl[x.l])
			if(bl[l]&1)return r<x.r;
			else return r>x.r;
		else return bl[l]<bl[x.l];
	}
}ask[N];
//sump[i]存数字i的出现次数 
//sum[i]存第i块中的数码个数
//sumr[i]存第i块中的数的个数 
void del(int x){
	x=a[x];
	--sump[x];--sumr[bl[x]];
	if(sump[x]<=0)--sum[bl[x]];
}
void add(int x){
	x=a[x];
	++sump[x];++sumr[bl[x]];
	if(sump[x]<=1)++sum[bl[x]];
}
int get_res(int l,int r){
	if(l>r)return 0;
	int ans=0;
	if(bl[l]==bl[r]){
		for(int i=l;i<=r;++i)ans+=(bool)sump[i];
		return ans;
	}
	for(int i=l;bl[i]==bl[l];++i)ans+=(bool)sump[i];
	for(int i=r;bl[i]==bl[r];--i)ans+=(bool)sump[i];
	for(int i=bl[l]+1;i<=bl[r]-1;++i)ans+=sum[i];
	return ans;
}
int get_ans(int l,int r){
	if(l>r)return 0;
	int ans=0;
	if(bl[l]==bl[r]){
		for(int i=l;i<=r;++i)ans+=sump[i];
		return ans;
	}
	for(int i=l;bl[i]==bl[l];++i)ans+=sump[i];
	for(int i=r;bl[i]==bl[r];--i)ans+=sump[i];
	for(int i=bl[l]+1;i<=bl[r]-1;++i)ans+=sumr[i];
	return ans;
}
signed main(){
	int l=1,r=0;
	n=rd();m=rd();len=1.0*n/pow(m,0.5)+1;
	for(int i=1;i<=N;++i)bl[i]=(i-1)/len+1;
	for(int i=1;i<=n;++i)a[i]=rd();
	for(int i=1;i<=m;++i){
		ask[i].l=rd();ask[i].r=rd();
		ask[i].a=rd();ask[i].b=rd();
		ask[i].id=i;
	}
	sort(ask+1,ask+1+n);
	for(int i=1;i<=m;++i){
		while(l<ask[i].l)del(l++);
		while(l>ask[i].l)add(--l);
		while(r>ask[i].r)del(r--);
		while(r<ask[i].r)add(++r);
		ans[ask[i].id]=get_ans(ask[i].a,ask[i].b);
		res[ask[i].id]=get_res(ask[i].a,ask[i].b);
	}
	for(int i=1;i<=m;++i)
		printf("%d %d\n",ans[i],res[i]);
	return 0;
}