离线莫队算法

预处理出每个位置i 前一个和这个颜色相同的位置pre[i]和下一个颜色相同的位置nxt[i]

莫队转移的时候看一下区间里面还有没有这个颜色就可以转移了

最后统计的时候我用了一个分块- -其实不用也可以的，或者用了分块可以不用预处理上面的东西，分块记录和然后颜色减到0的时候该块的和减1就可以了

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=50010;
struct ask{int l,r,id;}q[200010];
int pre[N],nxt[N],n,c[N],tmp[1000010],sqrn,sqrc=1010,bit[2000],ans[200010],l,r,m,mx;
bool cmp(ask a,ask b){return a.l/sqrn==b.l/sqrn?a.r<b.r:a.l/sqrn<b.l/sqrn;}
void read(int &x){
	char c;
	while((c=getchar())<'0' || c>'9');x=c-'0';
	while((c=getchar())>='0' && c<='9') x=x*10+c-'0';
}
int main(){
	//freopen("1878.in","r",stdin);freopen("1878.out","w",stdout);
	read(n);sqrn=(int)sqrt(n);
	for(int i=1;i<=n;i++) read(c[i]),mx=max(c[i]+10,mx);sqrc=(int)sqrt(mx);
	read(m);
	for(int i=1;i<=m;i++) read(q[i].l),read(q[i].r),q[i].id=i;
	for(int i=1;i<=n;i++) pre[i]=tmp[c[i]],tmp[c[i]]=i;
	for(int i=0;i<=1000000;i++) tmp[i]=50010;
	for(int i=n;i>=1;i--) nxt[i]=tmp[c[i]],tmp[c[i]]=i;//预处理pre和nxt
	sort(q+1,q+m+1,cmp);l=r=1;bit[c[1]/sqrc]=1;
	for(int i=1;i<=m;i++){
		int ret=0;
		for(;l<q[i].l;l++) if(nxt[l]>r) bit[c[l]/sqrc]--;
		for(;l>q[i].l;l--) if(nxt[l-1]>r) bit[c[l-1]/sqrc]++;
		for(;r<q[i].r;r++) if(pre[r+1]<l) bit[c[r+1]/sqrc]++;
		for(;r>q[i].r;r--) if(pre[r]<l) bit[c[r]/sqrc]--;
		for(int j=0;j<sqrc+10;j++) ret+=bit[j];
		ans[q[i].id]=ret;
	}
	for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
	return 0;
}