莫队算法是一种利用分块思想，来解决离线区间询问问题的算法。
Part 1 普通莫队
莫队的基本思想是利用上一个询问的信息，通过移动区间头尾指针，暴力转移到下一个询问区间。
先举个例子：
给出一个长度为 \(n\) 的序列，序列中所有数字均不超过一个给定的数字 \(k\)，现在给出 \(m\) 次询问，每次询问区间 \([l,r]\) 中所有数字出现次数的平方和。
数据范围：\(n,m,k \leq 50000\)
最暴力的方法当然是对每个询问分别暴力扫描计算，复杂度是 \(O(nm)\) 的。
我们注意到我们可以利用上一次询问区间的信息来进行优化。具体地说，对于一个状态 \([l,r]\)，我们可以通过移动区间首尾指针的方式，转移到 \([l-1,r],[l+1,r],[l,r-1],[l,r+1]\) 这样几个区间。
于是我们有了一个优化的算法：从第一个询问区间开始，每次通过暴力移动区间首尾指针的方式来更新信息，并转移到下一个询问区间。
我们可能有很多指针移动操作，所以这样还是很慢。
如果题目并不要求强制在线，我们可以将所有询问一次性读入，并通过排序的方法来使得指针的移动次数最少。
怎么排序呢？如果直接按照 \(l\) 为第一关键字，\(r\) 为第二关键字排序，虽然左端点指针移动次数少了，但右端点可能会产生大量移动。
我们来考虑分块的思想：具体来说，我们将区间分成若干块，先按照左端点所在块的编号进行排序，如果有若干区间左端点处在同一块中，则按右端点所在块的编号排序。
如果块大小取 \(\sqrt n\)，可以证明这样算法的复杂度是 \(n \sqrt n\) 的。
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
struct query
{
int l,r,bl,br,id;
}q[50005];
long long a[50005],ans[50005],t[50005],res;
bool cmp(const query&a,const query&b)
{
return a.bl<b.bl||(a.bl==b.bl&&a.br<b.br);
}
void del(int x)
{
res-=2*t[a[x]]-1;
t[a[x]]--;
}
void add(int x)
{
res+=2*t[a[x]]+1;
t[a[x]]++;
}
int main()
{
int n,m,k;
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
cin>>a[i];
int siz=sqrt(n);
for(int i=1;i<=m;i++)
{
cin>>q[i].l>>q[i].r;
q[i].bl=(q[i].l-1)/siz+1;
q[i].br=(q[i].r-1)/siz+1;
q[i].id=i;
}
sort(q+1,q+m+1,cmp);
int l=1,r=0;
for(int i=1;i<=m;i++)
{
int ql=q[i].l,qr=q[i].r;
while(l<ql)
{
del(l);
l++;
}
while(l>ql)
{
l--;
add(l);
}
while(r<qr)
{
r++;
add(r);
}
while(r>qr)
{
del(r);
r--;
}
ans[q[i].id]=res;
}
for(int i=1;i<=m;i++)
cout<<ans[i]<<endl;
return 0;
}
Part 2 带修莫队
之前的题目没有修改操作，如果加上了修改操作，又该如何处理呢？
方法还是很暴力：我们给原来的状态加上一维时间戳，将状态改为 \([l,r,t]\) 的形式。排序和转移的时候考虑一下时间就可以了。
（To be continued…）