稳健

用户名：jxfzzzt

访问量：2289

签　名：

等　　级
排　　名	534
经　　验	4445
参赛次数	6
文章发表	2
年　　龄	0
在职情况	学生
学　　校	南昌大学
专　　业

　　自我简介：

TA的其他文章

蓝桥杯2022年第十三届省赛真题-重复的数
浏览：800

你可能喜欢

蓝桥杯2022年第十三届省赛真题-重复的数

　　作者: 稳健　　　　发表时间：2022-06-19 15:56:32 浏览：800　|　评论：0　

原题链接：蓝桥杯2022年第十三届省赛真题-重复的数

### 题目描述
给定一个数列 A = (a1, a2, · · · , an)，给出若干询问，每次询问某个区间 [l, r] 内恰好出现 k次的数有多少个 ?

### 题目分析
经典离线莫队问题，cnt数组维护当前状态的每个数出现的次数，calc数组维护当前状态的每个cnt数组中的数出现的次数。

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

0.0分

5 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

稳健

TA的其他文章

你可能喜欢

C二级辅导-同因查找（C语言代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

一个简单易懂的代码

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题9.1 （C++代码）

蓝桥杯2022年第十三届省赛真题-重复的数

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

C语言训练-求函数值（C语言代码）

C语言训练-计算：t=1-1/(22)-1/(33)-...-1/(m*m) （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

三角形（C++代码）递归（存在大量重复计算，容易出现时间超限）

C语言程序设计教程（第三版）课后习题6.6 （C语言代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

DNA （C语言代码）

用筛法求之N内的素数。（C语言代码）

稳健

TA的其他文章

你可能喜欢

C二级辅导-同因查找 （C语言代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

一个简单易懂的代码

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题9.1 （C++代码）

蓝桥杯2022年第十三届省赛真题-重复的数

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

C语言训练-求函数值 （C语言代码）

C语言训练-计算：t=1-1/(2*2)-1/(3*3)-...-1/(m*m) （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

三角形 （C++代码）递归（存在大量重复计算，容易出现时间超限）

C语言程序设计教程（第三版）课后习题6.6 （C语言代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

DNA （C语言代码）

用筛法求之N内的素数。 （C语言代码）

C二级辅导-同因查找（C语言代码）

　　评论区

C语言训练-求函数值（C语言代码）

C语言训练-计算：t=1-1/(22)-1/(33)-...-1/(m*m) （C语言代码）

三角形（C++代码）递归（存在大量重复计算，容易出现时间超限）

用筛法求之N内的素数。（C语言代码）