木板切割

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

用按原始编号分割合并的 Treap 表示木板，并只扫描切下部分与剩余部分中较小的一块来维护颜色频次。

OJ: shumeng

题目 ID: CSP202409E

难度:提高+/省选-

标签:Treap分裂合并启发式合并模拟

日期: 2026-07-31 16:21

形式化题目

初始木板由编号 $1 \sim n$ 的段按顺序组成，每段有一个颜色。 $k$ 次操作：从第 $x$ 号木板中取出原始编号在 $[l, r]$ 内的所有段，按原顺序组成新木板（编号为操作序号 + 1），原木板把剩余段按原顺序重新连接。

每次操作输出新木板的两个值：

不同颜色数；
颜色段数（相邻相同颜色算一段）。

思路

直接保存每块木板的段编号序列并整块扫描是 $O(nk)$ ，需要更高效的结构。

朴素做法：整块扫描

先看直接实现：每块木板保存一个段编号序列，每次操作扫描整块，按编号范围拆成选中段与剩余段，再统计新木板的颜色信息。

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/**
 * 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:21
 * update_at: 2026-08-17 22:39
 */
// brute.cpp：小数据暴力解，直接保存每块木板上的原始段编号，每步扫描整块木板。
#include <bits/stdc++.h>
using namespace std;

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

    int n, m, k;
    cin >> n >> m >> k;
    vector<int> color(n + 1);
    for (int i = 1; i <= n; i++) cin >> color[i];

    vector<vector<int> > board(k + 2); // board[i] 保存第 i 块木板上的段编号序列
    for (int i = 1; i <= n; i++) board[1].push_back(i);
    for (int operation = 1; operation <= k; operation++) {
        int source, left_key, right_key;
        cin >> source >> left_key >> right_key;
        // 扫描整块木板，按编号范围拆成选中段与剩余段
        vector<int> selected;
        vector<int> remaining;
        for (int i = 0; i < (int)board[source].size(); i++) {
            int position = board[source][i];
            if (left_key <= position && position <= right_key) selected.push_back(position);
            else remaining.push_back(position);
        }
        board[source] = remaining;
        board[operation + 1] = selected;

        // 统计新木板的不同颜色数与颜色段数（连续同色计为一段）
        vector<char> appeared(m + 1, 0);
        int distinct = 0;
        int runs = 0;
        int previous_color = -1;
        for (int i = 0; i < (int)selected.size(); i++) {
            int current_color = color[selected[i]];
            if (!appeared[current_color]) {
                appeared[current_color] = 1;
                distinct++;
            }
            if (i == 0 || current_color != previous_color) runs++;
            previous_color = current_color;
        }
        cout << distinct << ' ' << runs << '\n';
    }
    return 0;
}

做法完全符合题意，但每步 $O(\text{木板大小})$ ，最坏 $O(nk)$ 。

主解：用 Treap 表示木板

所有段的相对顺序始终与原始编号一致，因此每块木板可以表示成“按键为原始编号”的 Treap，只需要保存一个根节点。一次切割就是两次按键分裂：

text

1板 x = [编号 < l] + [l..r] + [编号 > r]

中间根就是新木板，首尾两部分合并后仍是原木板。Treap 节点维护子树大小、首尾颜色和颜色段数，于是新木板的颜色段数可以在根节点 $O(1)$ 读取。

小块扫描维护不同颜色数

不同颜色数不能只用边界信息维护，需要为每块木板保存一张 <颜色, 出现次数> 频率表。一次切割后，切下部分和剩余部分构成原木板的划分：只扫描两者中较小的一块，建立它的频率表；原木板原有的频率表转移给较大的一块并扣除小块频次，另一块使用扫描得到的新表。

摊还关键：一个段只要被扫描一次，它所在的新木板大小就至多变成原来的一半，因此每个段总共被扫描 $O(\log n)$ 次。

代码

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/**
 * 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:21
 * update_at: 2026-08-17 22:39
 */
#include <bits/stdc++.h>
using namespace std;

struct SequenceNode {
    int left, right;
    int priority;
    int key, color;
    int size;
    int first_color, last_color;
    int run_count;
};

vector<SequenceNode> sequence_tree;

int sequence_size(int root) {
    return root == 0 ? 0 : sequence_tree[root].size;
}

void pull_sequence(int root) {
    if (root == 0) return;
    SequenceNode &node = sequence_tree[root];
    node.size = sequence_size(node.left) + sequence_size(node.right) + 1;
    node.first_color = node.left == 0 ? node.color : sequence_tree[node.left].first_color;
    node.last_color = node.right == 0 ? node.color : sequence_tree[node.right].last_color;
    node.run_count = sequence_tree[node.left].run_count + 1 + sequence_tree[node.right].run_count;
    if (node.left != 0 && sequence_tree[node.left].last_color == node.color) node.run_count--;
    if (node.right != 0 && node.color == sequence_tree[node.right].first_color) node.run_count--;
}

int merge_sequence(int left_root, int right_root) {
    if (left_root == 0) return right_root;
    if (right_root == 0) return left_root;
    if (sequence_tree[left_root].priority > sequence_tree[right_root].priority) {
        sequence_tree[left_root].right = merge_sequence(sequence_tree[left_root].right, right_root);
        pull_sequence(left_root);
        return left_root;
    }
    sequence_tree[right_root].left = merge_sequence(left_root, sequence_tree[right_root].left);
    pull_sequence(right_root);
    return right_root;
}

void split_sequence(int root, int key, int &left_root, int &right_root) {
    if (root == 0) {
        left_root = 0;
        right_root = 0;
        return;
    }
    if (sequence_tree[root].key <= key) {
        left_root = root;
        split_sequence(sequence_tree[root].right, key, sequence_tree[root].right, right_root);
        pull_sequence(left_root);
    } else {
        right_root = root;
        split_sequence(sequence_tree[root].left, key, left_root, sequence_tree[root].left);
        pull_sequence(right_root);
    }
}

void collect_colors(int root, unordered_map<int, int> &count) {
    if (root == 0) return;
    collect_colors(sequence_tree[root].left, count);
    count[sequence_tree[root].color]++;
    collect_colors(sequence_tree[root].right, count);
}

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

    int n, m, k;
    cin >> n >> m >> k;
    vector<int> color(n + 1);
    for (int i = 1; i <= n; i++) cin >> color[i];

    sequence_tree.assign(n + 1, SequenceNode());
    mt19937 random_engine(712367821);
    int initial_root = 0;
    for (int i = 1; i <= n; i++) {
        sequence_tree[i].left = 0;
        sequence_tree[i].right = 0;
        sequence_tree[i].priority = (int)random_engine();
        sequence_tree[i].key = i;
        sequence_tree[i].color = color[i];
        sequence_tree[i].size = 1;
        sequence_tree[i].first_color = color[i];
        sequence_tree[i].last_color = color[i];
        sequence_tree[i].run_count = 1;
        initial_root = merge_sequence(initial_root, i);
    }

    vector<int> board_root(k + 2, 0);
    vector<unique_ptr<unordered_map<int, int> > > board_colors(k + 2);
    board_root[1] = initial_root;
    board_colors[1].reset(new unordered_map<int, int>());
    board_colors[1]->reserve(n * 2 + 1);
    for (int i = 1; i <= n; i++) (*board_colors[1])[color[i]]++;

    for (int operation = 1; operation <= k; operation++) {
        int source_board, left_key, right_key;
        cin >> source_board >> left_key >> right_key;

        int left_root, middle_root, right_root;
        int temporary_root;
        split_sequence(board_root[source_board], left_key - 1, left_root, temporary_root);
        split_sequence(temporary_root, right_key, middle_root, right_root);
        int remaining_root = merge_sequence(left_root, right_root);
        int middle_size = sequence_size(middle_root);
        int remaining_size = sequence_size(remaining_root);

        int small_size = min(middle_size, remaining_size);
        unique_ptr<unordered_map<int, int> > small_colors(new unordered_map<int, int>());
        small_colors->reserve(small_size * 2 + 1);
        if (middle_size <= remaining_size) collect_colors(middle_root, *small_colors);
        else collect_colors(remaining_root, *small_colors);

        unique_ptr<unordered_map<int, int> > old_colors = move(board_colors[source_board]);
        unordered_map<int, int>::iterator iterator = small_colors->begin();
        while (iterator != small_colors->end()) {
            unordered_map<int, int>::iterator old_iterator = old_colors->find(iterator->first);
            old_iterator->second -= iterator->second;
            if (old_iterator->second == 0) old_colors->erase(old_iterator);
            ++iterator;
        }

        if (middle_size <= remaining_size) {
            board_root[source_board] = remaining_root;
            board_root[operation + 1] = middle_root;
            board_colors[source_board] = move(old_colors);
            board_colors[operation + 1] = move(small_colors);
        } else {
            board_root[source_board] = remaining_root;
            board_root[operation + 1] = middle_root;
            board_colors[source_board] = move(small_colors);
            board_colors[operation + 1] = move(old_colors);
        }

        if (middle_root == 0) cout << "0 0\n";
        else cout << board_colors[operation + 1]->size() << ' '
                  << sequence_tree[middle_root].run_count << '\n';
    }
    return 0;
}

复杂度

设段数 $n$ 、操作数 $k$ 。

时间：Treap 分裂、合并期望 $O(\log n)$ ；小块扫描的总长度 $S = O(n \log n)$ ，总时间复杂度期望 $O((n + k) \log n)$ 。
空间：频率表有效条目 $O(n)$ ，考虑哈希桶转移后保留的容量，记为 $O(n \log n + k)$ 。

总结

把“按原始编号取出一段”转化为 Treap 的按键分裂，再用小块扫描 + 大块频率表转移维护不同颜色数。颜色段数由序列聚合信息直接维护，整体避免了反复扫描大木板，是“序列分裂合并 + 启发式维护统计信息”的典型结合。

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

时间限制： 1.0 秒

空间限制： 512 MB

题目描述

你有一块长度为 $n$ 的木板和 $m$ 种颜色，木板被平均分成 $n$ 段，分别编号为 $1, 2, \cdots, n$ 。第 $i$ 段被染为颜色 $c_i$ 。这块木板为 $1$ 号木板。

你要进行 $k$ 次切割操作，第 $i~(1 \le i \le k)$ 次切割操作有三个参数 $x_i, l_i, r_i$ ：

表示将 $x_i$ 号木板中编号在 $[l_i, r_i]$ 之间的所有段切割下来，作为第 $i + 1$ 号木板；
原先木板切割剩下的部分重新连接成一块木板，木板编号仍为 $x_i$ ；
每一段的编号不受切割操作影响；
特别的，木板长度可以为 $0$ ，即切下的木板不包含任一段。

你想要知道，每次切割操作切下的木板：

包含多少种不同的颜色？
包含多少个颜色段？

一个颜色段定义为：一块木板上极长的连续若干段，满足这些段具有相同的颜色。若切下的木板长度为 $0$ ，则不同颜色数和颜色段数都视为 $0$ 。

输入格式

从标准输入读入数据。

输入共 $k+2$ 行。

第一行包含三个正整数 $n, m, k$ 。

第二行包含 $n$ 个正整数 $c_1, c_2, \cdots, c_n$ ，表示木板上每一段的颜色。

接下来共有 $k$ 行，每行三个整数 $x_i, l_i, r_i$ ，表示一次切割操作。

输出格式

输出到标准输出。

共 $k$ 行，第 $i$ 行两个正整数分别表示第 $i$ 次切下的木板中不同颜色数和颜色段数。

input1

1
2
3
4
5
6
76 3 5
1 2 2 3 1 2
1 3 4
1 5 5
1 4 5
1 1 6
2 4 4

output1

样例 1 解释

初始 $1$ 号木板包含段 $(1,2,3,4,5,6)$ ，颜色序列为 $(1,2,2,3,1,2)$ 。

第一次切割操作，切下 $1$ 号木板上段落编号在 $[3,4]$ 的部分，作为 $2$ 号木板：

$2$ 号木板包含段 $(3,4)$ ，其颜色序列为 $(2,3)$ ；
$1$ 号木板剩余段 $(1,2,5,6)$ ，其颜色序列为 $(1,2,1,2)$ 。

第二次切割操作，切下 $1$ 号木板上段落编号在 $[5,5]$ 的部分，作为 $3$ 号木板：

$3$ 号木板包含段 $(5)$ ，其颜色序列为 $(1)$ ；
$1$ 号木板剩余段 $(1,2,6)$ ，其颜色序列为 $(1,2,2)$ 。

第三次切割操作，切下 $1$ 号木板上段落编号在 $[4,5]$ 的部分，作为 $4$ 号木板：

因为 $1$ 号木板上已经不含段 $4$ 和 $5$ ，新切下的 $4$ 号木板为空；

第四次切割操作，切下 $1$ 号木板上段落编号在 $[1,6]$ 的部分，作为 $5$ 号木板：

$5$ 号木板包含段 $(1,2,6)$ ，其颜色序列为 $(1,2,2)$ ；
$1$ 号木板剩余部分为空。

第五次切割操作，切下 $2$ 号木板上段落编号在 $[4,4]$ 的部分，作为 $6$ 号木板：

$6$ 号木板包含段 $(4)$ ，其颜色序列为 $(3)$ ；
$2$ 号木板剩余段 $(3)$ ，其颜色序列为 $(2)$ 。

子任务

全部的数据满足：

$1 \le n, m, k \le 10^{5}$ ；
$1 \le c_i \le m$ ；
$1 \le l_i \le r_i \le n$ ；
$1 \le x_i \le i$ 。

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

子任务编号	分值	$n,m,k\le$	特殊性质
1	25	$2000$	无
2	10	$10^5$	A
3	15	$10^5$	B
4	15	$10^5$	C
5	35	$10^5$	无

特殊性质 A： $r_i - l_i \le 1000$ ；
特殊性质 B： $c_i = i$ ；
特殊性质 C：对于所有的 $1 \le i < j \le n$ 满足 $c_i \le c_j$ 。

木板切割

目录

形式化题目

思路

朴素做法：整块扫描

主解：用 Treap 表示木板

小块扫描维护不同颜色数

代码

复杂度

总结