【数据结构】莫队
感觉莫队没什么新手入门的教程，就写一下。
\texttt{Par1:} 莫队
- 这个东西听说在被正式发明前，已经在
CF 上被当成trick 使用了，但最后是由莫涛整理并发明的
莫队算法处理的问题，一般都可以化为如下形式：
给定一个有
n 个数序列a 和q 个询问。对于每个询问，给定区间
[l,r] ，求区间内所有数的贡献和。
典例：P2709 小B的询问
该题中，对于
a_i ，其贡献即(sum_{a_i}+1)^{2}-sum_{a_i}^{2}=2*sum_{a_i}+1 ，其中，sum_{a_i} 表示计算a_i 的贡献前，统计到的，区间内值为a_i 的数的数量。
对于这类问题，我们自然可以对于每个询问，暴力枚举区间内的每个数，计算贡献。
对于一个数，计算其贡献的复杂度是
显然它不够优秀，于是我们考虑对其优化。
但是，我们注意到对于单独的一个询问，我们无法以低于
于是，我们只能在询问之间进行优化。
考虑对于一个询问
对于左端点：
对于右端点：
于是，我们发现可以记录当前所在的区间
对于左端点，我们借鉴分块的思路，取块长
发现共有
发现此时满足
默认
时，
移动左右端点示例：
for (int i = 1; i <= m; i ++ )
{
while (l > q[i].l) add ( -- l);
while (r < q[i].r) add ( ++ r);
while (l < q[i].l) del (l ++ );
while (r > q[i].r) del (r -- );
// 统计「答案」或「答案的变化量」
}有关 l 和 r 初始值的分析
首先，初始的 0 0 。
但是，以 0 0 作为 q[1].l 和 q[1].r 。
-
执行
while (l > q[i].l) add ( -- l);，由于l 为0 ，不大于l_1 ，因此该语句不会被执行。 -
执行
while (r < q[i].r) add ( ++ r);，由于r 为0 ，必定小于r_1 ，因此该语句会被执行，[1,r_1] 的贡献被计算，r 变为r_1 。 -
执行
while (l < q[i].l) del (l ++ );，由于l 为0 ，必定小于l_1 ，因此该语句会被执行，[0,l_1-1] 的贡献被除掉，l 变为l_1 。 -
执行
while (r > q[i].r) del (r -- );，由于r 为r_1 ，不大于r_1 ，因此该语句不会被执行。
注意到此时，我们多排除了
因此，我们一般会将
奇偶性排序优化莫队
注意到我们从块
考虑对于所有编号为奇数的块，按
实际题目中将会对常数产生较大优化，建议使用。
具体实现：将原先代码中的重载运算符代码
bool operator< (const Qst& t) const
{
if (b == t.b) return r < t.r;
return b < t.b;
}改为
bool operator< (const Qst& t) const
{
if (b == t.b) return (b & 1) ? (r < t.r) : (r > t.r);
return b < t.b;
}即可，其中 Qst 为询问的结构体名称，b 为询问所属块的编号。
模版代码
以 P2709 小B的询问 为例。其中因为具体贡献更新并非莫队的模版内容，所以不详细解释。
//#pragma GCC optimize (2)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 5e4 + 5;
ll read ()
{
ll x = 0, y = 1;
char c = getchar ();
while (c < '0' || c > '9')
{
if (c == '-') y = -1;
c = getchar ();
}
while (c >= '0' && c <= '9')
{
x = (x << 3) + (x << 1) + (c ^ 48);
c = getchar ();
}
return x * y;
}
void write (ll x)
{
if (x < 0) putchar ('-'), x = -x;
if (x > 9) write (x / 10);
putchar (x % 10 + '0');
}
/*-------------------- Start Code --------------------*/
int n, m, k, B, l = 1, r, cnt;
int a[N], sum[N], ans[N];
struct Qst
{
int l, r, b, k;
// 区间左端点、右端点、所属块的编号、询问编号
bool operator< (const Qst& t) const // 重载运算符，奇偶性排序优化莫队
{
if (b == t.b) return (b & 1) ? (r < t.r) : (r > t.r);
return b < t.b;
}
};
Qst q[N];
int get (int res) // 返回 res 所属块的编号
{
return (res + B - 1) / B;
}
void add (int i) // 增加 a[i] 的贡献，随题目变化而变化
{
cnt += 2 * sum[a[i]] + 1;
sum[a[i]] ++ ;
}
void del (int i) // 除掉 a[i] 的贡献，随题目变化而变化
{
cnt -= 2 * sum[a[i]] - 1;
sum[a[i]] -- ;
}
signed main ()
{
n = read (), m = read (), k = read ();
B = sqrt (n) + 1;
for (int i = 1; i <= n; i ++ ) a[i] = read ();
for (int i = 1; i <= m; i ++ ) q[i].l = read (), q[i].r = read (), q[i].b = get (q[i].l), q[i].k = i;
sort (q + 1, q + m + 1);
for (int i = 1; i <= m; i ++ )
{
while (l > q[i].l) add ( -- l);
while (r < q[i].r) add ( ++ r);
while (l < q[i].l) del (l ++ );
while (r > q[i].r) del (r -- );
ans[q[i].k] = cnt; // 因为在排序中，我们改变了询问间的相对顺序，所以要注意将答案放到对应的 ans 里
}
for (int i = 1; i <= m; i ++ ) write (ans[i]), putchar ('\n');
return 0;
}例题：
P3372 【模板】线段树 1
P1494 [国家集训队] 小 Z 的袜子
P4462 [CQOI2018] 异或序列