地道战村庄连接问题 - 线段树解法分析

题目理解

给定一排 $n$ 个初始相连的村庄，处理三种操作：

1. D x：摧毁第 $x$ 个村庄（断开连接）
2. Q x：查询第 $x$ 个村庄所在连通块的大小
3. R：恢复最后被摧毁的村庄

解题方法

核心思路

使用线段树维护两个信息：

1. 左侧最近被摧毁点（最大值）
2. 右侧最近被摧毁点（最小值）

对于查询操作 $Q$ $x$：

• 找出 $x$ 左侧最近的被摧毁点 $Max$
• 找出 $x$ 右侧最近的被摧毁点 $Min$
• 连通块大小为 $Min - Max - 1$

算法实现

#include <bits/stdc++.h>
using namespace std;
const int N = 50010;

stack<int> sta; // 用于恢复操作
int n, m;

struct Tree {
    int l, r, mn, mx;
    #define l(x) tr[x].l
    #define r(x) tr[x].r
    #define ls(x) (x << 1)
    #define rs(x) (x << 1 | 1)
    #define mn(x) tr[x].mn
    #define mx(x) tr[x].mx
} tr[N << 2];

void build(int x, int l, int r) {
    l(x) = l, r(x) = r;
    if (l == r) {
        mn(x) = n + 1; // 初始化右侧最小为n+1
        mx(x) = 0;     // 初始化左侧最大为0
        return;
    }
    int mid = (l + r) >> 1;
    build(ls(x), l, mid);
    build(rs(x), mid + 1, r);
    // 更新区间信息
    mn(x) = min(mn(ls(x)), mn(rs(x)));
    mx(x) = max(mx(ls(x)), mx(rs(x)));
}

// 更新最大值（左侧最近被摧毁点）
void chgmax(int x, int pos, int v) {
    if (l(x) == r(x)) {
        mx(x) = v;
        return;
    }
    int mid = (l(x) + r(x)) >> 1;
    if (pos <= mid) chgmax(ls(x), pos, v);
    else chgmax(rs(x), pos, v);
    mx(x) = max(mx(ls(x)), mx(rs(x)));
}

// 更新最小值（右侧最近被摧毁点） 
void chgmin(int x, int pos, int v) {
    if (l(x) == r(x)) {
        mn(x) = v;
        return;
    }
    int mid = (l(x) + r(x)) >> 1;
    if (pos <= mid) chgmin(ls(x), pos, v);
    else chgmin(rs(x), pos, v);
    mn(x) = min(mn(ls(x)), mn(rs(x)));
}

int Qmax(int x, int l, int r) { /* 查询区间最大值 */ }
int Qmin(int x, int l, int r) { /* 查询区间最小值 */ }

int main() {
    scanf("%d%d", &n, &m);
    build(1, 1, n);
    while (m--) {
        char op[2]; int x;
        scanf("%s", op);
        if (op[0] == 'D') {
            scanf("%d", &x);
            // 标记x为被摧毁点
            chgmax(1, x, x);
            chgmin(1, x, x);
            sta.push(x);
        } else if (op[0] == 'Q') {
            scanf("%d", &x);
            int Max = Qmax(1, 1, x);   // 左侧最近被摧毁
            int Min = Qmin(1, x, n);   // 右侧最近被摧毁
            printf("%d\n", (Min == Max) ? 0 : (Min - Max - 1));
        } else { // 恢复操作
            int pos = sta.top(); sta.pop();
            chgmax(1, pos, 0);     // 重置最大值
            chgmin(1, pos, n + 1); // 重置最小值
        }
    }
    return 0;
}