概述

我们给莫队算法（详见「算法笔记」莫队算法）增加一条时间轴，就可以使其能够实现单点修改操作。

实现

思路

我们在修改后，显然是会对答案产生影响的，那么我们要把修改操作和查询操作都离线下来，并在记录查询操作时，增加一个变量记录本次询问之前最近的修改操作，记为 $t​$。

在核心代码中，我们记录 $L,R,T$ 三个指针，其中 $T$ 指针表示已经完成了前 $T$ 个修改操作。如果当前修改的次数比本次查询需要的修改的少，那么我们就修改下去；反之如果多了就改回来。

当然要注意：在修改或撤回时，只有修改的点在区间内时才能更新答案！

排序

毕竟莫队算法被称为优雅的暴力，那么我们无非就是改变了排序的方式，然后继续暴力！

我们这一次也是把询问分成若干块，排序的方法是：第一关键字为左端点所在块，第二关键字为右端点所在块，第三关键字为时间（这里的时间就是 $t​$）。

分块

对于带修改莫队，显然不能再按照原来的 $\sqrt n$ 或者 $\frac{n}{\sqrt m}$ 分块了。我们考虑把块的大小设为 $x$ 则有 $\frac{n}{x}$ 个块，那么有：

• 左端点

  1. 相同块：每次最多移动 $\mathcal O(x)$ 的距离，总复杂度为 $\mathcal O(mx)​$。
  2. 跨越块：每次最多移动 $\mathcal O(x)$ 的距离，总复杂度为 $\mathcal O(n)​$。

• 右端点

  1. 左端点所在块不变：每次移动 $\mathcal O(x)$，一共有 $\mathcal O(m)$ 次移动则复杂度为 $\mathcal O(mx)$。
  2. 左端点所在块改变：每次移动 $\mathcal O(n)$，一共有 $\mathcal O(\frac{n}{x})$ 次改变则总复杂度为 $\mathcal O(\frac{n^2}{x})$

• 时间轴

  1. 左右端点所在块不变：单调向右移动，复杂度为 $\mathcal O(m)​$。
  2. 左右端点所在块改变：每次最多移动 $\mathcal O(m)​$ 的距离。

  只需要知道最坏情况下有多少个 $t$ 的单调块。显然最多有 $\left(\frac{n}{x}\right)^2$ 个，那么总复杂度为 $\mathcal O\left(m(\frac{n}{x})^2\right)$。

我们总和起来得到复杂度 $\mathcal O\left(n+mx+\frac{n^2}{x}+m(\frac{n}{x})^2\right)$。当 $x=\sqrt[3]{nm}$ 时这个复杂度较小，为 $\mathcal O\left(\sqrt[3]{nm^4}+\sqrt[3]{n^4m}\right)$。

一般来说 $n$ 和 $m$ 同阶，块的大小取 $\mathcal O(n^{\frac{2}{3}})$，总复杂度为 $\mathcal O(n^{\frac{5}{3}})​$。

代码

我们就以「BZOJ 2120」数颜色 为例吧。

#include <cstdio>
#include <cmath>
#include <algorithm>

const int N = 5e4 + 5, M = 1e6 + 5;

int n, m, cnt1, cnt2, ret, a[N], b[N], bl[N], cnt[M], ans[N];

struct Data1 {
    int l, r, t, id;
    Data1(int _l = 0, int _r = 0, int _t = 0, int _id = 0) {
        l = _l, r = _r, t = _t, id = _id;
    }
    bool operator<(const Data1 &b) const {
        return bl[l] == bl[b.l] ? bl[r] == bl[b.r] ? t < b.t : r < b.r : l < b.l;
    }
} q[N];

struct Data2 {
    int x, u, v;
    Data2(int _x = 0, int _u = 0, int _v = 0) {
        x = _x, u = _u, v = _v;
    }
} r[N];

void add(int c) {
    if (++cnt[c] == 1) ret++;
}
void del(int c) {
    if (--cnt[c] == 0) ret--;
}
void modify(int l, int r, int x, int c) {
    if (l <= x && x <= r) del(a[x]), add(c);
    a[x] = c;
}
int main() {
    scanf("%d%d", &n, &m);
    int len = pow(n, 2.0 / 3);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        b[i] = a[i];
        bl[i] = (i - 1) / len + 1;
    }
    for (int i = 1; i <= m; i++) {
        char s[5];
        int x, y;
        scanf("%s%d%d", s, &x, &y);
        if (s[0] == 'Q') {
            cnt1++, q[cnt1] = Data1(x, y, cnt2, cnt1);
        } else {
            r[++cnt2] = Data2(x, b[x], y), b[x] = y;
        }
    }
    std::sort(q + 1, q + cnt1 + 1);
    for (int L = 1, R = 0, T = 0, i = 1; i <= cnt1; i++) {
        int x = q[i].l, y = q[i].r, t = q[i].t;
        while (T < t) T++, modify(L, R, r[T].x, r[T].v);
        while (T > t) modify(L, R, r[T].x, r[T].u), T--;
        while (L < x) del(a[L++]);
        while (L > x) add(a[--L]);
        while (R < y) add(a[++R]);
        while (R > y) del(a[R--]);
        ans[q[i].id] = ret;
    }
    for (int i = 1; i <= cnt1; i++) {
        printf("%d\n", ans[i]);
    }
    return 0;
}