数据抢修

GitHub跳转原题关系图 Canvas 关系图返回列表

在二进制 Trie 上递归计算异或阈值冲突图的最大团，并缓存跨子 Trie 状态支持合并。

OJ: shumeng

题目 ID: CSP202512E

难度:提高+/省选-

标签:Trie二分图动态合并

日期: 2026-07-31 16:22

形式化题目

每个数据包是可重集。若两元素权值 $x,y$ 满足 $x \oplus y < W$ ，则它们不能放在同一个稳定子包中。一个数据包的维修代价是能将其划分成稳定子包的最小数量。维护多个数据包，支持插入元素、合并数据包、查询所有激活数据包维修代价之和。

思路

先看朴素做法：把元素建成冲突图并回溯染色，验证答案的含义。

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:22
 * update_at: 2026-08-17 23:10
 */
// brute.cpp：把元素建成冲突图，回溯求最少染色数，适合小数据验证。
#include <bits/stdc++.h>
using namespace std;

int element_count;
int best_color;
vector<int> order_vertices;
vector<int> vertex_color;
vector<int> conflict_mask;
vector<int> vertex_degree;

bool degree_compare(int x, int y) {
    return vertex_degree[x] > vertex_degree[y];
}

void color_dfs(int position, int used_color) {
    if (used_color >= best_color) {
        return;
    }
    if (position == element_count) {
        best_color = used_color;
        return;
    }
    int u = order_vertices[position];
    int forbidden = 0;
    for (int i = 0; i < position; i++) {
        int v = order_vertices[i];
        if ((conflict_mask[u] >> v) & 1) {
            forbidden |= 1 << vertex_color[v];
        }
    }
    for (int color = 0; color < used_color; color++) {
        if (((forbidden >> color) & 1) == 0) {
            vertex_color[u] = color;
            color_dfs(position + 1, used_color);
        }
    }
    vertex_color[u] = used_color;
    color_dfs(position + 1, used_color + 1);
    vertex_color[u] = -1;
}

int repair_cost(const vector<int> &values, int w) {
    element_count = (int)values.size();
    if (element_count == 0) {
        return 0;
    }
    if (w >= (1 << 30)) {
        return element_count;
    }
    conflict_mask.assign(element_count, 0);
    vertex_degree.assign(element_count, 0);
    for (int i = 0; i < element_count; i++) {
        for (int j = 0; j < i; j++) {
            if ((values[i] ^ values[j]) < w) {
                conflict_mask[i] |= 1 << j;
                conflict_mask[j] |= 1 << i;
                vertex_degree[i]++;
                vertex_degree[j]++;
            }
        }
    }
    order_vertices.resize(element_count);
    for (int i = 0; i < element_count; i++) {
        order_vertices[i] = i;
    }
    sort(order_vertices.begin(), order_vertices.end(), degree_compare);
    vertex_color.assign(element_count, -1);
    best_color = element_count;
    color_dfs(0, 0);
    return best_color;
}

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

    int n, w;
    cin >> n >> w;
    vector<vector<int> > packets(n + 1);
    for (int i = 1; i <= n; i++) {
        int count;
        cin >> count;
        packets[i].resize(count);
        for (int j = 0; j < count; j++) {
            cin >> packets[i][j];
        }
    }
    int q;
    cin >> q;
    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int u, x;
            cin >> u >> x;
            packets[u].push_back(x);
        } else if (type == 2) {
            int u, v;
            cin >> u >> v;
            packets[u].insert(packets[u].end(),
                              packets[v].begin(), packets[v].end());
            packets[v].clear();
        } else {
            long long answer = 0;
            for (int i = 1; i <= n; i++) {
                answer += repair_cost(packets[i], w);
            }
            cout << answer << '\n';
        }
    }
    return 0;
}

转成图论模型

把每个元素看成顶点，异或值小于 $W$ 的两顶点连边。稳定子包就是冲突图的独立集，维修代价等于最小染色数。这个异或阈值图具有按最高位递归的完美图结构，最小染色数恰好等于最大团大小。

在 Trie 上递归求最大团

设 $h$ 为 $W$ 的最高位。高于 $h$ 的位一旦不同，异或值至少为 $2^{h+1} \ge W$ ，不会冲突，所以最大团只能来自同一个高位前缀。在第 $h$ 位时，同侧元素两两冲突；若同时选左右两侧，就要递归检查低位限制 $W - 2^h$ 。

定义 cross(u, v, b, L) 为从两棵低位 Trie 中选取元素，使任意跨侧异或小于 $L$ 时能选出的最大总数：

$L=0$ ：只能选一侧，答案为 $\max(cnt(u), cnt(v))$ ；
$L$ 当前位为 0：只能递归同位分支，取最大值；
$L$ 当前位为 1：两个反向分支互不影响，答案是两者之和。

动态维护

每个跨子树状态用节点版本号缓存，避免重复计算。合并数据包时启发式合并两棵 Trie 并刷新受影响的 best；插入只沿一条路径更新。根节点的 best 就是该数据包的维修代价。

代码

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
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:22
 * update_at: 2026-08-17 23:10
 */
#include <bits/stdc++.h>
using namespace std;

const int MAX_VALUE_BIT = 29;          // 值域 [0,10^9] 的二进制最高位
const int MAX_TOTAL_ELEMENT = 500000;  // 所有数据包元素总数上限
const int MAX_TRIE_NODE = MAX_TOTAL_ELEMENT * (MAX_VALUE_BIT + 1) + 5;

struct TrieNode {
    int child[2]; // 0/1 两个子节点下标
    int count;    // 子树内元素个数
    int best;     // 该子树对应冲突图的最大团大小（即该子树的维修代价）
    int version;  // 版本号，用于判断跨子树缓存是否过期
};

struct CrossCache {
    int version_left;  // 左子树版本
    int version_right; // 右子树版本
    int value;         // 缓存的跨子树结果
};

int n;
long long threshold_w;   // 稳定阈值 W
int highest_bit;         // W 的最高位所在位置
int low_threshold;       // W 去掉最高位后的低位部分
bool all_pairs_conflict; // W >= 2^30 时任意两元素异或都小于 W，全部互斥
TrieNode trie[MAX_TRIE_NODE];
int trie_nodes;
unordered_map<unsigned long long, CrossCache> cross_cache; // 跨子树状态缓存

// 两个节点下标拼成一个 key，用于跨子树缓存
unsigned long long pair_key(int x, int y) {
    if (x > y) {
        swap(x, y);
    }
    return (unsigned long long)(unsigned int)x << 32
           | (unsigned int)y;
}

int get_count(int u) {
    return u == 0 ? 0 : trie[u].count;
}

int new_node() {
    trie_nodes++;
    trie[trie_nodes].child[0] = 0;
    trie[trie_nodes].child[1] = 0;
    trie[trie_nodes].count = 0;
    trie[trie_nodes].best = 0;
    trie[trie_nodes].version = 0;
    return trie_nodes;
}

// 从两个低位 Trie 中选取元素，使任意跨侧异或小于 limit 时能选出的最大总数。
// 这是冲突图最大团的递归计算核心
int cross_value(int left, int right, int bit, int limit) {
    if (left == 0 && right == 0) {
        return 0;
    }
    if (left == 0) {
        return get_count(right);
    }
    if (right == 0) {
        return get_count(left);
    }
    if (limit == 0) {
        return max(get_count(left), get_count(right));
    }
    if (bit < 0) {
        return get_count(left) + get_count(right);
    }

    // 用版本号判断缓存是否仍有效
    unsigned long long key = pair_key(left, right);
    unordered_map<unsigned long long, CrossCache>::iterator it;
    it = cross_cache.find(key);
    if (it != cross_cache.end()
        && it->second.version_left == trie[left].version
        && it->second.version_right == trie[right].version) {
        return it->second.value;
    }

    int result;
    if (((limit >> bit) & 1) == 0) {
        // 低位限制的当前位为 0：只能选同一位分支，取最大值
        int same_zero = cross_value(trie[left].child[0],
                                    trie[right].child[0], bit - 1, limit);
        int same_one = cross_value(trie[left].child[1],
                                   trie[right].child[1], bit - 1, limit);
        result = max(max(get_count(left), get_count(right)),
                     max(same_zero, same_one));
    } else {
        // 当前位为 1：两个反向分支互不影响，可以同时选
        int lower_limit = limit ^ (1 << bit);
        int different_zero = cross_value(trie[left].child[0],
                                         trie[right].child[1],
                                         bit - 1, lower_limit);
        int different_one = cross_value(trie[left].child[1],
                                        trie[right].child[0],
                                        bit - 1, lower_limit);
        result = different_zero + different_one;
    }

    CrossCache cache;
    cache.version_left = trie[left].version;
    cache.version_right = trie[right].version;
    cache.value = result;
    cross_cache[key] = cache;
    return result;
}

// 重新计算节点 u 的 best：看左右子树的单侧最大团与跨侧最大团
void update_best(int u, int bit) {
    if (bit > highest_bit) {
        trie[u].best = max(trie[trie[u].child[0]].best,
                           trie[trie[u].child[1]].best);
    } else if (bit == highest_bit) {
        int left_count = get_count(trie[u].child[0]);
        int right_count = get_count(trie[u].child[1]);
        int cross = cross_value(trie[u].child[0], trie[u].child[1],
                                highest_bit - 1, low_threshold);
        trie[u].best = max(max(left_count, right_count), cross);
    }
}

// 向 Trie 插入一个值，沿路径更新计数并刷新各节点的 best
void insert_value(int &u, int bit, int value) {
    if (u == 0) {
        u = new_node();
    }
    trie[u].count++;
    trie[u].version++;
    if (bit < 0) {
        return;
    }
    int direction = (value >> bit) & 1;
    insert_value(trie[u].child[direction], bit - 1, value);
    update_best(u, bit);
}

// 合并两棵 Trie（按大小启发式），返回合并后的根
int merge_trie(int left, int right, int bit) {
    if (left == 0) {
        return right;
    }
    if (right == 0) {
        return left;
    }
    if (trie[left].count < trie[right].count) {
        swap(left, right);
    }
    trie[left].count += trie[right].count;
    trie[left].version++;
    if (bit >= 0) {
        trie[left].child[0] = merge_trie(trie[left].child[0],
                                          trie[right].child[0], bit - 1);
        trie[left].child[1] = merge_trie(trie[left].child[1],
                                          trie[right].child[1], bit - 1);
        update_best(left, bit);
    }
    return left;
}

int packet_cost(int root) {
    if (root == 0) {
        return 0;
    }
    if (all_pairs_conflict) {
        return trie[root].count;
    }
    return trie[root].best;
}

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

    cin >> n >> threshold_w;
    highest_bit = 0;
    long long temp_w = threshold_w;
    while (temp_w > 1) {
        temp_w >>= 1;
        highest_bit++;
    }
    all_pairs_conflict = threshold_w >= (1LL << 30);
    if (all_pairs_conflict) {
        highest_bit = MAX_VALUE_BIT;
        low_threshold = 0;
    } else {
        low_threshold = (int)(threshold_w - (1LL << highest_bit));
    }
    cross_cache.reserve(1 << 20);

    vector<int> packet_root(n + 1, 0);
    vector<int> packet_size(n + 1, 0);
    long long total_cost = 0;
    for (int i = 1; i <= n; i++) {
        int count;
        cin >> count;
        packet_size[i] = count;
        for (int j = 0; j < count; j++) {
            int value;
            cin >> value;
            insert_value(packet_root[i], MAX_VALUE_BIT, value);
        }
        total_cost += packet_cost(packet_root[i]);
    }

    int q;
    cin >> q;
    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int u, value;
            cin >> u >> value;
            total_cost -= packet_cost(packet_root[u]);
            insert_value(packet_root[u], MAX_VALUE_BIT, value);
            packet_size[u]++;
            total_cost += packet_cost(packet_root[u]);
        } else if (type == 2) {
            int u, v;
            cin >> u >> v;
            total_cost -= packet_cost(packet_root[u]);
            total_cost -= packet_cost(packet_root[v]);
            packet_root[u] = merge_trie(packet_root[u], packet_root[v],
                                        MAX_VALUE_BIT);
            packet_size[u] += packet_size[v];
            packet_root[v] = 0;
            packet_size[v] = 0;
            total_cost += packet_cost(packet_root[u]);
        } else {
            cout << total_cost << '\n';
        }
    }
    return 0;
}

复杂度

Trie 深度为 $B \le 30$ 。插入沿一条路径更新 $O(B)$ ；合并访问较小 Trie 的节点，配合缓存均摊 $O(nB)$ ；空间复杂度为 Trie 节点与访问过的跨状态数量。

总结

异或阈值关系不是普通数值区间，但它在二进制最高位上具有清晰的递归结构。把分组问题转成冲突图染色，再利用完美图性质把最大团递归落实到 Trie，就能同时高效处理插入与数据包合并。

题目来自第 40 次 CSP 认证 T5，评测使用自造高质量复刻数据。我们承认原始题面与大样例版权均归中国计算机学会（CCF）所有，因此题面与评测服务均免费对外开放。如果您认为我们侵犯了您的权益，可联系我们。

时间限制： 3.0 秒

空间限制： 1024 MB

题目背景

由小 C 和小 F 开发的 CrazyFry 服务突然出现了故障，这导致了诸多平台的访问受到影响，现在他们正在紧急抢修。

题目描述

CrazyFry 目前有 $n$ 个数据包，每个数据包初始包含一些元素，也可能为空，每个元素有一个权值。数据包编号为 $1\sim n$ ，默认为激活状态。同一个数据包允许出现权值相同的元素，即数据包可以看做一个可重集。

小 C 为 CrazyFry 设定了一个稳定值 $W$ 。一个 CrazyFry 数据包是稳定的当且仅当其中任意两个元素的权值 $x, y$ 均满足 $x\oplus y\ge W$ 。其中 $\oplus$ 表示按位异或运算。显然，只有一个元素的数据包一定是稳定的。

将一个数据包划分为若干子数据包，使得每个元素恰好出现在其中一个子数据包，且每个子数据包都是稳定的，我们称这样的划分方式是稳定的。一个稳定的划分方式所划分出的子数据包数量的最小值为该数据包的维修代价。CrazyFry 的维修代价为目前所有处于激活状态的数据包的维修代价的总和。

现在小 F 要对 CrazyFry 进行测试，他会进行 $q$ 次操作：

$1\ u\ x$ ：在编号为 $u$ 的数据包中添加一个权值为 $x$ 的元素，保证 $u$ 目前处于激活状态。
$2\ u\ v$ ：将编号为 $v$ 的数据包合并到编号为 $u$ 的数据包里，保证 $u\ne v$ 且 $u, v$ 均处于激活状态，此后 $v$ 处于离线状态，并且不会出现在之后操作中。
$3$ ：查询操作，询问目前 CrazyFry 的维修代价。

输入格式

从标准输入读入数据。

第一行读入一个正整数 $n$ 和一个正整数 $W$ 。

接下来 $n$ 行，第 $i$ 行首先读入一个非负整数 $m_i$ ，表示编号为 $i$ 的数据包的初始元素个数，随后读入 $m_i$ 个非负整数，表示数据包中元素的权值。

下一行读入一个正整数 $q$ ，表示操作个数。

接下来 $q$ 行，每行先读入一个正整数 $op$ ：

若 $op = 1$ ，表示进行 $1$ 操作，接下来读入两个整数 $u, x$ 。
若 $op = 2$ ，表示进行 $2$ 操作，接下来读入两个整数 $u, v$ 。
若 $op = 3$ ，表示进行 $3$ 操作。

操作含义同上文描述。

输出格式

输出到标准输出。

对于每一个查询操作，输出一行一个整数，表示 CrazyFry 的维修代价。

input1

output1

样例 1 解释

任意两个元素的权值异或都小于 $W$ ，故每个元素必须单独放在一个子数据包里，答案始终为 $3$ 。

input2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
165 15
7 4 7 8 13 13 0 11 
1 11 
9 9 4 19 0 11 9 5 9 8 
2 9 16 
4 10 17 12 1 
9
1 3 10
1 5 19
2 1 4
1 2 16
3
1 2 18
1 5 11
3
2 5 2

output2

1
217
19

input3

output3

样例 3 解释

$7\oplus 5\ge 2$ ，故 ${7, 5}$ 可以放入一个子数据包里，答案为 $1$ 。

子任务

全部测试数据满足： $1\le n, q, \sum\limits_{i = 1}^n m_i \le 5\times 10^5$ ，所有权值值域为 $[0, 10^9]$ 且 $W > 0$ 。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

子任务编号	分值	$n,q,\sum\limits_{i = 1}^n m_i\le $	权值值域上限
1	20	$10$	$10^3$
2	15	$100$	$10^3$
3	15	$10^3$	$10^6$
4	20	$10^5$	$10^6$
5	30	$5\times 10^5$	$10^9$

数据抢修

目录

形式化题目

思路

转成图论模型

在 Trie 上递归求最大团

动态维护

代码

复杂度

总结