莫队

莫队主要用来快速处理一个数组中多个区间内不同数字的状态

核心思想

  1. 分块：把长度为 \(n\) 的数组分为 若干个 长度为\(\sqrt{n}\) 的块
  2. 离线：对于所有的查询，按照双关键字排序，同一块内按右端点从小到大，否则按块的先后顺序从左到右

定义两个指针 \(l, r\)，代表当前维护的区间是 \([l,r]\)，对于排好序的查询，用双指针依次扫描查询的区间，时间复杂度 \(O(n\sqrt{n})\)

复杂度分析

假设查询的数量也是 \(n\) * 对于 \(l\) 指针，假设每个块内的查询，\(l\) 都要从左到右或者从右到左，每次的距离是\(\sqrt{n}\)，则一共需要跑 \(n\sqrt{n}\)
* 对于 \(r\) 指针，假设每当查询完一个块，\(r\) 指针都在 \(n\)，并且要到当前块的最右边，则一共需要跑 \(n\sqrt{n}-\frac{(1+\sqrt{n})*\sqrt{n}}{2}\)

因此总时间复杂度为 \(O(n\sqrt{n})\)

常数优化

每个块内查询的右边界都是升序排序，导致相邻块过渡的时候，右边界相距过远

因此可以奇数块内的查询按右边界升序排序，偶数块内的查询按左边界降序排序，可以达到减小常数的目的

例题

Luogu P2709 小B的询问

题目描述

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

输入格式

第一行三个整数 \(n,m,k\)。

第二行 \(n\) 个整数，表示小 \(B\) 的序列。

接下来的 \(m\) 行，每行两个整数 \(l,r\)。

输出格式

输出 \(m\) 行，每行一个整数，对应一个询问的答案。

数据范围

\(1 \le n,m,k \le 5 \times 10^4\)

code:

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
63
64
65
66
#include <bits/stdc++.h>

using namespace std;

const int N = 50010;

struct Q
{
    int id, l, r;
}q[N];

int n, m, k;
int b, sum;
int a[N];
int c[N];
int res[N];

bool cmp(Q A, Q B)
{
    if (A.l / b != B.l / b) return A.l < B.l;
    if (A.l / b & 1) return A.r < B.r;
    return A.r > B.r;
}

void add(int x)
{
    sum -= c[x] * c[x];
    c[x]++;
    sum += c[x] * c[x];
}

void del(int x)
{
    sum -= c[x] * c[x];
    c[x]--;
    sum += c[x] * c[x];
}

int main()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int i = 1; i <= m; i++)
    {
        int l, r;
        cin >> l >> r;
        q[i] = {i, l, r};
    }

    b = sqrt(n);
    sort(q + 1, q + 1 + m, cmp);

    for (int i = 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--]);
        res[q[i].id] = sum;
    }

    for (int i = 1; i <= m; i++) cout << res[i] << endl;

    return 0;
}