CodeForces
题意：N个数，M个查询，求[Li,Ri]区间内出现次数等于其数值大小的数的个数。
分析：用莫队处理离线问题是一种解决方案。但ai的范围可达到1e9，所以需要离散化预处理。每次区间向外扩的更新的过程中，检查该位置的数ai的出现次数是否已经达到ai或ai+1，以判断是否要更新结果。同理，区间收缩的时候判断ai出现次数是否达到ai或ai-1。
另一种更高效的方法是使用树状数组离线处理查询。用一个vector数组维护每个ai以此出现的位置。显然ai>N的数不会对结果做出贡献，所以数组开1e5就足够了。树状数组的维护操作：从1道N递推，当ai的出现次数sz>=ai后，对其从右往左数的第ai次出现的位置+1；当出现次数sz>ai次后，需要对从右往左数第ai+1的位置减2；但是出现次数sz>ai+1次后，上述操作会多减去一部分，那么相应的就应该在从右往左数第ai+2次出现的位置上+1。
莫队代码：
#include<iostream> #include<stdio.h> #include<algorithm> #include<cstring> #include<cmath> #include<map> using namespace std; const int maxn=1e5+5; typedef long long LL; int N,M,res; struct Node{ int val; int id; bool operator < (const Node &p) const {return val<p.val;} }a[maxn]; bool cmpid(const Node &x,const Node &y) {return x.id<y.id;} int b[maxn]; int pos[maxn],cnt[maxn],block; //块数 int ans[maxn]; int v[maxn]; //离散化 struct Query{ int L,R,id; }Q[maxn]; bool cmp1(const Query& x,const Query& y){ //根据所属块的大小排序 if(pos[x.L]==pos[y.L]) return x.R<y.R; return pos[x.L]<pos[y.L]; } void add(int pos) { int id = v[a[pos].id]; if(cnt[id]==b[pos]-1) res++; else if(cnt[id]==b[pos]) res--; cnt[id]++; } void pop(int pos) { int id = v[a[pos].id]; if(cnt[id]==b[pos]) res--; else if(cnt[id]==b[pos]+1) res++; cnt[id]--; } //#define LOCAL int main() { #ifdef LOCAL freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif int T; int cas=1; while(scanf("%d%d",&N,&M)==2){ block = ceil(sqrt(1.0*N)); memset(cnt,0,sizeof(cnt)); for(int i=1;i<=N;++i){ scanf("%d",&a[i].val); a[i].id = i; b[i] = a[i].val; pos[i]=i/block; } //离散化 sort(a+1,a+N+1); int tag = 1; v[a[1].id] = tag; for(int i=2;i<=N;++i){ if(a[i].val == a[i-1].val) v[a[i].id] = tag; else v[a[i].id] = ++tag; } sort(a+1,a+N+1,cmpid); for(int i=1;i<=M;++i){ scanf("%d%d",&Q[i].L,&Q[i].R); Q[i].id = i; } sort(Q+1,Q+M+1,cmp1); res=0; int curL=1,curR=0; for(int i=1;i<=M;++i){ while(curL>Q[i].L) add(--curL); while(curR<Q[i].R) add(++curR); while(curL<Q[i].L) pop(curL++); while(curR>Q[i].R) pop(curR--); ans[Q[i].id] = res; } for(int i=1;i<=M;++i) printf("%d ",ans[i]); } return 0; }
离线树状数组代码：
#include<iostream> #include<stdio.h> #include<algorithm> #include<cstring> #include<cmath> #include<map> #include<vector> using namespace std; const int maxn=1e5+5; typedef long long LL; int N,M; int a[maxn]; int ans[maxn]; struct Query{ int L,R,id; bool operator < (const Query &q) const {return R<q.R;} }Q[maxn]; int bit[maxn]; inline int lowbit(int x) {return x&(-x);} void add(int i,int val){ for(;i<=N;i+=lowbit(i)) bit[i]+=val; } int sum(int i){ int res=0; for(;i>0;i-=lowbit(i)) res+=bit[i]; return res; } #define LOCAL int main() { #ifdef LOCAL freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif int T; int cas=1; while(scanf("%d%d",&N,&M)==2){ vector<int> pos[maxn]; memset(bit,0,sizeof(bit)); for(int i=1;i<=N;++i){ scanf("%d",&a[i]); } for(int i=1;i<=M;++i){ scanf("%d%d",&Q[i].L,&Q[i].R); Q[i].id = i; } sort(Q+1,Q+M+1); int la=1; for(int i=1;i<=N;++i){ if(a[i]<=N){ //如果a[i]>N 那么不可能对结果有贡献 pos[a[i]].push_back(i); //记录出现的位置 int sz = pos[a[i]].size(); if(sz>=a[i]){ add(pos[a[i]][sz-a[i]],1); //对从右往左数的第a[i]次出现的位置，加1 //若a[i]出现的次数大于a[i]，从右往左数出现的第a[i]+1次的位置已经被加1，不能作出贡献的前缀被多加了2，所以减去2 if(sz>a[i]) add(pos[a[i]][sz-a[i]-1],-2); //但是若a[i]出现的次数大于a[i]+1,那么之前的-2操作就需要“补偿回来” if(sz>a[i]+1) add(pos[a[i]][sz-a[i]-2],1); } } while(la<=M && Q[la].R==i){ ans[Q[la].id] = sum(Q[la].R) - sum(Q[la].L-1); la++; } if(la>M) break; } for(int i=1;i<=M;++i) printf("%d ",ans[i]); } return 0; }