[Aya Round 1 H] 破碎的历史

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

一次染色只能填补两个已黑点之间的空隙，因此答案等价于：两端点初始为黑，且每段初始白色空隙都被至少一个活跃操作跨过。

OJ: luogu

题目 ID: P8473

难度:提高+/省选-

标签:线段树二分区间覆盖建模思维

日期: 2026-06-21 02:30

题意

数轴上有 n 个特殊点，每个点初始是黑色或白色。

还维护一个当前活跃的线段集合 S。

两类操作：

1 l r：把所有端点都在 [l, r] 内的特殊点线段加入 S
2 x：撤销第 x 次操作加入的所有线段

在初始时和每次操作后，判断是否存在一种合法顺序，使得可以把所有特殊点都染成黑色。

一次合法染色要求：

选 S 中一条线段
其两个端点对应的特殊点都已经是黑色
然后把线段内部所有白色特殊点染黑

思路

先看一个最直接的暴力闭包：

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

// brute.cpp：直接维护当前活跃线段集合，然后暴力模拟染色闭包。

const int MAXN = 105;
const int MAXQ = 105;

int n, q;
int pos_arr[MAXN];
int color_arr[MAXN];
int add_l[MAXQ], add_r[MAXQ];
int add_ok[MAXQ];
int cnt_seg[MAXN][MAXN];

bool simulate() {
    int black[MAXN];
    for (int i = 1; i <= n; i++) {
        black[i] = color_arr[i];
    }

    int changed = 1;
    while (changed) {
        changed = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = i; j <= n; j++) {
                if (cnt_seg[i][j] == 0) {
                    continue;
                }
                if (black[i] == 0 || black[j] == 0) {
                    continue;
                }
                for (int k = i; k <= j; k++) {
                    if (black[k] == 0) {
                        black[k] = 1;
                        changed = 1;
                    }
                }
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        if (black[i] == 0) {
            return false;
        }
    }
    return true;
}

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

    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> pos_arr[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> color_arr[i];
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cnt_seg[i][j] = 0;
        }
    }

    cout << (simulate() ? "Yes" : "No") << '\n';

    for (int i = 1; i <= q; i++) {
        int op;
        cin >> op;
        add_ok[i] = 0;

        if (op == 1) {
            int l, r;
            cin >> l >> r;

            int L = lower_bound(pos_arr + 1, pos_arr + n + 1, l) - pos_arr;
            int R = (int)(upper_bound(pos_arr + 1, pos_arr + n + 1, r) - pos_arr) - 1;

            if (L <= R) {
                add_ok[i] = 1;
                add_l[i] = L;
                add_r[i] = R;
                for (int x = L; x <= R; x++) {
                    for (int y = x; y <= R; y++) {
                        cnt_seg[x][y]++;
                    }
                }
            }
        } else {
            int x;
            cin >> x;
            if (add_ok[x]) {
                for (int i1 = add_l[x]; i1 <= add_r[x]; i1++) {
                    for (int j1 = i1; j1 <= add_r[x]; j1++) {
                        cnt_seg[i1][j1]--;
                    }
                }
            }
        }

        cout << (simulate() ? "Yes" : "No") << '\n';
    }

    return 0;
}

brute.cpp 显式维护当前有哪些线段活跃，然后不断尝试：

如果某条线段两端已经黑了
就把中间点全部染黑

直到不能继续为止。

这个做法可以帮助理解题意，但数据范围下显然不可能这么做。

关键观察是：

一次染色只能把两个已黑点之间的点染黑。

因此黑色集合只能“填补空隙”，而不会向最左黑点左边或最右黑点右边扩张。

这立刻带来第一个必要条件：

第 1 个特殊点和第 n 个特殊点必须初始为黑色

接下来只关注初始黑点序列：

$b_1 < b_2 < \dots < b_k$

如果相邻两个初始黑点 $b_i$ 和 $b_{i+1}$ 中间存在白点，那么这段白色空隙想被染黑，就必须有某个活跃操作跨过它。

原因很直接：

在这段空隙第一次被染黑前，里面没有黑点
所以唯一可能的合法线段，端点只能来自这段空隙的左右两侧

反过来，如果某个活跃操作跨过了这段空隙，那么它两侧的初始黑点本来就是黑的，可以直接用这条线段把整段空隙染黑。

于是原题就被压缩成：

两端点初始必须黑
每一段初始白色空隙，都至少被一个活跃操作跨过

现在看一次 1 l r 操作。

在特殊点下标上，它覆盖的是一个连续区间 $[L, R]$ 。

如果这段区间里包含黑点序列中的第 $s$ 到第 $t$ 个黑点，那么它就能跨过所有空隙：

$[s, t-1]$

这变成了一个非常标准的动态区间覆盖问题：

加入操作：给一段空隙覆盖次数 +1
撤销操作：给同一段空隙覆盖次数 -1
判断当前最小覆盖次数是否大于 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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 500000 + 5;
const int INF = 1000000000;

int n, q;
int pos_arr[MAXN];
int color_arr[MAXN];
int black_idx[MAXN];
int black_cnt;

int seg_min[MAXN << 2];
int lazy_add[MAXN << 2];
int base_gap[MAXN];

int op_l[MAXN];
int op_r[MAXN];
int op_valid[MAXN];

void push_up(int u) {
    seg_min[u] = min(seg_min[u << 1], seg_min[u << 1 | 1]);
}

void build(int u, int l, int r) {
    lazy_add[u] = 0;
    if (l == r) {
        seg_min[u] = base_gap[l];
        return;
    }

    int mid = (l + r) >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    push_up(u);
}

void apply_add(int u, int val) {
    seg_min[u] += val;
    lazy_add[u] += val;
}

void push_down(int u) {
    if (lazy_add[u] == 0) {
        return;
    }
    apply_add(u << 1, lazy_add[u]);
    apply_add(u << 1 | 1, lazy_add[u]);
    lazy_add[u] = 0;
}

void range_add(int u, int l, int r, int ql, int qr, int val) {
    if (ql <= l && r <= qr) {
        apply_add(u, val);
        return;
    }

    push_down(u);
    int mid = (l + r) >> 1;
    if (ql <= mid) {
        range_add(u << 1, l, mid, ql, qr, val);
    }
    if (qr > mid) {
        range_add(u << 1 | 1, mid + 1, r, ql, qr, val);
    }
    push_up(u);
}

bool can_all_black() {
    if (color_arr[1] == 0 || color_arr[n] == 0) {
        return false;
    }
    if (black_cnt <= 1) {
        return n == 1 && color_arr[1] == 1;
    }
    return seg_min[1] > 0;
}

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

    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> pos_arr[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> color_arr[i];
    }

    black_cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (color_arr[i] == 1) {
            black_idx[++black_cnt] = i;
        }
    }

    int gap_cnt = max(0, black_cnt - 1);
    if (gap_cnt > 0) {
        for (int i = 1; i <= gap_cnt; i++) {
            if (black_idx[i + 1] == black_idx[i] + 1) {
                // 两个黑点相邻，中间没有白点，这个“缝隙”天然已经满足。
                base_gap[i] = INF;
            } else {
                // 中间存在白点，需要至少一个活跃操作跨过这段缝隙。
                base_gap[i] = 0;
            }
        }
        build(1, 1, gap_cnt);
    }

    cout << (can_all_black() ? "Yes" : "No") << '\n';

    for (int i = 1; i <= q; i++) {
        int op;
        cin >> op;
        op_valid[i] = 0;

        if (op == 1) {
            int l, r;
            cin >> l >> r;

            if (gap_cnt > 0) {
                int left_pos = lower_bound(pos_arr + 1, pos_arr + n + 1, l) - pos_arr;
                int right_pos = (int)(upper_bound(pos_arr + 1, pos_arr + n + 1, r) - pos_arr) - 1;

                if (left_pos <= right_pos && black_cnt >= 2) {
                    int left_black = lower_bound(black_idx + 1, black_idx + black_cnt + 1, left_pos) - black_idx;
                    int right_black = (int)(upper_bound(black_idx + 1, black_idx + black_cnt + 1, right_pos) - black_idx) - 1;

                    if (left_black < right_black) {
                        op_valid[i] = 1;
                        op_l[i] = left_black;
                        op_r[i] = right_black - 1;
                        range_add(1, 1, gap_cnt, op_l[i], op_r[i], 1);
                    }
                }
            }
        } else {
            int x;
            cin >> x;
            if (gap_cnt > 0 && op_valid[x]) {
                range_add(1, 1, gap_cnt, op_l[x], op_r[x], -1);
            }
        }

        cout << (can_all_black() ? "Yes" : "No") << '\n';
    }

    return 0;
}

复杂度

每次操作主要做：

二分定位特殊点区间
二分定位黑点序号区间
线段树区间加减

所以单次复杂度：

$O(log n)$

总时间复杂度：

$O((n + q) \log n)$

空间复杂度：

$O(n + q)$

总结

这题最关键的不是线段树，而是先把复杂染色过程压缩成一个更简单的判定：

黑色只能填补初始黑点之间的白色空隙

一旦看出这一点，后面就是“动态维护所有空隙是否都被覆盖”的标准模型。

一图流解析

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

P8473 [Aya Round 1 H] 破碎的历史

题目背景

幻想乡迎来了它的毁灭，幻想的载体也已经遁入了幻想。

所幸的是，幻想乡中的乡民们还侥幸存活着，她们在尝试恢复幻想乡的历史。然而历史之中的大大小小的事情不计其数，人们只能记得起一些大事情罢了。

或许，根据那些重要的事情，可以把次要的事件推导出来呢？

题目描述

数轴的正半轴上有 $n$ 个互不相同的被黑白染色的特殊整点，位置从左到右依次为 $p_1,p_2,\cdots,p_n$ 。维护初始为空的可重线段集合 $S$ 。

$q$ 次操作。操作分若干种，具体格式如下：

1 l r：将所有满足 $l \le x \le y \le r$ 且两端点均为特殊整点的线段 $[x,y]$ 加入 $S$ 。
2 x：撤回第 $x$ 次操作添加的线段。

在初始时和每次操作后，假设你可以进行任意次（可以是零次）染色。每次从 $S$ 中选出一条线段 $[x,y]$ ，满足位于点 $x$ 和点 $y$ 的特殊整点均为黑色，然后将所有在线段内的白色特殊整点染黑。试判断是否存在至少一种合法染色方式使得正半轴上的所有特殊整点均被染黑（即，不存在白色特殊整点）。注意：所有的询问均为「假设」，即各组询问之间独立，不会造成对数轴的实际修改。

输入格式

第一行输入两个整数 $n,q$ 。
第二行输入 $n$ 个整数 $p_1,p_2,\cdots,p_n$ ，表示 $n$ 个特殊整点从左到右的位置。
第三行输入 $n$ 个整数 $a_1,a_2,\cdots,a_n$ ，表示特殊整点的颜色。其中 $a_i=0$ 表示白色， $a_i=1$ 表示黑色。
接下来 $q$ 行，每行二至三个整数，表示一次操作。

输出格式

输出共 $(q+1)$ 行。
在初始时和每次操作后，输出一行一个字符串：
- yes 代表存在合法染色方式。
- no 代表不存在合法染色方式。
你可以输出字符串的任意大小写形式。例如：字符串 yes、Yes、YES 均会被视为表示存在合法染色方式。

输入输出样例 #1

输入 #1

text

1
2
3
4
5
66 3
1 2 3 5 8 13
1 0 0 1 0 1
1 5 10
1 1 15
2 2

输出 #1

text

1
2
3
4No
No
Yes
No

说明/提示

样例解释

六个特殊点的位置/颜色在数轴正半轴上如图所示。

容易发现，并非所有点都是黑点。因此在进行操作前，输出 $\verb!NO!$ 。

第一次操作后，一共往 $S$ 加入了三条线段： $[5,5],[8,8],[5,8]$ （图中省略了端点重叠的线段）。容易发现，此时无法进行任何操作，因此没法将所有点变成黑点。输出 $\verb!NO!$ 。

第二次操作后，又往 $S$ 中加入了 $20$ 条线段。除去端点重叠的选段，在 $S$ 中如图所示。（以示区别，上一次操作加入的边标成了深蓝色）。

可以找出一种方案，将图上所有特殊点变成黑点。具体而言，首先选择 $S$ 中 $[1,5]$ 线段（容易发现位于 $1$ 和 $5$ 的特殊点均为黑点，因此可以进行染色），那么可以把位于 $2$ 和 $3$ 的点染色。

此时又可以选择 $S$ 中 $[3,13]$ 线段（在上一轮操作中， $3$ 号点变为了黑点，因此 $[3,13]$ 符合条件），将点 $8$ 染为黑色。

此时所有点都为黑色，因此输出 $\verb!YES!$ 。再次强调，询问之间互相独立，且只是询问是否存在染色方案，而不会对特殊整点进行实际上的染色操作。

第三个操作撤回了第二个操作往 $S$ 里加入的所有线段。因此退回到了只有第一个操作的情况。不存在一种方案将所有点染黑，因此输出 $\verb!NO!$ 。

数据范围

对于所有数据， $1 \le n,q \le 5 \times 10^5$ ， $a_i \in \{0,1\}$ ， $1 \le l< r \le 10^9$ ， $1 \le p_i \le 10^9$ 。保证 $p_i$ 单调递增， $2$ 操作撤销的只会是 $1$ 操作，且每个操作最多被撤销一次。

[Aya Round 1 H] 破碎的历史

目录

题意

思路

代码

复杂度

总结

一图流解析