题解：洛谷 P2709 【模板】莫队 / 小 B 的询问
本文分享的必刷题目是从蓝桥云课、洛谷、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_{i=1}^k c_i^2i=1∑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 #莫队
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;// 定义长整型别名，便于处理大数据#defineintlonglong// 定义数组最大容量constintN=200005;// 全局变量声明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.l<b.l;// 不同块按左端点升序returna.r>b.r;// 同块按右端点降序（奇数块优化）}// 添加一个数到当前区间voidadd(intx){sum-=cnt[x]*cnt[x];// 减去旧贡献cnt[x]++;// 增加计数sum+=cnt[x]*cnt[x];// 加上新贡献}// 从当前区间删除一个数voiddel(intx){sum-=cnt[x]*cnt[x];// 减去旧贡献cnt[x]--;// 减少计数sum+=cnt[x]*cnt[x];// 加上新贡献}// 主函数入口signedmain(){// 读取数组长度、询问次数和未使用的参数kcin>>n>>m>>k;// 计算分块大小B=sqrt(n);// 读取原始数组for(inti=1;i<=n;i++)cin>>a[i];// 读取所有询问for(inti=1;i<=m;i++){cin>>q[i].l>>q[i].r;q[i].id=i;// 记录原始顺序}// 按照莫队顺序排序询问sort(q+1,q+m+1,cmp);// 初始化当前区间为空，l=1, r=0表示空区间for(inti=1,l=1,r=0;i<=m;i++){// 移动指针到目标区间while(l>q[i].l)// 左边界向左扩展add(a[--l]);while(r<q[i].r)// 右边界向右扩展add(a[++r]);while(l<q[i].l)// 左边界向右收缩del(a[l++]);while(r>q[i].r)// 右边界向左收缩del(a[r--]);// 存储当前区间的答案ans[q[i].id]=sum;}// 按原始顺序输出所有答案for(inti=1;i<=m;i++)cout<<ans[i]<<endl;return0;}【运行结果】
6 4 3 1 3 2 1 1 3 1 4 2 6 3 5 5 6 6 9 5 2