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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53