分块算法#

什么是分块算法#

分块是一种思想，对整块整体处理，对零散快单独处理。

分块实际上就是暴力，不过可以被称为“优雅的暴力”。分块能解决很多类型的问题，很多算法也利用了分块的思想并进行优化。莫队的很多题目中也会一并使用分块来解决。

另外分块也可以分为图论分块，数论分块，字符串分块，数据结构分块等等，分块所设计的领域非常广，往往也可以使用分块来解决一些看似需要高深算法来解决的问题。

例如：P3372 【模板】线段树 1

显然利用现在所学知识无法在 $O(nlogn)$ 的时间复杂度下来解决此问题，那么这时我们可以考虑使用这种算法。

何时分块#

再给出一个块，块长为 $N$ ，要求求解区间 $[l,r]$ 的部分相关问题，如求解区间 $[l,r]$ 的最大值，最小值和区间和等问题。这时我们可以来维护区间 $[l,r]$ 内的块和附近的少量元素。

如何分块#

块长#

我们可以通过“猜”的方式来大致得出相对优秀的块长

长度为 $1$ ？长度为 $n$ ？如分
长度为 $\frac{n}{2}$ 依然很难维护
长度为 $logn$ 需要维护 $\frac{n}{logn}$ 的块假设数据范围为 $2e5$ 是大约 $38000$ 个块
长度为 $\sqrt{n}$ 需要维护 $\sqrt{n}$ 的块只需要维护 $450$ 个块

实际上块的大小可以通过计算得出

若以顺序查找来确定块，则分块查找成功时的平均查找长度为

ASL_{ls}=L_{b}+L_{w}=\frac{b+1}{2}+\frac{s+1}{2}=\frac{\frac{n}{s}+s}{2}+1=\frac{n+s^{2}}{2s}+1

$n$ 为查找表的长度， $s$ 为块的长度

$b=⌈\frac{n}{s}⌉$ 为块的个数。当 $s=\sqrt{n}$ 时， $ASL_{ls}$ 取最小值 $\sqrt{n}+1$

时间复杂度#

$n$ 次询问，长度为 $m$ ，时间复杂度为 $O(n\sqrt{m})$ ，准确来说为 $O(n\sqrt{n}+n\sqrt{m})$

实现思路#

我们具体需要维护的有如下三点：

在前面的一部分零散的元素
中间的若干个整块
后面的一部分零散的元素

具体实现#

P3372 【模板】线段树 1

1
int a[N], st[N], ed[N], sum[N], add[N], len, id[N];
2

3
void change(int l, int r, int k) {
4
  if (id[l] == id[r]) {
5
    for (int i = l; i <= r; i++) {
6
      a[i] += k;
7
      sum[id[i]] += k;
8
    }
9
  } else {
10
    for (int i = l; i <= ed[l]; i++) {
11
      a[i] += k;
12
      sum[id[i]] += k;
13
    }
14
    for (int i = st[r]; i <= r; i++) {
15
      a[i] += k;
16
      sum[id[i]] += k;
17
    }
18
    for (int i = id[l] + 1; i < id[r]; i++) {
19
      add[i] += k;
20
    }
21
  }
22
}
23

24
int query(int l, int r) {
25
  int ans = 0;
26
  if (id[l] == id[r]) {
27
    for (int i = l; i <= r; i++) {
28
      ans += a[i] + add[id[i]];
29
    }
30
  } else {
31
    for (int i = l; i <= ed[l]; i++) {
32
      ans += a[i] + add[id[i]];
33
    }
34
    for (int i = st[r]; i <= r; i++) {
35
      ans += a[i] + add[id[i]];
36
    }
37
    for (int i = id[l] + 1; i < id[r]; i++) {
38
      ans += sum[i] + add[i] * (ed[i] - st[i] + 1);
39
    }
40
  }
41
  return ans;
42
}
43

44
void solve() {
45
  int n, m;
46
  cin >> n >> m;
47
  len = sqrt(n);
48
  for (int i = 1; i <= n; i++) {
49
    cin >> a[i];
50
    id[i] = (i - 1) / len + 1;
51
    st[i] = (id[i] - 1) * len + 1;
52
    ed[i] = min(id[i] * len, n);
53
    sum[id[i]] += a[i];
54
  }
55
  while (m--) {
56
    int op, x, y, k;
57
    cin >> op >> x >> y;
58
    if (op == 1) {
59
      cin >> k;
60
      change(x, y, k);
61
    } else {
62
      cout << query(x, y) << endl;
63
    }
64
  }
65
}

P3865 【模板】ST 表 && RMQ 问题

1
int st[N], ed[N], mx[N], id[N], a[N], len;
2

3
int query() {
4
  int ans = 0;
5
  int l, r;
6
  cin >> l >> r;
7
  if (id[l] == id[r]) {
8
    for (int i = l; i <= r; i++) {
9
      ans = max(ans, a[i]);
10
    }
11
  } else {
12
    for (int i = l; i <= ed[id[l]]; i++) {
13
      ans = max(ans, a[i]);
14
    }
15
    for (int i = st[id[r]]; i <= r; i++) {
16
      ans = max(ans, a[i]);
17
    }
18
    for (int i = id[l] + 1; i <= id[r] - 1; i++) {
19
      ans = max(ans, mx[i]);
20
    }
21
  }
22
  return ans;
23
}
24

25
void solve() {
26
  int n, m;
27
  cin >> n >> m;
28
  len = sqrt(n);
29
  for (int i = 1; i <= n; i++) {
30
    cin >> a[i];
31
    id[i] = (i - 1) / len + 1;
32
    st[id[i]] = (id[i] - 1) * len + 1;
33
    ed[id[i]] = id[i] * len;
34
    mx[id[i]] = (i == st[id[i]]) ? a[i] : max(mx[id[i]], a[i]);
35
  }
36
  while (m--) {
37
    cout << query() << endl;
38
  }
39
}

莫队算法#

莫队？#

alt text

何为莫队算法#

为了解决区间问题，最开始的区间问题是前缀和，然后出现越来越难的问题，越来越困难的算法：分块，RMQ，树状数组，线段树等等，于是莫队算法出现，就是为了解决这类的区间问题。

分块算法和莫队算法的异同#

同：

都是为了解决区间问题而存在

异：

莫队查询的更快但是只能离线查询
分块查询的更慢但是可以在线查询

离线查询：查询操作是在已知所有查询的情况下进行的。也就是说，在开始查询之前，所有的查询都已经确定并且可以提前处理。

在线查询：查询操作是在不知道所有查询内容的情况下进行的。每次查询时都立即处理，不会提前对查询进行任何优化。查询顺序通常是动态的。

莫队算法基本原理#

利用双指针来进行区间的移动查询

莫队算法的核心#

1
while (l > q[i].l) {
2
  add(a[--l]);
3
}
4
while (r < q[i].r) {
5
  add(a[++r]);
6
}
7
while (l < q[i].l) {
8
  del(a[l++]);
9
}
10
while (r > q[i].r) {
11
      del(a[r--]);
12
}

具体实现

P1494 [国家集训队] 小 Z 的袜子

1
int a[N], sum, ans1[N], len, ans2[N], cnt[N];
2

3
struct query {
4
  int l, r, id;
5
} q[N];
6

7
void add(int x) {
8
  sum += cnt[x];
9
  cnt[x]++;
10
}
11

12
void del(int x) {
13
  cnt[x]--;
14
  sum -= cnt[x];
15
}
16

17
void solve() {
18
  int n, m;
19
  cin >> n >> m;
20
  len = sqrt(n);
21
  for (int i = 1; i <= n; i++) {
22
    cin >> a[i];
23
  }
24
  for (int i = 1; i <= m; i++) {
25
    cin >> q[i].l >> q[i].r;
26
    q[i].id = i;
27
  }
28
  sort(q + 1, q + m + 1, [](const query &lhs, const query &rhs) {
29
    if ((lhs.l - 1) / len != (rhs.l - 1) / len) return lhs.l < rhs.l;
30
    return lhs.r < rhs.r;
31
  });
32

33
  for (int i = 1, l = 1, r = 0; i <= m; i++) {
34
    if (q[i].l == q[i].r) {
35
      ans1[q[i].id] = 0;
36
      ans2[q[i].id] = 1;
37
      continue;
38
    }
39
    while (l > q[i].l) {
40
      add(a[--l]);
41
    }
42
    while (r < q[i].r) {
43
      add(a[++r]);
44
    }
45
    while (l < q[i].l) {
46
      del(a[l++]);
47
    }
48
    while (r > q[i].r) {
49
      del(a[r--]);
50
    }
51
    if (sum == 0) {
52
      ans1[q[i].id] = 0;
53
      ans2[q[i].id] = 1;
54
      continue;
55
    }
56
    ans1[q[i].id] = sum;
57
    ans2[q[i].id] = (r - l + 1) * (r - l) / 2;
58
    int t = __gcd(ans1[q[i].id], ans2[q[i].id]);
59
    ans1[q[i].id] /= t;
60
    ans2[q[i].id] /= t;
61
  }
62
  for (int i = 1; i <= m; i++) {
63
    cout << ans1[i] << '/' << ans2[i] << endl;
64
  }
65
}

普通莫队的优化#

奇偶排序优化#

对于如下数据：

经过排序后的等效数据：

手动模拟一下可以发现，指针的移动次数大概为 $300$ 次，我们处理完第一个块之后 $(l=2，r=100)$ ，此时只需要移动2次指针到 $l=4, r=100$ 就可以得到第四个询问的答案，再移动 $100$ 次到 $l=3，r=1$ 就可以得到第三次询问的答案，但是我们却将指针移动 $100$ 次到 $l=3，r=1$ 来获取第三个询问的答案，再移动 $100$ 次到 $l=4，r=100$ 获取第四个询问的答案，这样多了 $98$ 次的指针移动。我们怎么优化这个地方呢？

这里我们就要用到奇偶化排序。什么是奇偶化排序？奇偶化排序即对于属于奇数块的询问， $r$ 按从小到大排序，对于属于偶数块的排序， $r$ 从大到小排序，这样我们的 $r$ 指针在处理完这个奇数块的问题后，将在返回的途中处理偶数块的问题，再向 $n$ 移动处理下一个奇数块的问题，优化了 $r$ 指针的移动次数，理论上能快一倍。

优化后并排序后的等效数据：

1
  sort(q + 1, q + m + 1, [](const query &lhs, const query &rhs) {
2
    if ((lhs.l - 1) / len != (rhs.l - 1) / len) {
3
      return lhs.l < rhs.l;
4
    }
5
    if (((lhs.l - 1) / len + 1) & 1) {
6
      return lhs.r < rhs.r;
7
    }
8
    return lhs.r > rhs.r;
9
  });

1
bool cmp(node a,node b) {
2
  return pos[a.l] ^ pos[b.l] ? pos[a.l] < pos[b.l] : pos[a.l] & 1 ? a.r < b.r : a.r > b.r;
3
}

块的大小优化#

alt text

网上大多都说分块大小取 $\sqrt{n}$ 最优，此时时间复杂度为 $O(n\sqrt{n})$ ，实际上这是不严谨的，当 $n$ ， $m$ 差距较大时使用 $\sqrt{n}$ 作为分块大小效率会明显降低。

普通莫队时间复杂度的证明：

具体证明方法有多种：

第一种（By yihang_01）

alt text

第二种

排序 $O(nlogn)$
网页渲染有点问题，所以贴了张图片。
右端点在一个左端点相同的块内是有序的，那么对于每一个块 $i$ 中的 $x_{i}$ 个区间，右端点最多跳完整的一个序列（就是不会往回跳），一共有 $\sqrt{n}$ 个块，所以总时间复杂度为 $O(n\sqrt{n})$

第三种

分块相同时，右端点递增是 $O(n)$ 的，分块共有 $O(\sqrt{n})$ 个，复杂度为 $n^{1.5}$

分块转移时，右端点最多变化 $N$ ，分块共有 $O(\sqrt{n})$ 个，复杂度为 $n^{1.5}$

分块相同时，左端点最多变化 $\sqrt{n}$ ，分块转移时，左端点最多变化 $2\sqrt{n}$

共有 $N$ 个询问，复杂度为 $n^{1.5}$

综上， $n$ 次询问，长度为 $m$ ，块大小为 $\sqrt{m}$ 的莫队，时间复杂度为 $O(n\sqrt{m})$ 。

普通莫队最优块长的证明：

设每一块的大小为 $T$ ，序列长为 $n$ ，询问个数为 $m$ 。

那么最多有 $\frac{n}{T}$ 块。

对于右端点的移动，每一块最多移动 $n$ 次，有 $\frac{n}{T}$ 块，所以右端点时间复杂度为 $O\left(\frac{n^2}{T}\right)$ 。

对于左端点的移动，每一次最多移动 $T$ 次，有 $m$ 次移动，所以左端点时间复杂度为 $O(mT)$ 。

那么总时间复杂度为 $O\left(\frac{n^2}{T} + mT\right)$ 。

设 $\frac{n^2}{T} + mT = S$ 。

原式等于 $n^2 + mT^2 - ST = 0$ 。

这样变为一个经典的二次函数求最小值的问题。

$\Delta = S^2 - 4mn^2 \geq 0$

为取到最小值， $\Delta = 0$ 。

那么 $S^2 - 4mn^2 = 0$ 。

$S^2 = 4mn^2$

$S = 2\sqrt{mn}$

代入回 $x = -\frac{b}{2a} + \frac{\sqrt{\Delta}}{2a}$

算出 $T = \frac{n}{\sqrt{m}}$

其他莫队#

带修莫队#

前面说过，普通莫队只能解决没有修改的问题，那么如果想解决修改问题呢？

P1903 [国家集训队] 数颜色 / 维护队列

那就需要带修莫队，带修莫队就是一种支持修改查询的莫队。

当然，这是一道在线问题，但我们可以把这个在线问题转化为离线问题。

普通莫队是把点经过排序，下一次询问是从上一次询问转移而来，但是有修改的问题在经过排序后，查询的结果也会随着排序而改变，把所有的修改操作加上一个时间戳 $[l,r,time]$ 。

排序规则：第一关键字为左端点所在块 $\frac{l}{B}$ ，第二关键字为右端点所在块 $\frac{r}{B}$ ，第三关键字是时间 $t$ 。

每次询问先做区间拓展，再考虑时间戳，也就是之前的修改对当次查询的影响。

(1) $j$ > $i$ ，则把 $i+1$ 到 $j$ 个修改的贡献加上

(2) $j$ < $i$ ，则把 $i$ 到 $j+1$ 个修改的贡献还原

带修莫队的时间复杂度及最优块长的证明#

块的大小为 $B^{\frac{2}{3}}$ ,修改个数为 $c$ ，询问次数为 $q$ ，则总移动次数为 $O(\frac{cn^{2}}{B^{2}}+qB+\frac{n^{2}}{B})$ ，操作次数为 $m$ 的话，则为 $O(\frac{mn^{2}}{B^{2}}+mB+\frac{n^{2}}{B})$ 。

$B$ 可以取 $B=\frac{n^2}{3^{\frac{1}{2}}(9m^3n^2+\sqrt{3}\sqrt{27m^6n^4-m^3n^6})^{\frac{1}{3}}}+ \frac{(9m^3n^2+\sqrt{3}\sqrt{27m^6n^4 - m^3n^6})^{\frac{1}{3}}}{3^{\frac{2}{3}}m}$

正常写题时肯定不会去算这么离谱的一个块长 $B$ ，直接视作 $n=m$ 的话，就可以得到总移动次数为 $O(\frac{n^{3}}{B^{2}}+nB+\frac{n^{2}}{B})$ ，那么当 $B=n^{\frac{2}{3}}$ 时，取得最小值，此时最小值为 $O(n^{\frac{5}{3}})$ 。

同样，对于最优块长也可以做如下证明：

可以这么认为，序列的值是随着时间而变化的。

那我们就在坐标系上再加上一个时间维度，用 $(l,r,t)$ 来表示一个查询

alt text

很明显，我们需要分别按照l与r分块，在同一块内的询问按照t从小到大完成。块的大小就是 $n^{\frac{2}{3}}$ ，只是这个粗略得出的块长只是相对优秀的，而不是最优。

综上，带修莫队的渐进时间复杂度为 $O(nlogn+n^{\frac{5}{3}})$ （视作 $n=m$ ），认为是 $O(n^{\frac{5}{3}})$ 。

实现过程#

对于询问，我们记录以下值：

1
struct kkk {
2
  int l;  //左端点
3
  int r;  //右端点
4
  int t;  //此询问前修改数量
5
  int id;  //询问编号
6
}q[N];

对于修改，我们记录以下值：

1
struct ttt {
2
  int id;  //修改位置
3
  int val;//修改值
4
}c[N];

将原来值对答案的影响抹去，再将修改值对答案的影响加上，然后更新该位置的值

1
#define add(x) {
2
  if(++vis[x]==1)sum++;
3
}
4
#define del(x) {
5
  if(--vis[x]==0)sum--;
6
}
7
void change(int x) {
8
  if(c[x].id>=l&&c[x].id<=r) {
9
    del(v[c[x].id]);
10
    add(c[x].val);
11
  }  //改变影响
12
  swap(c[x].val,v[c[x].id]);    //值更新 *
13
}
14
...
15
while(now<q[i].t)change(++now);  //修改
16
while(now>q[i].t)change(now--);  //修改

这道题能转化为离线的根本原因是这一次的查询并不需要使用上一次的查询结果，只是题目让我们立即返回查询结果，但当次结果只是依赖于之前的修改，而不是依赖于之前的查询，所以我们给修改打上一个时间戳就可以了。

{% folding 查看代码 By huangce %}

1
int n, m;
2
int len;
3
int mq, mr;
4
struct op {
5
  int l, r;
6
  int idx, tim;
7
  bool operator<(const op& that) const {
8
    if (l / len != that.l / len) return l < that.l;
9
    if (r / len != that.r / len) return r < that.r;
10
    return tim < that.tim;
11
  }
12
} q[N];
13
struct modify {
14
  int p, c;
15
} R[N];
16
int a[N], cnt[N];
17
int ans[N];
18
int res;
19
void add(int x) {
20
  if (cnt[x] == 0) res++;
21
  cnt[x]++;
22
}
23
void del(int x) {
24
  cnt[x]--;
25
  if (cnt[x] == 0) res--;
26
}
27
void solve() {
28
  cin >> n >> m;
29
  len = pow(n, 2.0 / 3.0);
30
  int l, r;
31
  char ch;
32
  for (int i = 1; i <= n; i++) {
33
    cin >> a[i];
34
  }
35
  for (int i = 1; i <= m; i++) {
36
    cin >> ch >> l >> r;
37
    if (ch == 'Q')
38
      q[++mq] = {l, r, mq, mr};
39
    else
40
      R[++mr] = {l, r};
41
  }
42
  sort(q + 1, q + 1 + mq);
43
  for (int i = 1, l = 1, r = 0, x = 0; i <= mq; i++) {
44
    while (q[i].l < l) add(a[--l]);
45
    while (r < q[i].r) add(a[++r]);
46
    while (l < q[i].l) del(a[l++]);
47
    while (q[i].r < r) del(a[r--]);
48

49
    // 时间戳
50
    // 要将 a[pos] 和 R[x].c 交换，而不能用其他变量代替，因为需要来回滚动
51
    while (x < q[i].tim) {
52
      ++x;  // 先加
53
      int pos = R[x].p;
54
      // 修改数在区间内
55
      if (l <= pos && pos <= r) {
56
        add(R[x].c);
57
        del(a[pos]);
58
      }
59
      swap(a[pos], R[x].c);
60
    }
61
    while (x > q[i].tim) {
62
      int pos = R[x].p;
63
      if (l <= pos && pos <= r) {
64
        add(R[x].c);
65
        del(a[pos]);
66
      }
67
      swap(a[pos], R[x].c);
68
      x--;  // 后减
69
    }
70
    ans[q[i].idx] = res;
71
  }
72

73
  for (int i = 1; i <= mq; i++) {
74
    cout << ans[i] << endl;
75
  }
76
}

回滚莫队#

当删除或增加的其中一个在操作时，不能或者不方便统计答案时，可以尝试使用回滚莫队解决。

原题链接

歴史の研究(Historical Research)

第１３回日本情報オリンピック　春季トレーニング合宿

zh-CN链接

歴史の研究

实现过程#

对于左右端点在同一块的暴力计算。
跟普通莫队一样排序，左端点换块时清空答案，把左指针设为左端点所在块的下一块的开头，把右指针设为左端点所在块的最后一位。这样右指针是单调递增的，每处理一个询问时，先记录一些信息（比如答案），再左移左指针并更新答案，然后把左指针移回左端点所在块的下一块的开头，过程中回滚除记录下的信息以外的其它影响，最后把记录下的信息恢复。如：先右移右指针，再记录 $ans$ ，然后左移左指针时增加 $cnt$ 并更新 $ans$ ，回滚时把增加的 $cnt$ 减掉，最后把 $ans$ 回滚为记录的值。

{% folding 查看代码 By yihang_01 %}

1
int n, m, a[N], len, cnt1[N], cnt2[N], ans[N], st[N], ed[N], id[N], b[N], p;//cnt1 为统计数字个数的桶，cnt2 为处理暴力结果的桶，ans 为答案数组，b 为离散化后的数组，p 为离散化后的数组长度
2

3
struct query {
4
    int l, r, id;
5
    bool operator<(const query &rhs) const {
6
        if (::id[l] != ::id[rhs.l]) return l < rhs.l;
7
        return r < rhs.r;
8
    }
9
} q[N];
10

11
void add(int x, int &tmp) {
12
    ++cnt1[x];
13
    tmp = max(tmp, cnt1[x] * b[x]);
14
}
15

16
void del(int x) { --cnt1[x]; }
17

18
void solve() {
19
    cin >> n >> m;
20
    len = sqrt(n);
21
    for (int i = 1; i <= n; i++) {
22
        cin >> a[i];
23
        b[i] = a[i];
24
        id[i] = (i - 1) / len + 1;
25
        st[i] = (id[i] - 1) * len + 1;
26
        ed[i] = min(id[i] * len, n);
27
    }
28
    for (int i = 1; i <= m; i++) {
29
        cin >> q[i].l >> q[i].r;
30
        q[i].id = i;
31
    }
32
    sort(q + 1, q + m + 1);
33

34
    // 离散化
35
    sort(b + 1, b + n + 1);
36
    p = unique(b + 1, b + n + 1) - b - 1;
37
    for (int i = 1; i <= n; i++)
38
        a[i] = lower_bound(b + 1, b + p + 1, a[i]) - b;//a 数组现在存放的是离散化后的值
39
    int now = 0, last = 0, lstl = 0, tmp = 0;
40
    for (int i = 1, l = 1, r = 0; i <= m; i++) {
41
        if (id[q[i].l] == id[q[i].r]) {  // 左右区间属于同一块则进行暴力处理答案
42
            for (int j = q[i].l; j <= q[i].r; j++) ++cnt2[a[j]];
43
            for (int j = q[i].l; j <= q[i].r; j++)
44
                ans[q[i].id] = max(ans[q[i].id], cnt2[a[j]] * b[a[j]]);
45
            for (int j = q[i].l; j <= q[i].r; j++) --cnt2[a[j]];
46
            continue;
47
        }
48
        // 访问到了新的块，先把上一个块的答案清空
49
        if (id[q[i].l] != last) {
50
            while (r > ed[q[i].l]) del(a[r--]);   // 右指针移至上一个区间的右端点
51
            while (l <= ed[q[i].l]) del(a[l++]);  // 左指针右移至下一个区间的左端点
52
            tmp = 0;
53
            last = id[q[i].l];
54
        }
55
        // 扩展右指针
56
        while (r < q[i].r) add(a[++r], tmp);
57
        lstl = l;  // 准确来说 l 才是原先的左指针
58
        now = tmp;  // 非常重要
59
        // 扩展左指针
60
        while (lstl > q[i].l) add(a[--lstl], now);
61
        ans[q[i].id] = now;
62
        // 回滚左指针
63
        while (lstl < l) del(a[lstl++]);
64
    }
65
    for (int i = 1; i <= m; i++) cout << ans[i] << '\n';
66
}

树上莫队#

莫队算法的出现正是为了解决部分数据结构相关问题而存在，当然可以上树。

P2325 [SCOI2005] 王室联邦这道题目可以说是专为树上莫队设计的题目。

分块方式#

这里提供一种构造方式，证明略。

dfs，并创建一个栈，dfs一个点时先记录初始栈顶高度，每dfs完当前节点的一棵子树就判断栈内（相对于刚开始dfs时）新增节点的数量是否≥B，是则将栈内所有新增点分为同一块，核心点为当前dfs的点，当前节点结束dfs时将当前节点入栈，整个dfs结束后将栈内所有剩余节点归入已经分好的最后一个块。

1
void solve() {
2
  auto dfs = [&](auto &&self, auto u, auto fa) -> auto {
3
    int t = top;
4
    for (int i = head[u]; i; i = nxt[i]) {
5
      int v = to[i];
6
      if (v != fa) {
7
        dfs(v, u);
8
        if (top - t >= B) {
9
          key[++tot] = u;
10
          while (top > t) bl[stk[top--]] = tot;
11
        }
12
      }
13
    }
14
    stk[++top] = u;
15
  };
16
  dfs(1, 0);
17
  if (!tot) ++tot;
18
  key[tot] = 1;
19
  while (top) bl[stk[top--]] = tot;
20
}

lambda函数原本是不支持递归的，但是有几种方法使其支持递归：

传入参数 auto &&self 如 auto dfs = [&](auto &&self, auto u, auto fa) -> auto 递归时使用self递归
采用匿名函数如 function<void(int,int)> dfs = [&](auto u,auto fa) -> auto 递归时使用原函数名递归
采用Deducing this特性如 auto dfs = [&] self(auto u, auto fa) -> auto 递归时使用self名递归

为什么lambda自身在定义时无法被调用

匿名性：Lambda 表达式是匿名的，编译器在定义时不为其生成名称，因此无法在其内部直接引用或调用自己。
捕获和名称：在 lambda 定义时，虽然可以捕获外部变量，但不能直接引用自身，因为 lambda 的名字在定义时尚未确定。

auto dfs = … 的写法只是将一个 Lambda 表达式赋值给名为dfs的变量，并没有定义一个真正的命名函数。它本质上是一个匿名函数，只是通过auto dfs来保存该变量，而非声明了一个具名函数。

修改方式#

所谓“修改”，就是由询问 $(cu, cv)$ 更新至询问 $(tu, tv)$ 。

如果把两条路径上的点全部修改，复杂度是和暴力一样的，所以需要做一些处理。

$T(u, v)$ 表示 $u$ 到 $v$ 的路径上除 $lca(u, v)$ 外的所有点构成的集合， $S(u, v)$ 代表 $u$ 到 $v$ 的路径， $xor$ 表示集合对称差（就跟异或差不多）。

两个指针 $cu, cv$ （相当于序列队的 $l, r$ 两个指针）， $ans$ 记录 $T(cu, cv)$ 的答案， $vis$ 数组记录每个节点是否在 $T(cu, cv)$ 内。
由 $T(cu, cv)$ 更新至 $T(tu, tv)$ 时，将 $T(cu, tu)$ 和 $T(cv, tv)$ 的 $vis$ 分别取反，并相应地更新答案。
将答案记录到 $out$ 数组（离线后用于输出那个）时对 $lca(cu, cv)$ （此时的 $cu, cv$ 已更新为上一步中的 $tu, tv$ ）的 $vis$ 取反并更新答案，记录完再改回来（因为 $lca$ 处理比较麻烦，这样搞比较方便）。

$T(cu, cv) \oplus T(tu, tv)$

$= (S(cu, root) \oplus S(cv, root)) \oplus (S(tu, root) \oplus S(tv, root))$

$= (S(cu, root) \oplus S(tu, root)) \oplus (S(cv, root) \oplus S(tv, root))$

$= T(cu, tu) \oplus T(cv, tu)$

之所以要把 $T(cu, cv) \oplus T(tu, tv)$ 转化成 $T(cu, tu) \oplus T(cv, tu)$ ，是因为这样的话就能通过对询问排序来保证复杂度。排序方式就是以 $u$ 所在块编号为第一关键字， $v$ 的编号为第二关键字排序。如果结合了带修莫队，就还要以时间为第三关键字。

时间复杂度#

不带修： $O(n\sqrt{m})$ ，带修： $O(n^{\frac{5}{3}})$

#58. 【WC2013】糖果公园

莫队的在线化改造#

P1903 [国家集训队] 数颜色 / 维护队列

上面这道题做如下修改：

在读入每个更新操作的位置 $P$ 时，把 $P$ 用上一次 $Query$ 的答案进行异或后再得到真正的 $P$ 。

有了这个背景，就能更清楚的理解为什么原题可以改造为离线了，而这道修改后的题目不可以。正因为每次修改操作紧密联系于上一次查询操作，必须真的按照题目的要求“立即输出查询结果”才能进行此次修改，而原题可以假的“立即输出”。如果把这道题强行加上时间戳，如果经过排序后第 $1$ 个修改操作是原来的第 $99$ 个修改，那此次操作需要用到第 $98$ 行的查询结果（假设输入为一行修改+一行查询），而想要得到 $98$ 行的查询结果，有需要用到 $97$ 行的修改，反复套娃，这个排序不如不排，时间复杂度直接变为 $O(n^{2})$ 。

所以这下真的变成在线了，不能用莫队了。

但我相信大家是不会使用Spaly/Fenwick/Segt（可能是主席树）来做这道题的（以上均为口胡，没写过）。

不，这道题还可以使用莫队，我们可以强行来用莫队，进行莫队的在线化改造！

普通莫队的在线化改造#

在线化改造的关键#

我们都知道，普通的莫队算法会先把所有查询离线排好序，然后通过“从上一个查询区间转移到下一个区间”的方式来快速计算答案。

但如果我们想把莫队算法“在线化”，就不能简单地从上一个查询区间直接转移。为应对这种情况，可以先挑选出一些特别的区间作为“特征区间”，并处理这些特征区间的答案，让这些区间成为莫队中的“上一个区间”，在线查询就能从相应的特征区间“跳转”过来。

特征区间的要求#

这些特征区间的所有信息，必须能在可接受的时间复杂度内全部算出来。
对于任意一个真实查询，都能在合适的时间内从某个特征区间转移过来。

选取特征点#

假设我们在序列中每隔 $d$ 步选一个“特征点”，并且把任意两个特征点之间的区间都做成特征区间。

这样，预处理时的复杂度大约是 $O(\frac{n^{2}}{d})$ 。
当处理一个真实查询时，如果只要移动区间的左右端点分别不超过 $\frac{d}{2}$ 步，那么就能从相应的特征区间转移到真实查询的区间，花费 $O(d)$ 的时间。
可以证明 $d=\sqrt{n}$ 最优。

保存特征区间信息#

为了在后来能够复用特征区间的信息，需要记录下：

特征区间的答案本身。
莫队所需的辅助信息，比如每种颜色在区间内出现的次数等（常见于莫队中统计出现频次的需求），往往是几个数组。

直接记住所有特征区间的完整信息可能会占用过多的空间导致爆空间。绝大多数莫队所需要的数据都具有“可减”性质（例如出现次数可以通过增减来实现维护），所以我们只需要把 $[1, s_{i}]$ 这前缀范围的信息保存起来，需要时再用前缀和或加减方法获得目标区间的数据。

实现步骤#

先对所有特征区间做预处理，存下它们的答案和辅助信息。
当真正查询出现时，先找到“最近”的特征区间，再通过不超过 $\frac{d}{2}$ 步的端点移动，将这个特征区间调整到查询所需的区间，并得出结果。

这样一来，就能把原本只能离线处理的莫队，做成一个“在线化”的版本，成功实现了莫队的在线化改造。

带修莫队的在线化改造#

普通莫队的改造中提到的特征区间预处理只是个常见的小技巧，但需要在预处理阶段对所有特征区间的答案和信息进行保存，这让我们在支持修改时很麻烦。

回顾带修莫队做法：在每次查询前，先把修改操作处理到当前时间，维护相关结构后再进行查询。此时常见的数据结构（如线段树）通常是“懒标记”地处理修改，只有在真正需要的时候才更新。

本算法则类似：

我们仍然划分特征区间，并在预处理时保存中间信息，但在执行修改时不直接更新特征区间的答案，仅更新莫队维护的核心信息（如颜色出现次数等）即可。
询问发生时，如果特征区间的答案早就过期（上次更新时间小于当前时间），就先更新它，再从这个特征区间转移到目标区间并得到正确答案。
由于莫队在维护中间信息时是最新的，所以真正计算答案时要“反向”更新，以保证最终求得的是当前正确结果。

时间复杂度分析#

若 $d=n^{\frac{2}{3}}$ ，则选取的特征点有 $O(n^{\frac{1}{3}})$ 个。
每次修改若强行更新所有预处理区间会导致极高复杂度，所以采用“懒更新”方式，仅在需要时才刷新对应区间的答案。
总整体复杂度约为 $O(n^{\frac{5}{3}})$ ，与带修莫队相当，但原则上不会达到最坏情况。

实现步骤简要#

预处理：计算并存下所有特征区间的答案 + 中间信息
修改：只更新莫队中间状态，不更新特征区间答案
查询：
- 若特征区间答案过期，先更新
- 再用不超过 $\frac{d}{2}$ 次移动，将特征区间扩展/收缩到查询区间，输出结果

时空复杂度的分析#

在普通莫队基础上做在线化改造，时间复杂度保持不变，但会额外消耗 $O(n)$ 的空间；在带修莫队基础上做改造，时间复杂度也与带修莫队相同，但需要额外 $O(n^{\frac{1}{3}})$ 的空间。尽管改造过程只需“向前修改”，常数因素仍会导致实际运行效率与原带修莫队相差不大。

1
#include <bits/stdc++.h>
2
using namespace std;
3
const int MAXN = 50050;
4
const int BLNB = 550;
5
const int COL = 1000050;
6
void read(int &x) {
7
  char ch;
8
  while (ch = getchar(), ch < '!');
9
  x = ch - 48;
10
  while (ch = getchar(), ch > '!') x = (x << 3) + (x << 1) + ch - 48;
11
}
12
int target[MAXN];
13
struct Change {
14
  int p, col, las;
15
} change[MAXN];
16
int nc, n, m, mp[COL], tot, D, cnt[BLNB][MAXN * 2], c[MAXN], blnm, spe[BLNB];
17
int CNT[MAXN * 2], ans[BLNB][BLNB], ima, tim[BLNB][BLNB], id[MAXN];
18
// 细节：我们不能直接在cnt[][]上做更改，所以需要记录一个临时的变化量数组CNT[]
19
// 变量解释：nc表示当前时间，mp[]和tot是离散化用的，D表示特征点步长，cnt[][]是预处理的莫队信息，id[]记录下标为i的特征点是第几个特征点，spe[]用于存储所有的特征点下标，ans[][]表示特征区间的答案，tim[][]记录答案的上一次更新时间，target[]表示离位置i最近的特征点坐标。
20
inline int getc(int sl, int sr, int p) {
21
  if (sl == 0 && sr == 0)
22
    return 0;
23
  else {
24
    if (c[sl] == p)
25
      return cnt[id[sr]][p] - cnt[id[sl]][p] + 1;
26
    else
27
      return cnt[id[sr]][p] - cnt[id[sl]][p];
28
  }  // 细节：端点特判一下
29
}
30
// 函数作用：读取区间[sl,sr]中的莫队数组信息。
31
inline void del(int pos, int sl, int sr) {
32
  if ((--CNT[c[pos]]) + getc(sl, sr, c[pos]) == 0) --ima;
33
}
34
inline void add(int pos, int sl, int sr) {
35
  if ((++CNT[c[pos]]) + getc(sl, sr, c[pos]) == 1) ++ima;
36
}
37
int main() {
38
  read(n);
39
  read(m);
40
  D = pow(n, 2.0 / 3);  // 带修莫队的块大小
41
  for (int i = 1; i <= n; ++i) {
42
    read(c[i]);
43
    if (!mp[c[i]])
44
      c[i] = mp[c[i]] = ++tot;
45
    else
46
      c[i] = mp[c[i]];
47
  }
48
  int tmp = 1;
49
  spe[blnm = 1] = 1;
50
  id[1] = 1;
51
  for (int i = 1; i <= n; ++i) {
52
    if (i - tmp == D) tmp = i, spe[++blnm] = i, id[i] = blnm;
53
    target[i] = tmp;
54
  }  // 预处理特征点以及每个点对应的离它最近的特征点
55
  int p = 1;
56
  for (int i = 1; i <= n; ++i) {
57
    ++CNT[c[i]];
58
    if (i == spe[p]) {
59
      for (int j = 1; j <= n; ++j) cnt[p][j] = CNT[j];
60
      ++p;
61
    }
62
  }  // 预处理莫队所需信息
63
  for (int i = 1; i <= blnm; ++i) {
64
    int p = i + 1;
65
    ima = 0;
66
    memset(CNT, 0, sizeof CNT);
67
    for (int j = spe[i]; j <= n; ++j) {
68
      if ((++CNT[c[j]]) == 1) ++ima;
69
      if (j == spe[p]) {
70
        ans[i][p] = ima;
71
        ++p;
72
      }
73
    }
74
  }  // 预处理特征区间答案
75
  memset(CNT, 0, sizeof CNT);
76
  while (m--) {
77
    char opt;
78
    int l, r;
79
    ima = 0;
80
    while (opt = getchar(), opt != 'Q' && opt != 'R');
81
    read(l);
82
    read(r);
83
    if (opt == 'R') {
84
      change[++nc].p = l;
85
      if (!mp[r])
86
        r = mp[r] = ++tot;
87
      else
88
        r = mp[r];
89
      change[nc].col = r;
90
      change[nc].las = c[l];
91
      int p = blnm;
92
      for (; spe[p] >= l; --p)
93
        --cnt[p][c[l]], ++cnt[p][r];  // 修改中间过程的信息
94
      c[l] = r;
95
    } else {
96
      int sl = target[l], sr = target[r];
97
      int SL = sl, SR = sr;
98
      // sl、sr表示所需特征区间的左右端点。
99
      if (sl == sr) {
100
        for (int i = l; i <= r; ++i)
101
          if (++CNT[c[i]] == 1) ++ima;
102
        printf("%d\n", ima);  // 细节：区间左右端点所属特征点相同，暴力计算
103
        for (int i = l; i <= r; ++i) --CNT[c[i]];
104
        // 临时数组还原
105
      } else {
106
        for (int t = nc; t > tim[id[sl]][id[sr]]; --t) {
107
          if (sl <= change[t].p && change[t].p <= sr) {
108
            if (++CNT[change[t].las] + getc(sl, sr, change[t].las) == 1)
109
              --ans[id[sl]][id[sr]];
110
            if (--CNT[change[t].col] + getc(sl, sr, change[t].col) == 0)
111
              ++ans[id[sl]][id[sr]];
112
            // 反向计算答案，即把原来带修莫队的东西反过来写，详情可以参考题解里普通带修莫队的修改方式做对照。
113
          }
114
        }
115
        for (int t = nc; t > tim[id[sl]][id[sr]]; --t)
116
          if (sl <= change[t].p && change[t].p <= sr) {
117
            --CNT[change[t].las];
118
            ++CNT[change[t].col];
119
          }
120
        // 临时数组还原
121
        tim[id[sl]][id[sr]] = nc;
122
        ima = ans[id[sl]][id[sr]];
123
        while (sl < l) del(sl++, SL, SR);
124
        while (sl > l) add(--sl, SL, SR);
125
        while (sr < r) add(++sr, SL, SR);
126
        while (sr > r) del(sr--, SL, SR);
127
        // 可爱的四句莫队
128
        printf("%d\n", ima);
129
        while (SL < l) add(SL++, 0, 0);
130
        while (SL > l) del(--SL, 0, 0);
131
        while (SR < r) del(++SR, 0, 0);
132
        while (SR > r) add(SR--, 0, 0);
133
        // 临时数组还原
134
      }
135
    }
136
  }
137
}

当然上述代码解决的只是P1903 [国家集训队] 数颜色 / 维护队列原问题，只是我们自己强制自己把这道题写成了在线莫队。

实际上一些问题是强制在线的，不像P1903一样可以转化为离线问题，这时在线莫队就显得尤为重要，可以用相对简单的在线莫队解决相对困难的问题，比如树套树，主席树，Fenwike等等需要高级DS的问题。

具体可以看一下这道题U540166 【模板】诗乃莫队

1
enum EventType { QUERY, MODIFY };
2

3
struct Query {
4
  int l, r, t, idx;
5
};
6

7
struct Modification {
8
  int pos;    // 修改位置
9
  int type;   // 1: 修改颜色, 2: 修改数字
10
  int prevC;  // 若是颜色修改，原来的颜色
11
  int nowC;
12
  int prevA;  // 若是数字修改，原来的数字
13
  int nowA;
14
};
15

16
int n, m, k;
17
int initA[NMAX], curA[NMAX];
18
int initC[NMAX], curC[NMAX];  // curC 存储离散化后的颜色
19
vector<int> compColors;
20

21
int totQuery = 0, totMod = 0;
22
vector<Query> queries;
23
vector<Modification> mods;
24

25
ll ansArr[NMAX];
26

27
// 优化：使用 vector 记录每个颜色（离散化后编号）的当前数字和
28
vector<ll> colSumArr;  // 下标范围 [1, totColors]
29

30
ll curAns = 0;
31

32
// 快速计算 f(x) = x^k，其中 k=1,2,3
33
inline ll f(ll x) {
34
  if (k == 1)
35
    return x;
36
  else if (k == 2)
37
    return x * x;
38
  else
39
    return x * x * x;
40
}
41

42
// 内联更新函数：移除位置 pos 的贡献
43
inline void removePos(int pos) {
44
  int color = curC[pos];  // 范围 1..totColors
45
  int val = curA[pos];
46
  ll oldVal = colSumArr[color];
47
  ll newVal = oldVal - val;
48
  curAns -= (f(oldVal) - f(newVal));
49
  colSumArr[color] = newVal;
50
}
51

52
// 内联更新函数：添加位置 pos 的贡献
53
inline void addPos(int pos) {
54
  int color = curC[pos];
55
  int val = curA[pos];
56
  ll oldVal = colSumArr[color];
57
  ll newVal = oldVal + val;
58
  curAns += (f(newVal) - f(oldVal));
59
  colSumArr[color] = newVal;
60
}
61

62
// 应用修改操作 modIdx（如果 pos 在当前区间内，先 remove 后 add）
63
void applyModification(int modIdx, int L, int R) {
64
  Modification &mod = mods[modIdx];
65
  int pos = mod.pos;
66
  if (L <= pos && pos <= R) removePos(pos);
67
  if (mod.type == 1) {
68
    // 颜色修改：curC[pos] 从 prevC 变为 nowC
69
    curC[pos] = mod.nowC;
70
  } else {
71
    curA[pos] = mod.nowA;
72
  }
73
  if (L <= pos && pos <= R) addPos(pos);
74
}
75

76
// 撤销修改操作 modIdx
77
void undoModification(int modIdx, int L, int R) {
78
  Modification &mod = mods[modIdx];
79
  int pos = mod.pos;
80
  if (L <= pos && pos <= R) removePos(pos);
81
  if (mod.type == 1) {
82
    curC[pos] = mod.prevC;
83
  } else {
84
    curA[pos] = mod.prevA;
85
  }
86
  if (L <= pos && pos <= R) addPos(pos);
87
}
88

89
void solve() {
90
  cin >> n >> m >> k;
91
  for (int i = 1; i <= n; i++) {
92
    cin >> initA[i];
93
    curA[i] = initA[i];
94
  }
95
  for (int i = 1; i <= n; i++) {
96
    cin >> initC[i];
97
    compColors.push_back(initC[i]);
98
    curC[i] = initC[i];  // 后续会进行离散化
99
  }
100

101
  ll lastans = 0;
102
  for (int i = 0; i < m; i++) {
103
    char op;
104
    cin >> op;
105
    if (op == 'Q') {
106
      int l, r;
107
      cin >> l >> r;
108
      l ^= lastans;
109
      r ^= lastans;
110
      if (l > r) swap(l, r);
111
      queries.push_back({l, r, (int)totMod, (int)totQuery});
112
      totQuery++;
113
    } else if (op == 'C') {
114
      int x, y;
115
      cin >> x >> y;
116
      x ^= lastans;
117
      y ^= lastans;
118
      compColors.push_back(y);
119
      mods.push_back({x, 1, curC[x], y, 0, 0});
120
      curC[x] = y;
121
      totMod++;
122
    } else {
123
      int x, y;
124
      cin >> x >> y;
125
      x ^= lastans;
126
      y ^= lastans;
127
      mods.push_back({x, 2, 0, 0, curA[x], y});
128
      curA[x] = y;
129
      totMod++;
130
    }
131
  }
132

133
  // 离散化：压缩所有颜色
134
  sort(compColors.begin(), compColors.end());
135
  compColors.erase(unique(compColors.begin(), compColors.end()),
136
                   compColors.end());
137
  int totColors = compColors.size();
138
  auto getColorId = [&](int c) -> int {
139
    return (int)(lower_bound(compColors.begin(), compColors.end(), c) -
140
                 compColors.begin()) +
141
           1;
142
  };
143
  for (int i = 1; i <= n; i++) {
144
    initC[i] = getColorId(initC[i]);
145
    curC[i] = initC[i];
146
  }
147
  for (auto &mod : mods) {
148
    if (mod.type == 1) {
149
      mod.prevC = getColorId(mod.prevC);
150
      mod.nowC = getColorId(mod.nowC);
151
    }
152
  }
153

154
  for (int i = 1; i <= n; i++) {
155
    curA[i] = initA[i];
156
    curC[i] = initC[i];
157
  }
158

159
  // 初始化 colSumArr，所有颜色贡献初始为 0
160
  colSumArr.assign(totColors + 1, 0);
161
  curAns = 0;
162

163
  int blockSize = max((ll)1, (ll)pow(n, 2.0 / 3.0));
164
  sort(queries.begin(), queries.end(), [&](const Query &A, const Query &B) {
165
    int ablock = A.l / blockSize, bblock = B.l / blockSize;
166
    if (ablock != bblock) return ablock < bblock;
167
    int rblockA = A.r / blockSize, rblockB = B.r / blockSize;
168
    if (rblockA != rblockB) return A.r < B.r;
169
    return A.t < B.t;
170
  });
171

172
  // 恢复 curA, curC 为初始状态
173
  for (int i = 1; i <= n; i++) {
174
    curA[i] = initA[i];
175
    curC[i] = initC[i];
176
  }
177
  // colSumArr 已经初始化为 0，curAns = 0
178
  int L = 1, R = 0, curT = 0;
179
  for (auto &q : queries) {
180
    while (curT < q.t) {
181
      applyModification(curT, L, R);
182
      curT++;
183
    }
184
    while (curT > q.t) {
185
      curT--;
186
      undoModification(curT, L, R);
187
    }
188
    while (R < q.r) {
189
      R++;
190
      addPos(R);
191
    }
192
    while (R > q.r) {
193
      removePos(R);
194
      R--;
195
    }
196
    while (L < q.l) {
197
      removePos(L);
198
      L++;
199
    }
200
    while (L > q.l) {
201
      L--;
202
      addPos(L);
203
    }
204
    ansArr[q.idx] = curAns;
205
    lastans = curAns;
206
  }
207

208
  for (int i = 0; i < totQuery; i++) {
209
    cout << ansArr[i] << endl;
210
  }
211
}

二维莫队#

二维莫队解题报告

莫队二次离线#

莫队二次离线