第十三届蓝桥杯 C++ C 组省赛 J 题——重复的数 （AC）

1.重复的数

1.题目描述

给定一个数列 $A=\left(a_1,a_2,\cdots ,a_n\right)$, 给出若干询问, 每次询问某个区间 $\left[l_i,r_i\right]$ 内恰好出现 $k_i$次的数有多少个。

2.输入格式

输入第一行包含一个整数 $n$ 表示数列长度。

第二行包含 $n$ 个整数 $a_1,a_2,\cdots ,a_n$ , 表示数列中的数。

第三行包含一个整数 $m$ 表示询问次数。

接下来 $m$ 行描述询问, 其中第 $i$ 行包含三个整数 $l_i,r_i,k_i$表示询问 $\left[l_i,r_i\right]$ 区 间内有多少数出现了 $k_i$次。

3.输出格式

输出 $m$ 行, 分别对应每个询问的答案。

4.样例输入

3
1 2 2
5
1 1 1
1 1 2
1 2 1
1 2 2
1 3 2

5.样例输出

1
0
2
0
1

6.数据范围

$1\le n,m\le 100000,1\le a1,a2,\cdots ,an\le 100000,1\le li\le r_i\le n,1\le k_i\le n_{\text{。 }}$。

2.解题思路

莫队的模板题，学过的能一眼看出来，没学过下面链接跳转学习一下：
莫队

3.Ac_code

#include
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> PII;
#define pb(s) push_back(s);
#define SZ(s) ((int)s.size());
#define ms(s,x) memset(s, x, sizeof(s))
#define all(s) s.begin(),s.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const int N = 200010;

// 莫队
int n, q, c[N], cnt[N], freq[N], ans[N];
int sq;
struct query
{
	int l, r, k, id;
	bool operator<(const query &o) const
	{
		if (l / sq != o.l / sq)
			return l < o.l;
		if (l / sq & 1)
			return r < o.r;
		return r > o.r;
	}
} que[N];
void add(int x) {
	cnt[freq[c[x]]]--;
	freq[c[x]]++;
	cnt[freq[c[x]]]++;
};
void del (int x) {
	cnt[freq[c[x]]]--;
	freq[c[x]]--;
	cnt[freq[c[x]]]++;
};
void solve()
{
	cin >> n;
	sq = sqrt(n);
	for (int i = 1; i <= n; ++i) {
		cin >> c[i];
	}
	cin >> q;
	for (int i = 0; i < q; ++i) {
		int l, r, k;
		cin >> l >> r >> k;
		que[i] = {l, r, k, i};
	}
	int B = 500;
	sort(que, que + q);
	int l = 1, r = 0;
	for (int i = 0; i < q; ++i) {
		while (r < que[i].r) r++, add(r);
		while (l > que[i].l) l--, add(l);
		while (r > que[i].r) del(r), r--;
		while (l < que[i].l) del(l), l++;
		ans[que[i].id] = cnt[que[i].k];
	}
	for (int i = 0; i < q; ++i) {
		cout << ans[i] << '\n';
	}
}
int main()
{
	ios_base :: sync_with_stdio(false);
	cin.tie(nullptr);
	int t = 1;
	while (t--)
	{
		solve();
	}
	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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

​