Codeforces 220B

传送门

题目大意

给出一个长度为$n$的序列，进行$m$次询问。

每次询问区间$[l,r]$内，有多少个数字$x$刚好出现了$x$次。

思路

枚举右端点$r$，维护左端点$l$，设法将$sum(l,r)$ 表示为区间内的合法数字个数

所以以区间$[2,2,2,2]$为例：

1. $r=1$,左端点的贡献分别为:$[0,0,0,0]$;
2. $r=2$,左端点的贡献分别为:$[1,0,0,0]$;
3. $r=3$,左端点的贡献分别为:$[-1,1,0,0]$;
4. $r=4$,左端点的贡献分别为:$[0,-1,1,0]$;

所以可以看出规律，只需要维护上述规律即可将贡献维护成前缀和。

代码

typedef pair<ll, ll>PLL;
typedef pair<int, int>PII;
int a[maxn],n,m,ans[maxn],tr[maxn];
vector<PII>q[maxn];
vector<int>g[maxn];int lowbit(int x){return x&-x;
}
void update(int pos,int val){while(pos<=n){tr[pos]+=val;pos+=lowbit(pos);}
}
int query(int pos){int res=0;while(pos){res+=tr[pos];pos-=lowbit(pos);}return res;
}int main(){cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=m;i++){int l,r;cin>>l>>r;q[r].push_back({l,i});}for(int i=1;i<=n;i++){int x=a[i];if(x<=n){g[x].push_back(i);int siz=g[x].size();if(siz>=x){update(g[x][siz-x],1);if(siz-x-1>=0) update(g[x][siz-x-1],-2);if(siz-x-2>=0) update(g[x][siz-x-2],1);}}for(int j=0;j<q[i].size();j++){PII t=q[i][j];int l=t.first,id=t.second;ans[id]=query(i)-query(l-1);}}for(int i=1;i<=m;i++) printf("%d\n",ans[i]);return 0;
}