本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P2709 【模板】莫队 / 小 B 的询问 - 洛谷【题目描述】小 B 有一个长为n nn的整数序列a aa值域为[ 1 , k ] [1,k][1,k]。他一共有m mm个询问每个询问给定一个区间[ l , r ] [l,r][l,r]求∑ i 1 k c i 2 \sum\limits_{i1}^k c_i^2i1∑kci2其中c i c_ici表示数字i ii在[ l , r ] [l,r][l,r]中的出现次数。小 B 请你帮助他回答询问。【输入】第一行三个整数n , m , k n,m,kn,m,k。第二行n nn个整数表示小 B 的序列。接下来的m mm行每行两个整数l , r l,rl,r。【输出】输出m mm行每行一个整数对应一个询问的答案。【输入样例】6 4 3 1 3 2 1 1 3 1 4 2 6 3 5 5 6【输出样例】6 9 5 2【算法标签】#提高plus #莫队【代码详解】#includebits/stdc.husingnamespacestd;// 定义长整型别名便于处理大数据#defineintlonglong// 定义数组最大容量constintN200005;// 全局变量声明intn,m,k,B;// n: 数组长度, m: 询问次数, k: 未使用参数, B: 分块大小inta[N];// 原始数组intcnt[N];// 计数器记录每个数值出现的次数intans[N];// 存储每个询问的答案intsum;// 当前区间内所有数的出现次数的平方和// 询问结构体structQ{intl,r;// 区间左右端点intid;// 询问编号}q[N];// 莫队排序比较函数奇偶性优化boolcmp(Q a,Q b){if(a.l/B!b.l/B)returna.lb.l;// 不同块按左端点升序returna.rb.r;// 同块按右端点降序奇数块优化}// 添加一个数到当前区间voidadd(intx){sum-cnt[x]*cnt[x];// 减去旧贡献cnt[x];// 增加计数sumcnt[x]*cnt[x];// 加上新贡献}// 从当前区间删除一个数voiddel(intx){sum-cnt[x]*cnt[x];// 减去旧贡献cnt[x]--;// 减少计数sumcnt[x]*cnt[x];// 加上新贡献}// 主函数入口signedmain(){// 读取数组长度、询问次数和未使用的参数kcinnmk;// 计算分块大小Bsqrt(n);// 读取原始数组for(inti1;in;i)cina[i];// 读取所有询问for(inti1;im;i){cinq[i].lq[i].r;q[i].idi;// 记录原始顺序}// 按照莫队顺序排序询问sort(q1,qm1,cmp);// 初始化当前区间为空l1, r0表示空区间for(inti1,l1,r0;im;i){// 移动指针到目标区间while(lq[i].l)// 左边界向左扩展add(a[--l]);while(rq[i].r)// 右边界向右扩展add(a[r]);while(lq[i].l)// 左边界向右收缩del(a[l]);while(rq[i].r)// 右边界向左收缩del(a[r--]);// 存储当前区间的答案ans[q[i].id]sum;}// 按原始顺序输出所有答案for(inti1;im;i)coutans[i]endl;return0;}【运行结果】6 4 3 1 3 2 1 1 3 1 4 2 6 3 5 5 6 6 9 5 2
题解：洛谷 P2709 【模板】莫队 / 小 B 的询问
发布时间：2026/6/15 20:17:00
本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P2709 【模板】莫队 / 小 B 的询问 - 洛谷【题目描述】小 B 有一个长为n nn的整数序列a aa值域为[ 1 , k ] [1,k][1,k]。他一共有m mm个询问每个询问给定一个区间[ l , r ] [l,r][l,r]求∑ i 1 k c i 2 \sum\limits_{i1}^k c_i^2i1∑kci2其中c i c_ici表示数字i ii在[ l , r ] [l,r][l,r]中的出现次数。小 B 请你帮助他回答询问。【输入】第一行三个整数n , m , k n,m,kn,m,k。第二行n nn个整数表示小 B 的序列。接下来的m mm行每行两个整数l , r l,rl,r。【输出】输出m mm行每行一个整数对应一个询问的答案。【输入样例】6 4 3 1 3 2 1 1 3 1 4 2 6 3 5 5 6【输出样例】6 9 5 2【算法标签】#提高plus #莫队【代码详解】#includebits/stdc.husingnamespacestd;// 定义长整型别名便于处理大数据#defineintlonglong// 定义数组最大容量constintN200005;// 全局变量声明intn,m,k,B;// n: 数组长度, m: 询问次数, k: 未使用参数, B: 分块大小inta[N];// 原始数组intcnt[N];// 计数器记录每个数值出现的次数intans[N];// 存储每个询问的答案intsum;// 当前区间内所有数的出现次数的平方和// 询问结构体structQ{intl,r;// 区间左右端点intid;// 询问编号}q[N];// 莫队排序比较函数奇偶性优化boolcmp(Q a,Q b){if(a.l/B!b.l/B)returna.lb.l;// 不同块按左端点升序returna.rb.r;// 同块按右端点降序奇数块优化}// 添加一个数到当前区间voidadd(intx){sum-cnt[x]*cnt[x];// 减去旧贡献cnt[x];// 增加计数sumcnt[x]*cnt[x];// 加上新贡献}// 从当前区间删除一个数voiddel(intx){sum-cnt[x]*cnt[x];// 减去旧贡献cnt[x]--;// 减少计数sumcnt[x]*cnt[x];// 加上新贡献}// 主函数入口signedmain(){// 读取数组长度、询问次数和未使用的参数kcinnmk;// 计算分块大小Bsqrt(n);// 读取原始数组for(inti1;in;i)cina[i];// 读取所有询问for(inti1;im;i){cinq[i].lq[i].r;q[i].idi;// 记录原始顺序}// 按照莫队顺序排序询问sort(q1,qm1,cmp);// 初始化当前区间为空l1, r0表示空区间for(inti1,l1,r0;im;i){// 移动指针到目标区间while(lq[i].l)// 左边界向左扩展add(a[--l]);while(rq[i].r)// 右边界向右扩展add(a[r]);while(lq[i].l)// 左边界向右收缩del(a[l]);while(rq[i].r)// 右边界向左收缩del(a[r--]);// 存储当前区间的答案ans[q[i].id]sum;}// 按原始顺序输出所有答案for(inti1;im;i)coutans[i]endl;return0;}【运行结果】6 4 3 1 3 2 1 1 3 1 4 2 6 3 5 5 6 6 9 5 2
