前言

莫队，是莫涛发明的一种解决区间查询等问题的算法，基于分块思想，时间复杂度 $O(n \sqrt{q})$ 。

通常来说，莫队题目要求必须支持离线操作，所以如果题目强制在线的话就不能用莫队了。

这里贴一个金句：当有一道题每次问你一个区间的某某问题，而这个东西不可合并（线段树做不了），不可差分（树状数组做不了），分块后不好合并/无法合并（分块做不了），但是支持离线操作，并且任意的一个区间能通过扩张和收缩得到其他区间的答案，那么这道题就可以莫队。

本文以一道莫队模板题为例，来进行莫队的发明。

【模板】莫队 / 小 B 的询问

有一个长为 $n$ 的整数序列 $a$，值域为 $[1,k]$。
一共有 $m$ 个询问，每个询问给定一个区间 $[l,r]$，求：
$$\sum\limits_{i=1}^k c_i^2$$

其中 $c_i$ 表示数字 $i$ 在 $[l,r]$ 中的出现次数。

对于 $100%$ 的数据，$1\le n,m,k \le 10^5$。

简单思考

对于一个区间，设数字 $x$ 出现了 $\mathrm{cnt}[x]$ 次，答案就是：

$$ \mathrm{sum}=\sum_{x=1}^{k}\mathrm{cnt}[x]^2 $$

例如样例中的区间 $1,4$，里面是：

1
1 3 2 1

数字 $1,2,3$ 的出现次数分别为 $2,1,1$，所以答案是：

$$ 2^2+1^2+1^2=6 $$

暴力做法是每次扫描询问区间，统计频次，再求答案。最坏需要 $O(nm)$，这里 $n,m\le 10^5$，显然不行。

你可能会想到线段树，但这道题的答案不容易只用两个子区间的答案合并出来。对于同一个数，它在左右子区间出现了 $u,v$ 次，合并后的贡献是：

$$ (u+v)^2=u^2+v^2+2uv $$

两个子区间的答案没有记录每个数对应的 $u,v$，无法直接算出交叉项。

不过，加入或删除一个元素时，答案很好修改。 这就是本题使用莫队的突破口。

加入或删除一个元素

对于这道题来说，假设当前区间中数字 $x$ 出现了 $c$ 次。

加入一个 $x$ 后，答案由 $c^2$ 变成了 $(c+1)^2$ ，其他的数字贡献不变，所以答案增加 $(c+1)^2 - c^2 = 2c+1$ 。

删除一个 $x$ 也是同理的，只不过答案是从 $c^2$ 变成了 $(c-1)^2$ 。

像这样，我们就可以删去旧的贡献，加上新的贡献，得到结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
void add(int p) {
    int x = a[p];
    sum -= 1LL * cnt[x] * cnt[x];
    cnt[x]++;
    sum += 1LL * cnt[x] * cnt[x];
}

void del(int p) {
    int x = a[p];
    sum -= 1LL * cnt[x] * cnt[x];
    cnt[x]--;
    sum += 1LL * cnt[x] * cnt[x];
}

这里传入的 $p$ 是数组位置，所以 $a_p$ 是数字。

整个算法其实是在维护：cnt[x] 是数字 $x$ 在当前区间 $L,R$ 中的出现次数，sum 是这个区间的答案。

用旧区间算出新区间

假设已经求出了 $1,4$ 的答案，现在要求 $2,6$。

我们不需要重新扫描，我们只需要删除 $1$ 再加入 $5,6$ 就可以得到答案了。

我们进行推广，对于任意的目标区间 $l,r$ ，我们都可以用这四个循环得到：

1
2
3
4
while (L > l) add(--L);
while (R < r) add(++R);
while (L < l) del(L++);
while (R > r) del(R--);

其中 $L,R$ 是已知答案的区间。

初始化时，$L = 1,R = 0$ ，表示当前区间为空，所有频次和答案都是零。按照上面的顺序，先扩展再收缩，也方便保证删除的元素确实在当前区间里。

重新安排询问顺序

如果询问依次在很远的区间反复跳跃，那么端点还是会移动 $O(nm)$ 次，这样就退化为暴力了。但是当所有询问都提前给出的时候，我们可以先改变处理顺序，最后按原顺序输出答案，这个技巧就是离线处理。

莫队的做法是：把数组的位置分成若干个块，每块长度取 $B$ ，通常我们会取：

$B \approx \sqrt{n}$

位置 $p$ 所在的块编号就是：

$bel_p = \lfloor\frac{p-1}{B}\rfloor$

然后按照下面两个规则来排序询问：

  1. 左端点所在块不同，按块编号递增。
  2. 左端点在同一块，按右端点递增。

注意：第一关键字是左端点的块编号，不是左端点本身。

时间复杂度证明

分别数两个端点的移动次数。

对于左端点：

同一块中的两个询问，左端点距离小于 $B$，所以这部分总移动量是 $O(mB)$。块与块之间按顺序推进，额外移动量为 $O(n)$。

对于右端点：

在同一个左端点块内，右端点递增，总移动量是 $O(n)$。切换到下一个块时，右端点可能向左返回，但一次也最多移动 $O(n)$。

一共有大约 $n/B$ 个块，因此右端点总移动量是：

[ O\left(\frac{n^2}{B}\right) ]

每次移动都能 $O(1)$ 更新答案，所以维护部分的复杂度是：

[ O\left(mB+\frac{n^2}{B}+n\right) ]

取 $B\approx\sqrt n$，加上询问排序，得到：

[ O\left((n+m)\sqrt n+m\log m\right) ]

当 $n,m$ 同阶时，通常简称为 $O(n\sqrt n)$。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1e9 + 7;
const ll INF = 4e18;
const int MAXN = 1e5+100;
#define endl '\n'

ll n,m,k,bel[MAXN],a[MAXN],ans[MAXN],B,sum,cnt[MAXN];

struct query {
    ll l,r,id;
}Q[MAXN];

bool cmp(query x,query y) {
    if(bel[x.l]!=bel[y.l]) return bel[x.l]<bel[y.l];
    return x.r<y.r;
}

void add(int p) {
    ll x=a[p];
    sum-=1LL*cnt[x]*cnt[x];
    cnt[x]++;
    sum+=1LL*cnt[x]*cnt[x];
}

void del(int p) {
    ll x=a[p];
    sum-=1LL*cnt[x]*cnt[x];
    cnt[x]--;
    sum+=1LL*cnt[x]*cnt[x];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m>>k;
    B=max(1,int(sqrt(n)));
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        bel[i]=(i-1)/B;
    }
    for(int i=1;i<=m;i++) {
        cin>>Q[i].l>>Q[i].r;
        Q[i].id=i;
    }
    sort(Q+1,Q+1+m,cmp);
    int L=1,R=0;
    for(int i=1;i<=m;i++) {
        int l=Q[i].l,r=Q[i].r;
        while(L>l) add(--L);
        while(R<r) add(++R);
        while(L<l) del(L++);
        while(R>r) del(R--);
        ans[Q[i].id]=sum;
    }
    for(int i=1;i<=m;i++) {
        cout<<ans[i]<<endl;
    }
    return 0;
}