CF220B Little Elephant and Array 题解

发表于 | 分类于

题意：
有一个长度为 $n$ 的数组和 $m$ 次询问，每次询问给出 $l$ 和 $r$，要求出 $a$ 数组下标在 $[l,r]$ 这段区间内，有多少个数 $x$ 其出现次数也为 $x$。

区间问题，自然想到莫队。

一个数的出现次数可以开个桶记录一下。

注意到 $a_i$ 可能很大，不可能记录下所有数的出现次数，所以我们只需要记录不大于 $n$ 的数。

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
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>

using namespace std;

int buc[100010], n, m, ans[100010], block_size, cnt, a[100010];

struct query {
	int id, l, r, bl;
} q[100010];

inline bool is_digit(char c) {
	return c <= '9' && c >= '0';
}

inline int read() {
	char c = getchar();
	int tmp = 0;
	while(!is_digit(c)) c = getchar();
	while(is_digit(c)) tmp = (tmp << 1) + (tmp << 3) + (c ^ 48), c = getchar();
	return tmp;
}

void write(int x) {
	if(x > 9) write(x / 10);
	putchar((x % 10) ^ 48);
}

inline bool cmp(query a, query b) {
	return a.bl != b.bl ? a.bl < b.bl : (a.bl & 1 ? a.r > b.r : a.r < b.r);
}

inline void add(int x) {
	if(a[x] > n) return ;
	if(buc[a[x]] == a[x]) cnt--;
	buc[a[x]]++;
	if(buc[a[x]] == a[x]) cnt++;
}

inline void del(int x) {
	if(a[x] > n) return ; 
	if(buc[a[x]] == a[x]) cnt--;
	buc[a[x]]--;
	if(buc[a[x]] == a[x]) cnt++;
}

int main() {
	n = read(), m = read();
	block_size = n / ((int)sqrt(m) + 1) + 1;
	for(register int i = 1; i <= n; i++) a[i] = read();
	for(register int i = 1; i <= m; i++) 
		q[i].l = read(), q[i].r = read(), q[i].id = i, q[i].bl = q[i].l / block_size;
	sort(q + 1, q + m + 1, cmp); 
	int l = q[1].l, r = l - 1;
	for(register int i = 1; i <= m; i++) {
		while(l > q[i].l) add(--l);
		while(r < q[i].r) add(++r);
		while(l < q[i].l) del(l++);
		while(r > q[i].r) del(r--);
		ans[q[i].id] = cnt;
	}
	for(register int i = 1; i <= m; i++) write(ans[i]), putchar(10);
	return 0;
}