鬼子进村

形式化题目

有一排 $n$ 个位置 $1,2,\dots,n$ 。初始时所有位置都“完好”。依次处理 $m$ 条操作：

D x：把位置 $x$ 标记为“摧毁”，并把这个动作压入历史；
R：撤销最近一次尚未撤销的摧毁，把它对应的位置恢复为“完好”；
Q x：如果 $x$ 已被摧毁，答案是 $0$ ；否则求包含 $x$ 的、由连续完好位置组成的极大区间长度。

解法总览

暴力查询要向左、向右逐格扫描直到遇到断点，单次最坏 $O(n)$ ，总复杂度 $O(nm)$ ，在 $n,m\leqslant 5\times 10^4$ 下会超时。优化的关键在于换一个视角。

关键观察：把每个被摧毁的位置视为一个“断点”，再补上两个虚拟断点 $0$ 和 $n+1$ （看作始终被摧毁）。对任意一个未被摧毁的查询点 $x$ ，设

$L=\max\{y\mid y$ 被摧毁且 $y<x\}$ ，即 $x$ 左侧最近的断点；
$R=\min\{y\mid y$ 被摧毁且 $y>x\}$ ，即 $x$ 右侧最近的断点。

那么 $x$ 能到达的恰好就是开区间 $(L,R)$ 内的所有整数位置，数量为 $R-L-1$ 。若 $x$ 本身被摧毁，答案为 $0$ 。

于是问题归结为：维护一个动态有序集合 $S$ （初始含 $0,n+1$ ），支持插入、删除、查询某个值的前驱与后继。三种做法只是同一个抽象的不同实现方式：

解法	有序集合的实现	单次操作复杂度	说明
解法一：FHQ-Treap	按值分裂的无旋平衡树	期望 $O(\log n)$	正式主解，可迁移到需要分裂/合并的场景
解法二：`std::set`	红黑树	$O(\log n)$	本题最简写法
解法三：静态二分	排序数组 + 二分	$O(\log n)$	仅在无修改（离线）时可用

R 操作恢复的是“上一个被摧毁的房子”，这正是后进先出，所以额外用一个栈记录摧毁历史即可，无需在有序集合里再找最大值。

解法一：FHQ-Treap

思路

FHQ-Treap 把所有操作拆成两件事：按值切开 split，再按顺序拼回 merge。把它当作一个 std::set 使用，正好提供本题需要的三个接口：

摧毁 $x$ ：insert(x)；
修复 $x$ ：del(x)；
查询 $L,R$ ：lower_bound 求 $<x$ 的最大值，upper_bound 求 $>x$ 的最小值。

由于 $x$ 未被摧毁时左右两侧必定分别存在虚拟断点 $0$ 和 $n+1$ ，lower_bound/upper_bound 一定找得到，不需要处理“找不到”的情况。

也可以用笔记里的另一种写法：对 $x$ 做 split(root, x, tl, tr)，则 $L$ 是 tl 的最右节点、 $R$ 是 tr 的最左节点，查询完再 merge 回去。两种写法等价，前者常数更小，因为不需要改动树结构。

需要注意一个细节：如果同一个位置被 D 了两次，std::set 的 insert/erase 会自动去重、且 erase 删除全部同值元素；为了让 FHQ-Treap 行为与之一致，模板中的 insert 先判重，del 一次删掉整棵同值子树。否则重复摧毁会留下多余的断点，导致答案偏小。

下面是查询 Q 4（此时断点为 $\{0,3,5,6,8\}$ ）时的示意：

步骤	内容
1	$4$ 未被摧毁，继续查询
2	`upper_bound(4)` 找到 $R=5$
3	`lower_bound(4)` 找到 $L=3$
4	答案 $R-L-1=5-3-1=1$ ，即只有 $\{4\}$ 本身

代码

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/**
 * 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-09-15 22:15
 * update_at: 2026-09-15 22:15
 *
 * P1503 鬼子进村
 * 解法：把被摧毁的房子看作“断点”，用 FHQ-Treap 维护断点集合。
 *       查询 x 时，找到左侧最近的断点 L 和右侧最近的断点 R，
 *       能到达的房子数就是 R - L - 1。
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

// 增加虚拟边界 0 和 n+1，它们永远是被摧毁的
const int maxn = 5e5 + 5;

// ==================== FHQ-Treap 模板（按值分裂） ====================
template<typename T = long long, int N = 500005>
struct FHQ {
    int root;

    struct Node {
        int l, r;
        int size, fix;
        T val;
    };
    Node tr[N];
    int tr_idx = 0;
    int get() { return ++tr_idx; }

    std::mt19937 rnd;

    FHQ() {
        rnd.seed(233);
        init();
    }

    void init() {
        root = 0;
        tr_idx = 0;
        tr[0].l = tr[0].r = tr[0].size = 0;
        tr[0].val = 0;
    }

    int new_node(T v) {
        int id = get();
        tr[id].l = tr[id].r = 0;
        tr[id].size = 1;
        tr[id].fix = rnd();
        tr[id].val = v;
        return id;
    }

    void push_up(int u) {
        tr[u].size = tr[tr[u].l].size + tr[tr[u].r].size + 1;
    }

    // 把树 u 分成 x(<=v) 和 y(>v)
    void split(int u, int v, int &x, int &y) {
        if (!u) { x = y = 0; return; }
        if (tr[u].val <= v) {
            x = u;
            split(tr[u].r, v, tr[u].r, y);
        } else {
            y = u;
            split(tr[u].l, v, x, tr[u].l);
        }
        push_up(u);
    }

    int merge(int x, int y) {
        if (!x || !y) return x + y;
        if (tr[x].fix > tr[y].fix) {
            tr[x].r = merge(tr[x].r, y);
            push_up(x);
            return x;
        } else {
            tr[y].l = merge(x, tr[y].l);
            push_up(y);
            return y;
        }
    }

    // 集合中是否存在值 v
    bool contains(T v) {
        int u = root;
        while (u) {
            if (tr[u].val == v) return true;
            u = (v < tr[u].val) ? tr[u].l : tr[u].r;
        }
        return false;
    }

    // 插入 v，已存在则不重复插入（与 std::set 语义一致）
    void insert(T v) {
        if (contains(v)) return;
        int x, y;
        split(root, v, x, y);
        root = merge(merge(x, new_node(v)), y);
    }

    // 删除所有值为 v 的节点（与 std::set::erase 语义一致）
    void del(T v) {
        int x, y, z;
        split(root, v, x, z);
        split(x, v - 1, x, y);
        // y 中全是值为 v 的节点，直接整棵树丢弃
        root = merge(x, z);
    }

    // 查询第一个 > v 的值，找不到返回 INF_MAX
    T upper_bound(T v) {
        T ans = numeric_limits<T>::max();
        int u = root;
        while (u) {
            if (tr[u].val > v) {
                ans = tr[u].val;
                u = tr[u].l;
            } else {
                u = tr[u].r;
            }
        }
        return ans;
    }

    // 查询第一个 < v 的值，找不到返回 INF_MIN
    T lower_bound(T v) {
        T ans = numeric_limits<T>::min();
        int u = root;
        while (u) {
            if (tr[u].val < v) {
                ans = tr[u].val;
                u = tr[u].r;
            } else {
                u = tr[u].l;
            }
        }
        return ans;
    }
};
// ==================== FHQ-Treap 模板结束 ====================

int n, m;
bool destroyed[maxn]; // destroyed[i] 表示 i 号房子当前是否被摧毁
int stk[maxn], top_;  // 记录摧毁历史，R 操作按后进先出恢复
FHQ<int, maxn> fhq;

void read_data() {
    cin >> n >> m;
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0);
    read_data();

    // 虚拟边界：0 和 n+1 永远是被摧毁的
    fhq.insert(0);
    fhq.insert(n + 1);

    for (int i = 1; i <= m; ++i) {
        string op;
        cin >> op;
        if (op == "D") {
            int x;
            cin >> x;
            destroyed[x] = true;
            fhq.insert(x);
            stk[++top_] = x;
        } else if (op == "R") {
            int x = stk[top_--];
            destroyed[x] = false;
            fhq.del(x);
        } else { // Q
            int x;
            cin >> x;
            if (destroyed[x]) {
                cout << 0 << "\n";
            } else {
                int R = fhq.upper_bound(x);
                int L = fhq.lower_bound(x);
                cout << R - L - 1 << "\n";
            }
        }
    }

    return 0;
}

同一份解法也在 main.cpp 中作为标准入口提供。

复杂度

每次 split/merge 期望 $O(\log n)$ ，总时间复杂度 $O(m\log n)$ ，空间复杂度 $O(n+m)$ 。

Python 版本

Python 使用同一套思路，把模板换成类实现，并用 sys.stdin.buffer 一次性读入以降低常数。递归深度在随机数据下为期望 $O(\log n)$ ，但仍显式设置 sys.setrecursionlimit 以防万一。

python

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#!/usr/bin/env python3
"""
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-09-15 22:15
update_at: 2026-09-15 22:15

P1503 鬼子进村
解法：把被摧毁的房子看作“断点”，用 FHQ-Treap 维护断点集合。
      查询 x 时，找到左侧最近的断点 L 和右侧最近的断点 R，
      能到达的房子数就是 R - L - 1。
"""
import sys
from typing import Any, Optional, Tuple

sys.setrecursionlimit(300000)


class Node:
    """Treap 节点"""

    __slots__ = ("val", "pri", "size", "l", "r")

    def __init__(self, val: Any, pri: int):
        self.val = val
        self.pri = pri
        self.size = 1
        self.l: Optional["Node"] = None
        self.r: Optional["Node"] = None


class FHQTreap:
    """FHQ-Treap（无旋平衡树），当作有序集合 set 来用。"""

    def __init__(self, seed: int = 233):
        self.root: Optional[Node] = None
        self._seed = seed
        self._rnd_state = seed

    def _rnd(self) -> int:
        # 用线性同余代替 random 模块，速度更快且结果可复现
        self._rnd_state = (self._rnd_state * 1103515245 + 12345) & 0x7FFFFFFF
        return self._rnd_state

    def _size(self, u: Optional[Node]) -> int:
        return u.size if u is not None else 0

    def _push_up(self, u: Node) -> None:
        u.size = self._size(u.l) + self._size(u.r) + 1

    def _new_node(self, val: Any) -> Node:
        return Node(val, self._rnd() | 1)

    def split(self, u: Optional[Node], val: Any) -> Tuple[Optional[Node], Optional[Node]]:
        """左树 x：值 <= val；右树 y：值 > val。"""
        if u is None:
            return None, None
        if u.val <= val:
            x, y = self.split(u.r, val)
            u.r = x
            self._push_up(u)
            return u, y
        else:
            x, y = self.split(u.l, val)
            u.l = y
            self._push_up(u)
            return x, u

    def merge(self, x: Optional[Node], y: Optional[Node]) -> Optional[Node]:
        """前提：x 中所有值 <= y 中所有值。"""
        if x is None or y is None:
            return x if y is None else y
        if x.pri > y.pri:
            x.r = self.merge(x.r, y)
            self._push_up(x)
            return x
        else:
            y.l = self.merge(x, y.l)
            self._push_up(y)
            return y

    def contains(self, val: Any) -> bool:
        """判断集合中是否存在值为 val 的节点。"""
        u = self.root
        while u is not None:
            if u.val == val:
                return True
            u = u.l if val < u.val else u.r
        return False

    def insert(self, val: Any) -> None:
        """插入 val；若已存在则不再重复插入（与 std::set 语义一致）。"""
        if self.contains(val):
            return
        x, y = self.split(self.root, val)
        self.root = self.merge(self.merge(x, self._new_node(val)), y)

    def delete(self, val: Any) -> None:
        """删除所有值为 val 的节点（与 std::set::erase 语义一致）。"""
        x, z = self.split(self.root, val)
        x, _ = self.split(x, val - 1)  # 中间那棵树整体丢弃
        self.root = self.merge(x, z)

    def succ(self, val: Any) -> Optional[Any]:
        """第一个严格大于 val 的值（后继）。"""
        u = self.root
        ans = None
        while u is not None:
            if u.val > val:
                ans = u.val
                u = u.l
            else:
                u = u.r
        return ans

    def pre(self, val: Any) -> Optional[Any]:
        """第一个严格小于 val 的值（前驱）。"""
        u = self.root
        ans = None
        while u is not None:
            if u.val < val:
                ans = u.val
                u = u.r
            else:
                u = u.l
        return ans


def main() -> None:
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    m = int(data[1])

    destroyed = bytearray(n + 2)  # destroyed[i] 表示 i 号房子当前是否被摧毁
    stk = []                      # 摧毁历史，R 操作按后进先出恢复

    fhq = FHQTreap()
    fhq.insert(0)      # 虚拟左边界
    fhq.insert(n + 1)  # 虚拟右边界

    out = []
    idx = 2
    for _ in range(m):
        op = data[idx]
        idx += 1
        if op == b"D":
            x = int(data[idx])
            idx += 1
            destroyed[x] = 1
            fhq.insert(x)
            stk.append(x)
        elif op == b"R":
            x = stk.pop()
            destroyed[x] = 0
            fhq.delete(x)
        else:  # Q
            x = int(data[idx])
            idx += 1
            if destroyed[x]:
                out.append("0")
            else:
                r = fhq.succ(x)
                l = fhq.pre(x)
                out.append(str(r - l - 1))

    sys.stdout.write("\n".join(out) + ("\n" if out else ""))


if __name__ == "__main__":
    main()

解法二：std::set

思路

C++ 标准库的 std::set 底层就是红黑树，天然支持动态有序集合的全部需求：

s.insert(x)：摧毁 $x$ ；
s.erase(x)：修复 $x$ ；
it = s.upper_bound(x)：得到 $R$ ；再 --it 就是 $L$ 。

因为 0 和 n+1 始终在集合中，upper_bound 的结果一定有效，--it 也一定不会越界。用一个布尔数组 destroyed[x] 在 $O(1)$ 内判断查询点是否本身被摧毁，用栈记录摧毁历史实现 R 的撤销。

代码

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/**
 * 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-09-15 22:15
 * update_at: 2026-09-15 22:15
 *
 * P1503 鬼子进村
 * 解法：用 std::set 维护被摧毁的房子（断点）。
 *       查询 x 时用 upper_bound 找到右侧最近断点 R，再往前挪一格得到左侧断点 L，
 *       答案就是 R - L - 1。
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int maxn = 5e5 + 5;

int n, m;
bool destroyed[maxn]; // destroyed[i] 表示 i 号房子当前是否被摧毁
int stk[maxn], top_;  // 摧毁历史，R 操作按后进先出恢复
set<int> s;           // 存储所有被摧毁的房子编号

void read_data() {
    cin >> n >> m;
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0);
    read_data();

    // 虚拟边界：0 和 n+1 永远是被摧毁的
    s.insert(0);
    s.insert(n + 1);

    for (int i = 1; i <= m; ++i) {
        string op;
        cin >> op;
        if (op == "D") {
            int x;
            cin >> x;
            destroyed[x] = true;
            s.insert(x);
            stk[++top_] = x;
        } else if (op == "R") {
            int x = stk[top_--];
            destroyed[x] = false;
            s.erase(x);
        } else { // Q
            int x;
            cin >> x;
            if (destroyed[x]) {
                cout << 0 << "\n";
            } else {
                // 右侧最近的断点
                set<int>::iterator it = s.upper_bound(x);
                int R = *it;
                --it; // 往前一格就是左侧最近的断点
                int L = *it;
                cout << R - L - 1 << "\n";
            }
        }
    }

    return 0;
}

复杂度

每次插入、删除、查找均为 $O(\log n)$ ，总时间复杂度 $O(m\log n)$ ，空间复杂度 $O(n)$ 。

解法三：静态二分（离线）

思路

如果题目没有修改操作（所有摧毁在一开始给出，之后只有查询），动态结构就成了“杀鸡用牛刀”。此时可以把 $0$ 、 $n+1$ 与所有断点放进一个数组，排序后得到严格递增序列，查询 $x$ 时：

upper_bound(a, x) 找到第一个 $>x$ 的元素，即 $R$ ；
它的前一个元素就是 $L$ 。

单次仍是 $O(\log n)$ ，但数组内存连续，常数和缓存命中率都优于任何树形结构。

本题的 $D$ 与 $R$ 交替出现，是标准的动态场景，所以静态二分不能直接用于本题；这里列出它是为了说明“动态问题静态化”这条常见思路，以及写题时应先判断操作序列是否真的动态。

代码

复杂度

预处理 $O(k\log k)$ （ $k$ 为断点数），单次查询 $O(\log k)$ 。

复杂度对比

解法	单次 `D`/`R`	单次 `Q`	总时间	是否适用于本题
FHQ-Treap	期望 $O(\log n)$	期望 $O(\log n)$	$O(m\log n)$	是（主解）
`std::set`	$O(\log n)$	$O(\log n)$	$O(m\log n)$	是
静态二分	不支持	$O(\log k)$	—	否（仅离线可用）
暴力扫描	$O(1)$	$O(n)$	$O(nm)$	会超时

总结

这道题的骨架只有一句话：未被摧毁的连续段 = 左右最近断点夹出的开区间，长度就是 $R-L-1$ 。

识别信号非常明确：

“一维序列上破坏元素 + 查询某点所在连通块大小” → 用断点把序列割开；
“修复上一个被破坏的位置” → 后进先出，用栈撤销；
“动态维护前驱与后继” → std::set，或用 FHQ-Treap 把它当成 set 来写。

有了这个抽象，数据结构只是实现细节：std::set 是红黑树，FHQ-Treap 是按值分裂的无旋平衡树，静态二分是退化到数组的版本。它们的数学本质都是在全序集中寻找某个元素的前驱和后继。相关模板见 rbook 的 FHQ Treap：用分裂与合并维护有序集合。

目录