Tunnel Warfare（线段树取连续区间）

emmmmmmmm我菜爆了

思路来自：https://blog.csdn.net/chudongfang2015/article/details/52133243

线段树最难的应该就是要维护什么东西

这道题刚开始1~n都是连通的

D x 即破坏x这个地方

Q x 即查询包含x的连续区间有多长

R 即修复最后一次D的x

博主给了一个非常好的思路

线段树维护两个值，该区间内被破坏的最大的点，以及最小的那个点

如 1，2，...,，6 破坏了 2 ，4，5 那么该区间里的pmax = 5，pmin = 2

若要查询3 则取3右边的pmin 减去 3左边的pmax 再减1

3右的pmin = 4， 3左的pmax = 2 即为 4 - 2 - 1 = 1

未被破坏的点或者区间的pmax pmin分别设为0，n + 1

这样就能query的值能直接用来计算

比如1，2，3，4，5均为被破坏

则pmin - pmax - 1 = n = 5

特殊情况就为查询的x自身被破坏了

pmin = pmax = x 这样打印的结果是-1，所以打印的时候取一下pmin-pmax-1和0的最大值就好了

（orz多转换思路，试试各种值的维护）

#include <cstdio>

#include <algorithm>

#define lp p<<1

#define rp p<<1|1

using namespace std;

const int maxn = 5e4 + ;

int pmin[maxn<<], pmax[maxn<<];

int des[maxn], n;

void build(int p, int l, int r) {

    if (l == r) {

        pmin[p] = n + ;

        pmax[p] = ;

        return;

    }

    int mid = l + r >> ;

    build(lp, l, mid);

    build(rp, mid + , r);

    pmax[p] = max(pmax[lp], pmax[rp]);

    pmin[p] = min(pmin[lp], pmin[rp]);

}

void update(int p, int l, int r, int pos, int num1, int num2) {

    if (l == r) {

        pmax[p] = num1;

        pmin[p] = num2;

        return;

    }

    int mid = l + r >> ;

    if (pos <= mid) {

        update(lp, l, mid, pos, num1, num2);

    } else {

        update(rp, mid + , r, pos, num1, num2);

    }

    pmax[p] = max(pmax[lp], pmax[rp]);

    pmin[p] = min(pmin[lp], pmin[rp]);

}

int query_min(int p, int l, int r, int x, int y) {

    if (x <= l && y >= r) return pmin[p];

    int mid = l + r >> ;

    int res = 0x3f3f3f3f;

    if (x <= mid) res = min(res, query_min(lp, l, mid, x, y));

    if (y > mid) res = min(res, query_min(rp, mid + , r, x, y));

    return res;

}

int query_max(int p, int l, int r, int x, int y) {

    if (x <= l && y >= r) return pmax[p];

    int mid = l + r >> ;

    int res = ;

    if (x <= mid) res = max(res, query_max(lp, l, mid, x, y));

    if (y > mid) res = max(res, query_max(rp, mid + , r, x, y));

    return res;

}

int main() {

    int m;

    while (~scanf("%d%d", &n, &m)) {

        int last = ;

        build(, , n);

        while (m--) {

            char opt[];

            scanf("%s", opt);

            if (opt[] == 'D') {

                int p;

                scanf("%d", &p);

                update(, , n, p, p, p);

                des[++last] = p;

            } else if (opt[] == 'R') {

                update(, , n, des[last--], , n + );

            } else {

                int q;

                scanf("%d", &q);

                int ans1 = query_max(, , n, , q), ans2 = query_min(, , n, q, n);

                printf("%d\n", ans2 - ans1 -  >  ? ans2 - ans1 -  : );

            }

        }

    }

    return ;

}

对博主的代码简化了一下下（