跳转至

带修莫队

普通莫队无法处理修改操作。于是有了更高时间复杂度的带修莫队。带修莫队可以在 \(O(mn^{\frac 2 3})\) 的时间复杂度内将原问题转化为一个子问题：

  • \(O(1)\) 向序列的开头或结尾插入或删除一个元素；
  • \(O(1)\) 修改序列中的一个数字；
  • \(O(n^{\frac 2 3})\) 以内求出序列答案。

例题

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

题意

你需要维护一个长度为 \(n\) 的颜色序列，支持两种操作：

  • 单点修改；
  • 区间数颜色；

为了处理修改操作，我们引入时间维度。一个查询操作的时间 \(t\) 定义为排在其前面的修改操作的数量。如果两个查询操作的时间不同，则暴力加入或撤销其间的所有修改操作。如果影响了 \([c_l,c_r]\) 中的点，则还需要计量其对答案的贡献。

考虑如何刻画转移的时间复杂度：将每个查询操作视为三维空间中的一个点 \((l,r,t)\)，转移的时间复杂度即为两个点在三维空间中的曼哈顿距离。

考虑对 \(l\) 和 \(r\) 分块，分块大小分别为 \(b_1\) 和 \(b_2\)。总时间复杂度即为

\[ m(b_1+b_2)+\frac{n^2m}{b_1b_2}=m\big((b_1+b_2)+\frac{n^2}{b_1b_2}\big) \]

根据三维均值不等式，可得 \(b_1=b_2=\frac{n^2}{b_1b_2}\) 时复杂度最低，即

\[ \begin{cases} b_1=n^{\frac 2 3}\\ b_2=n^{\frac 2 3} \end{cases} \]

此时时间复杂度为 \(O(mn^{\frac 2 3})\)。

模板代码 
 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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<iostream>
#include<algorithm>
#include<cmath>
#define ll long long
#define ld long double
using namespace std;
const int N = 1.4e5 + 10;
const int V = 1e6 + 10;

int blen, blo[N];
struct Query {
    int l, r, t, id;
    inline bool operator<(const Query& other) const {
        if(blo[l] != blo[other.l]) return (blo[l] < blo[other.l]);
        if(blo[r] != blo[other.r]) return (blo[l] & 1) ? (blo[r] < blo[other.r]) : (blo[r] > blo[other.r]);
        return ((blo[l] + blo[r]) & 1) ? (t < other.t) : (t > other.t);
    }
} q[N];

struct Op {
    int p, v1, v2;
} p[N];

int n, m, t, nq;
int a[N], ta[N], ans[N];

int c_l, c_r, c_t, c_ans;
int cnt[V];

inline void update(int v1, int v2) {
    if(!cnt[v2]) ++c_ans;
    ++cnt[v2];
    --cnt[v1];
    if(!cnt[v1]) --c_ans;
}

void update_t(int tm, int w) {
    if(c_l <= p[tm].p && p[tm].p <= c_r) {
        if(w > 0) update(p[tm].v1, p[tm].v2);
        else update(p[tm].v2, p[tm].v1);
    }
    a[p[tm].p] = (w > 0) ? p[tm].v2 : p[tm].v1;
}

void update_p(int pos, int w) {
    if(!cnt[a[pos]]) ++c_ans;
    cnt[a[pos]] += w;
    if(!cnt[a[pos]]) --c_ans;
}

int main() {

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

    blen = pow((ld)n * n / 2, (ld)1 / 3);
    for(int i = 1; i <= n; i++) {
        blo[i] = (i + blen - 1) / blen;
    }

    for(int i = 1; i <= m; i++) {
        char op;
        int x, y;
        cin >> op >> x >> y;
        if(op == 'R') {
            p[++t] = {x, ta[x], y};
            ta[x] = y;
        } else {
            ++nq;
            q[nq] = {x, y, t, nq};
        }
    }

    sort(q + 1, q + 1 + nq);

    c_l = 1;
    c_r = 0;
    for(int i = 1; i <= nq; i++) {
        int l = q[i].l, r = q[i].r, t = q[i].t;
        while(c_t < t) update_t(++c_t, 1);
        while(c_t > t) update_t(c_t--, -1);
        while(c_r < r) update_p(++c_r, 1);
        while(c_l > l) update_p(--c_l, 1);
        while(c_r > r) update_p(c_r--, -1);
        while(c_l < l) update_p(c_l++, -1);
        ans[q[i].id] = c_ans;
    }

    for(int i = 1; i <= nq; i++) {
        cout << ans[i] << '\n';
    }

    return 0;
}