按询问区间右端点排序，从左往右扫，维护所有后缀的答案。
如果扫到 \(a[i]\)，那么让统计个数的 \(cnt[a[i]]++\).
如果\(cnt[a[i]]<a[i]\)，那么在当前的右端点固定的情况下这个\(a[i]\)不会有任何的贡献。
如果\(cnt[a[i]]=a[i]\)，那么可以让\([1,pre[i]]\)区间加\(1\)，其中\(pre[i]\)代表从\(i\)向前第\(a[i]\)个\(a[i]\)出现的位置。
如果\(cnt[a[i]]>a[i]\)，那么需要让\((pos[pos[pre[i]]],pos[pre[i]]]\)区间减\(1\)，其中\(pos[i]\)代表从\(i\)向前第\(1\)个\(a[i]\)出现的位置，同时还需要让\((pos[pre[i]],pre[i]]\)区间加\(1\)。
这个放上线段树区间修改单点查询就好了。
推上主席树。
还要区间修改。
pushdown空间巨大？
标记永久化。
Code #include<set> #include<map> #include<cmath> #include<queue> #include<cctype> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using std::min; using std::max; using std::swap; using std::vector; const int N=1e5+5; typedef double db; const int maxn=1e5; typedef long long ll; #define pb(A) push_back(A) #define pii std::pair<int,int> #define all(A) A.begin(),A.end() #define mp(A,B) std::make_pair(A,B) vector<int> v[N]; int n,q,a[N],sum[N*30],cov[N*30]; int root[N],ch[N*30][2],cnts[N],tot; int getint(){ int X=0,w=0;char ch=0; while(!isdigit(ch))w|=ch=='-',ch=getchar(); while( isdigit(ch))X=X*10+ch-48,ch=getchar(); if(w) return -X;return X; } int modify(int pre,int l,int r,int ql,int qr,int c){ int cur=++tot; ch[cur][0]=ch[pre][0];ch[cur][1]=ch[pre][1]; sum[cur]=sum[pre]+c*(qr-ql+1);cov[cur]=cov[pre]; if(ql<=l and r<=qr){ cov[cur]+=c; return cur; } int mid=l+r>>1; if(qr<=mid) ch[cur][0]=modify(ch[pre][0],l,mid,ql,qr,c); else if(ql>mid) ch[cur][1]=modify(ch[pre][1],mid+1,r,ql,qr,c); else{ ch[cur][0]=modify(ch[pre][0],l,mid,ql,mid,c); ch[cur][1]=modify(ch[pre][1],mid+1,r,mid+1,qr,c); } return cur; } int query(int cur,int l,int r,int ql,int qr,int add){ if(ql<=l and r<=qr) return sum[cur]+add*(r-l+1); int mid=l+r>>1; if(qr<=mid) return query(ch[cur][0],l,mid,ql,qr,add+cov[cur]); else if(ql>mid) return query(ch[cur][1],mid+1,r,ql,qr,add+cov[cur]); else return query(ch[cur][0],l,mid,ql,mid,add+cov[cur])+query(ch[cur][1],mid+1,r,mid+1,qr,add+cov[cur]); } signed main(){ n=getint(),q=getint(); for(int i=1;i<=n;i++) v[i].pb(0); for(int i=1;i<=n;i++){ a[i]=getint(); root[i]=root[i-1]; if(a[i]>n) continue; cnts[a[i]]++; v[a[i]].pb(i); if(cnts[a[i]]==a[i]) root[i]=modify(root[i],1,n,1,v[a[i]][1],1); else if(cnts[a[i]]>a[i]){ int sze=v[a[i]].size(); root[i]=modify(root[i],1,n,v[a[i]][sze-a[i]-2]+1,v[a[i]][sze-a[i]-1],-1); root[i]=modify(root[i],1,n,v[a[i]][sze-a[i]-1]+1,v[a[i]][sze-a[i]],1); } } int lasans=0; while(q--){ int x=getint()^lasans,y=getint()^lasans; printf("%d\n",lasans=query(root[y],1,n,x,x,0)); } return 0; }