【模板】带修莫队 / [国家集训队] 数颜色 / 维护队列

题意

维护一个颜色序列，支持两类操作：

Q L R：查询 [L,R] 中有多少种不同颜色；
R P C：把位置 P 的颜色改成 C。

思路

朴素做法是按顺序执行操作，查询时扫描整个区间统计颜色。

先看一个可以直接验证想法的朴素解：

cpp

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#include <bits/stdc++.h>
using namespace std;

// brute.cpp：按操作顺序直接修改、直接统计区间不同颜色，只适合小数据。

const int MAXN = 505;
const int MAXV = 1005;

int n, m;
int color[MAXN];
int seen[MAXV];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> color[i];
    }
    for (int i = 1; i <= m; i++) {
        char op;
        int x, y;
        cin >> op >> x >> y;
        if (op == 'Q') {
            for (int c = 0; c < MAXV; c++) {
                seen[c] = 0;
            }
            int answer = 0;
            for (int j = x; j <= y; j++) {
                if (!seen[color[j]]) {
                    seen[color[j]] = 1;
                    answer++;
                }
            }
            cout << answer << '\n';
        } else {
            color[x] = y;
        }
    }

    return 0;
}

有修改操作后，普通莫队只移动左右端点还不够。我们给每个查询多记录一个维度 t：这个查询发生前已经执行了多少次修改。

于是一个查询可以表示为 (l, r, t)。处理它时需要让当前状态满足：

当前区间是 [l,r]；
当前数组已经应用了前 t 次修改。

读入修改时，要记录这次修改的 pos、old_color、new_color。其中 old_color 不能等到处理时再猜，必须在读入阶段用临时数组模拟修改得到。

调整时间时：

时间前进：应用下一次修改；
时间回退：撤销当前最后一次修改；
如果修改位置在当前区间内，就先从答案中删掉旧颜色，再加入新颜色。

当前区间的不同颜色数用 color_count 和 distinct_count 维护。加入一个位置时，如果这个颜色原来次数为 0，不同颜色数加一；删除时如果次数变成 0，不同颜色数减一。

代码

cpp

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154#include <bits/stdc++.h>
using namespace std;

const int MAXN = 133335;
const int MAXV = 1000005;

struct Query {
    int l, r, t, id;
};

struct Change {
    int pos, old_color, new_color;
};

int n, m;
int block_size;
int initial_color[MAXN];
int current_color[MAXN]; // 莫队移动过程中数组当前位置的颜色。
int color_count[MAXV];   // 当前询问区间内每种颜色出现次数。
int distinct_count;
int query_count, change_count;
int answer[MAXN];
Query queries[MAXN];
Change changes[MAXN];

bool cmp_query(const Query &a, const Query &b) {
    int block_l_a = a.l / block_size;
    int block_l_b = b.l / block_size;
    if (block_l_a != block_l_b) {
        return block_l_a < block_l_b;
    }
    int block_r_a = a.r / block_size;
    int block_r_b = b.r / block_size;
    if (block_r_a != block_r_b) {
        return block_r_a < block_r_b;
    }
    return a.t < b.t;
}

void add_pos(int pos) {
    int c = current_color[pos];
    if (color_count[c] == 0) {
        distinct_count++;
    }
    color_count[c]++;
}

void remove_pos(int pos) {
    int c = current_color[pos];
    color_count[c]--;
    if (color_count[c] == 0) {
        distinct_count--;
    }
}

void apply_change(int change_id, int cur_l, int cur_r) {
    int pos = changes[change_id].pos;
    int new_color = changes[change_id].new_color;
    if (cur_l <= pos && pos <= cur_r) {
        remove_pos(pos);
        current_color[pos] = new_color;
        add_pos(pos);
    } else {
        current_color[pos] = new_color;
    }
}

void undo_change(int change_id, int cur_l, int cur_r) {
    int pos = changes[change_id].pos;
    int old_color = changes[change_id].old_color;
    if (cur_l <= pos && pos <= cur_r) {
        remove_pos(pos);
        current_color[pos] = old_color;
        add_pos(pos);
    } else {
        current_color[pos] = old_color;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    int temp_color[MAXN];
    for (int i = 1; i <= n; i++) {
        temp_color[i] = initial_color[i];
    }

    for (int i = 1; i <= m; i++) {
        char op;
        int x, y;
        cin >> op >> x >> y;
        if (op == 'Q') {
            query_count++;
            queries[query_count].l = x;
            queries[query_count].r = y;
            queries[query_count].t = change_count;
            queries[query_count].id = query_count;
        } else {
            change_count++;
            changes[change_count].pos = x;
            changes[change_count].old_color = temp_color[x];
            changes[change_count].new_color = y;
            temp_color[x] = y;
        }
    }

    block_size = max(1, (int)pow(n, 2.0 / 3.0));
    sort(queries + 1, queries + query_count + 1, cmp_query);

    int cur_l = 1, cur_r = 0, cur_t = 0;
    for (int i = 1; i <= query_count; i++) {
        while (cur_l > queries[i].l) {
            cur_l--;
            add_pos(cur_l);
        }
        while (cur_r < queries[i].r) {
            cur_r++;
            add_pos(cur_r);
        }
        while (cur_l < queries[i].l) {
            remove_pos(cur_l);
            cur_l++;
        }
        while (cur_r > queries[i].r) {
            remove_pos(cur_r);
            cur_r--;
        }

        // cur_t 表示当前数组已经应用了前 cur_t 次修改。
        while (cur_t < queries[i].t) {
            cur_t++;
            apply_change(cur_t, cur_l, cur_r);
        }
        while (cur_t > queries[i].t) {
            undo_change(cur_t, cur_l, cur_r);
            cur_t--;
        }

        answer[queries[i].id] = distinct_count;
    }

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

    return 0;
}

复杂度

带修莫队常用块长 $n^{2/3}$ ，总复杂度约为 $O(m \cdot n^{2/3})$ 量级。

空间复杂度 $O(n+m+C)$ ，C 是颜色值范围。

总结

带修莫队比普通莫队多了一个“时间指针”。只要修改能正确前进和回退，区间答案仍然可以像普通莫队一样用 add/remove 维护。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

【模板】带修莫队 / [国家集训队] 数颜色 / 维护队列

目录

题意

思路

代码

复杂度

总结

一图流解析