A40887. 重复的数本题总分：25 分【问题描述】给定一个数列 A = (a1, a2, · · · , an)，给出若干询问，每次询问某个区间 [li,ri]内恰好出现 ki 次的数有多少个。【
填空题
困难
知识点
题目描述
重复的数
本题总分：25 分
【问题描述】
给定一个数列 A = (a1, a2, · · · , an)，给出若干询问，每次询问某个区间 [li,ri]
内恰好出现 ki 次的数有多少个。
【输入格式】
输入第一行包含一个整数 n 表示数列长度。
第二行包含 n 个整数 a1, a2, · · · , an，表示数列中的数。
第三行包含一个整数 m 表示询问次数。
接下来 m 行描述询问，其中第 i 行包含三个整数 li,ri, ki 表示询问 [li,ri] 区
间内有多少数出现了 ki 次。
【输出格式】
输出 m 行，分别对应每个询问的答案。
【样例输入】
3
1 2 2
5
1 1 1
1 1 2
1 2 1
1 2 2
1 3 2
【样例输出】
1
参考答案
#pragma GCC optimize(2)
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <unordered_set>
#include <stack>
#include <unordered_map>
using namespace std;
const int N = 100010, M = N * 2, MOD = 998244353, INF = 0x3f3f3f3f;
const double eps = 1e-7;
typedef long long LL;
typedef pair<LL, int> PII;
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
int t, n, m, q;
int a[N];
int cnt[1000010];
int calc[N];
int len;
inline int read() {
int s = 0, w = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')w = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
return s * w;
}
int get(int x) {
return x / len;
}
struct Query {
int id, l, r, k;
bool operator<(const Query &ver) {
int j1 = get(r), j2 = get(ver.r);
if (j1 != j2) {
return j1 < j2;
} else {
return l < ver.l;
}
}
} query[N];
int ans[N];
void add(int x) {
calc[cnt[x]] -- ;
cnt[x] ++ ;
calc[cnt[x]] ++ ;
}
void del(int x) {
calc[cnt[x]] -- ;
cnt[x] -- ;
calc[cnt[x]] ++ ;
}
int main(void) {
t = 1;
while (t--) {
n = read();
len = (int) sqrt(1.0 * n);
for (int i = 1; i <= n; i++) {
a[i] = read();
}
m = read();
for (int i = 0; i < m; i++) {
int l, r, k;
l = read(), r = read(), k = read();
query[i] = {i, l, r, k};
}
sort(query, query + m);
for (int i = 0, j = 1, z = 0; z < m; z++) {
int l = query[z].l, r = query[z].r, k = query[z].k, id = query[z].id;
while (i < r) add(a[ ++ i]);
while (i > r) del(a[i -- ]);
while (j < l) del(a[j ++ ]);
while (j > l) add(a[-- j]);
ans[id] = calc[k];
}
for (int i = 0; i < m; i++) printf("%d\n", ans[i]);
}
return 0;
}
上一题
下一题