普通莫队概念
莫队：莫涛队长发明的算法，尊称莫队。其实就是优化的暴力。
普通莫队只兹磁询问不支持修改，是离线的。
莫队的基本思想：就是假定我得到了一个询问区间[l,r]的答案，那么我可以在极短（通常是O(1)）的时间复杂度内得到[l+1,r]的答案——于是对于区间查询类的题目，我可以一次性读完所有询问之后来回转移，得到每一个区间的答案。
如果可以通过区间[l,r]快速转移到[l-1,r][l+1,r][l,r-1][l,r+1],那么可以用O(x*|l1-l2|+|r1-r2|)的时间完成转移,[l2,r2]是[l1,r1]的后一次询问,x是[l,r]转到相邻区间的复杂度，我们让这个值最小，就是求曼哈顿距离最小生成树，但是这个比较难求。可以用分块加上一定规则来排序，以左端点所在块的编号为第一关键字排序，右端点的值作为第二关键字排序，最坏复杂度和上面的曼哈顿距离最小生成树是一样的，这个样子做的复杂度是 $O(n \sqrt n) $（不会证，反正使用分块后复杂度就是这）。
在这里，分块的作用就是加速而已。
题目
小B有一个序列，包含N个1~K之间的整数。他一共有M个询问，每个询问给定一个区间[L..R]，求Sigma(c(i)^2)的值,其中i的值从1到K，其中c(i)表示数字i在[L..R]中的重复次数
分析：
无修改莫队模板题，用一个数组记录当前区间每种数字出现的次数，在莫队转移是进行维护。
先读入所有的查询并排序，然后完成指针跳转得到每次查询的结果，最后根据查询顺序排序并输出结果。
对查询排序有两种方法：
- 左端点所在块的编号为第一关键字排序，右端点的值作为第二关键字排序
- 左端点所在块的编号为第一关键字排序，块号相同时，如果块序号为奇就升序排r，否则降序
#include<bits/stdc++.h>
using namespace std; typedef long long ll;
const int maxn = + ;
struct Que{
int l, r, id; //id表示是第几次询问
ll res; //当前询问的答案
}q[maxn]; int n, m, k;
ll block[maxn], num[maxn], sum[maxn], size;
ll ans;
//block: 分块数组 size分块大小
//sum[i]: 元素i的个数 void init()
{
size = (int)sqrt(n);
for(int i = ;i <= n;i++) block[i] = (i-) / size + ;
} //莫队精髓一
bool cmp(Que x, Que y)
{
return block[x.l] == block[y.l] ? x.r < y.r : x.l < y.l;
} bool cmpp(Que x, Que y)//第二种排序方式，快一些
{
return (block[x.l] ^ block[y.l]) ? block[x.l] < block[y.l] : ((block[x.l] & ) ? x.r < y.r : x.r > y.r);
} //按查询顺序排序，用于输出答案
bool cmp_id(Que x, Que y)
{
return x.id < y.id;
} //莫队精髓二：转移
void modify(int x, int w)
{
ans -= sum[num[x]] * sum[num[x]]; ///先将这个位置数的原来sum的平方减去
sum[num[x]] += w; //更新个数统计数组
ans += sum[num[x]] * sum[num[x]]; //然后加上新的sum
} void solve()
{
int l = , r = ; //莫队精髓三：两个小指针来回跳，表示当前ans维护的区间的左右端点
for(int i = ;i <= m;i++)
{
while(r < q[i].r) modify(r+, ), r++;
while(r > q[i].r) modify(r, -), r--;
while(l < q[i].l) modify(l, -), l++;
while(l > q[i].l) modify(l-, ), l--;
q[i].res = ans;
}
} int main()
{
scanf("%d%d%d", &n, &m, &k);
for(int i = ;i <= n;i++) scanf("%lld", &num[i]);
for(int i = ;i <= m;i++)
{
scanf("%d%d", &q[i].l, &q[i].r);
q[i].id = i;
} init();
sort(q+, q+m+, cmp); //or cmpp solve(); sort(q+, q+m+, cmp_id);
for(int i = ;i <= m;i++)
printf("%lld\n", q[i].res); return ;
}
参考链接：