题目描述
县城里有 n 个用地道相连的房子排成一条直线，第 i 个房子只与第 i-1 和 i+1 个相连。特别地，第 1 个房子只和第 2 个联通，第 n 个房子只和第 n-1 个联通。
有 m 条消息依次传来：
- D x：鬼子将 x 号房子摧毁了，地道被堵上
- R：村民们将鬼子上一个摧毁的房子修复了
- Q x：有一名士兵被围堵在 x 号房子中，询问能到达的房子数量
数据范围：1 ≤ n, m ≤ 5×10⁴
问题分析
核心观察
对于未被摧毁的 x 号房子，士兵能到达的范围是连续的，由左右两边最近的被摧毁房子决定。
设左边最近的被摧毁房子位置为 L（L < x），右边最近的被摧毁房子位置为 R（R > x），则能到达的范围是 (L+1) 到 (R-1)，能到达的房子数为 R – L – 1。
问题转化
原问题转化为：
- 维护一个集合 S，存储所有被摧毁的房子
- 对于查询 x，需要找到 S 中 x 的前驱（小于 x 的最大值）和后继（大于 x 的最小值）
- 答案 = 后继 – 前驱 – 1
算法设计
为什么使用树状数组？
树状数组（Fenwick Tree）是一种高效的数据结构，用于维护数组前缀和的动态查询和更新。
- 单点更新 O(log n)：修改一个元素的值
- 区间查询 O(log n)：查询前缀和
- 可以通过二分查找实现「连续完好的区间长度」查询
核心技巧：不直接找被摧毁的房子，而是找 x 左右连续完好的房子数量。
核心操作：查询连续完好区间
使用二分查找分别寻找左右两边连续完好的区间长度。
查询左边连续完好房子数
// 查询 x 左边连续完好的房子数
int find_left(int x) {
int l = 1, r = x, ans = x;
while (l <= r) {
int mid = (l + r) >> 1;
// 检查 [mid, x] 区间是否全部完好
if (query(mid, x) == x - mid + 1) {
ans = mid;
r = mid - 1; // 向左收缩，寻找更左边的起点
} else {
l = mid + 1; // 不全部完好，向右收缩
}
}
return x - ans + 1; // 左边连续完好数
}查询右边连续完好房子数
// 查询 x 右边连续完好的房子数
int find_right(int x) {
int l = x, r = n, ans = x;
while (l <= r) {
int mid = (l + r) >> 1;
// 检查 [x, mid] 区间是否全部完好
if (query(x, mid) == mid - x + 1) {
ans = mid;
l = mid + 1; // 向右扩大，寻找更右边的终点
} else {
r = mid - 1; // 不全部完好，向左收缩
}
}
return ans - x + 1; // 右边连续完好数
}二分查找的正确性
定义函数 f(mid) = [区间[mid, x]是否全部完好]
- 若 f(mid) = true，则对于任意 mid' > mid，区间[mid', x] 是 [mid, x] 的子区间，必然也全部完好
- 若 f(mid) = false，则对于任意 mid' < mid，区间[mid', x] 包含区间[mid, x]，必然也存在被摧毁房子
因此 f(mid) 具有单调性，存在一个分界点 M，使得当 mid ≥ M 时 f(mid)=true，当 mid < M 时 f(mid)=false。二分查找可以找到最小的 mid 使得 f(mid)=true。
完整代码实现
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 50010;
int n, m; // 房子数、消息数
int bad[N]; // 标记房子是否被摧毁，1=已摧毁
int tr[N]; // 树状数组，存储完好的房子数
int stk[N], top; // 栈，记录摧毁顺序用于 R 操作
// lowbit 函数：返回 x 二进制的最低位 1
int lowbit(int x) {
return x & -x;
}
// 树状数组单点更新
void add(int x, int c) {
for (; x <= n; x += lowbit(x))
tr[x] += c;
}
// 树状数组前缀和查询
int sum(int x) {
int res = 0;
for (; x; x -= lowbit(x))
res += tr[x];
return res;
}
// 区间查询：[l, r] 区间内完好的房子数
int query(int l, int r) {
if (l > r) return 0;
return sum(r) - sum(l - 1);
}
// 查询 x 左边连续完好的房子数
int find_left(int x) {
int l = 1, r = x, ans = x;
while (l <= r) {
int mid = (l + r) >> 1;
if (query(mid, x) == x - mid + 1) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
return x - ans + 1;
}
// 查询 x 右边连续完好的房子数
int find_right(int x) {
int l = x, r = n, ans = x;
while (l <= r) {
int mid = (l + r) >> 1;
if (query(x, mid) == mid - x + 1) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
return ans - x + 1;
}
int main() {
scanf("%d%d", &n, &m);
// 初始化树状数组：所有房子都是完好的
for (int i = 1; i <= n; i++)
add(i, 1);
while (m--) {
char op[2];
int x;
scanf("%s", op);
if (op[0] == 'D') { // 摧毁操作
scanf("%d", &x);
if (!bad[x]) {
bad[x] = 1;
add(x, -1); // 完好数减 1
stk[++top] = x; // 入栈
}
} else if (op[0] == 'R') { // 修复操作
if (top > 0) {
x = stk[top--]; // 取出上一个被摧毁的房子
bad[x] = 0;
add(x, 1); // 完好数加 1
}
} else if (op[0] == 'Q') { // 查询操作
scanf("%d", &x);
if (bad[x]) {
printf("0\n"); // 士兵在被摧毁的房子中
} else {
int l = find_left(x); // 左边连续完好数
int r = find_right(x); // 右边连续完好数
printf("%d\n", l + r - 1); // 减去重复计算的 x
}
}
}
return 0;
}复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 单点修改（add） | O(log n) | O(n) |
| 区间查询（query） | O(log n) | |
| 二分查找 | O(log² n) | |
| 总复杂度 | O(m log² n) |
对于 n, m ≤ 50000，log₂50000 ≈ 16，总操作数约为 50000 × 256 ≈ 1.28×10⁷，完全可以接受。
关键要点总结
- 栈的应用：维护被摧毁房子的顺序，确保 R 操作修复的是「最近」被摧毁的房子
- 树状数组：高效维护「完好房子数」，支持 O(log n) 的单点更新和区间查询
- 二分查找：利用单调性快速定位连续完好区间的边界
- 答案公式：left_good + right_good – 1（x 被重复计算）
样例验证
输入：
7 9
D 3
D 6
D 5
Q 4
Q 5
R
Q 4
R
Q 4处理过程：
操作 状态（被摧毁） 查询4号结果 说明
初始 {} - 所有房子完好
D 3 {3} - 摧毁3号
D 6 {3,6} - 摧毁6号
D 5 {3,5,6} - 摧毁5号
Q 4 {3,5,6} 1 4号只能到达4号本身
Q 5 {3,5,6} 0 5号已被摧毁
R {3,6} - 修复5号
Q 4 {3,6} 2 4号可到达4,5
R {3} - 修复6号
Q 4 {3} 4 4号可到达4,5,6,7输出：1 0 2 4