jimore

用户名：uq_30465888842

访问量：9728

签　名：

Don't let the dream just be a dream!!!

等　　级
排　　名	177
经　　验	6842
参赛次数	29
文章发表	63
年　　龄	0
在职情况	学生
学　　校	四川农业大学
专　　业	计算机科学与技术

　　自我简介：

目标院校：上海交通大学

TA的其他文章

二分答案（简单理解）
浏览：447

求一个很大的数的所有质因子（新方法）
浏览：246

佩尔方程——模板题
浏览：221

你可能喜欢

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

离线莫队经典问题

　　作者: jimore　　　　发表时间：2022-07-22 21:04:04 浏览：630　|　评论：0　

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

# 离线莫队经典问题

**凡是求解多个区间某一些东西的个数的时候，都可以用离线莫队解法**

什么是莫队算法大家可以参考这篇文章 [【莫队算法】 - 大米饼 - 博客园 (cnblogs.com)](https://www.cnblogs.com/Paul-Guderian/p/6933799.html)

大致思想就是将多个询问先排序，然后利用双指针的思想不断地向右移动来求每个询问区间的答案，求解完所有答案再按原循序输出

完整代码：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    const int N = 100010;
    #define B 174 //根号30000
    #define bel(x) ((x - 1) / B + 1) //求一个区间在第几个块
    using namespace std;
    struct sss
    {
        int id;
        int left,right,qus;
        friend bool operator <(struct sss x,struct sss y)//莫队排序方法
        {
            return bel(x.left)==bel(y.left)?x.right<y.right:x.left>y.left;
        }
    }q[N];
    int cnt[1000001];
    int a[N];
    int b[2*N];
    int calc[N];
    int sum=0;
    void del(int x)
    {
        calc[cnt[x]]--;
        cnt[x]--;
        calc[cnt[x]]++;
    }
    void add(int x)
    {
        calc[cnt[x]]--;
        cnt[x]++;
        calc[cnt[x]]++;
    }
    int main()
    {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        int m;
        scanf("%d",&m);
        for(int i=1;i<=m;i++)
        {
            q[i].id=i;
            scanf("%d%d%d",&q[i].left,&q[i].right,&q[i].qus);
        }
        sort(q+1,q+m+1);
        int l=1,r=0;
        for(int i=1;i<=m;i++)
        {
            while(l<q[i].left) del(a[l++]);//移动端点
            while(l>q[i].left) add(a[--l]);
            while(r<q[i].right) add(a[++r]);
            while(r>q[i].right) del(a[r--]);
            b[q[i].id]=calc[q[i].qus];
        }
        for(int i=1;i<=m;i++)
        {
            printf("%d\n",b[i]);
        }
        // system("pause");
        return 0;
    }

0.0分

3 人评分

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

jimore

TA的其他文章

你可能喜欢

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

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

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

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

C二级辅导-进制转换（C语言代码）

离线莫队经典问题

评论区

精彩推荐

简洁的代码

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

C二级辅导-统计字符（C语言代码）

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

A+B for Input-Output Practice （C++代码）

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

程序员的表白（C语言代码）

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

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

淘淘的名单（C语言代码）

jimore

TA的其他文章

你可能喜欢

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

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

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

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

C二级辅导-进制转换 （C语言代码）

离线莫队经典问题

评论区

精彩推荐

简洁的代码

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

C二级辅导-统计字符 （C语言代码）

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

A+B for Input-Output Practice （C++代码）

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

程序员的表白 （C语言代码）

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

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

淘淘的名单 （C语言代码）

C二级辅导-进制转换（C语言代码）

　　评论区

C二级辅导-统计字符（C语言代码）

程序员的表白（C语言代码）

淘淘的名单（C语言代码）