Question

HDU1540 Tunnel Warfare

在一条线上有 \(n\) 个村庄，两个相邻的村庄之间用地道连接，做 \(m\) 次操作

D x 第 \(x\) 个村庄被摧毁，它的地道也一同被摧毁
Q x 查询第 \(x\) 个村庄所能到达的村庄总数（包括村庄 \(x\)）
R 重建刚才被摧毁的村庄

Solution

对于 \(R\) 操作，用一个栈模拟就好了，现在考虑 \(D\) 和 \(Q\) 操作，如果我们定义存在的村庄是 \(1\)，已经摧毁的村庄是 \(0\) ，那么问题就翻译成了查找一段连续 \(1\) 的长度，并且带修改

用线段树，定义 \(pre,suf\) 表示每个区间从左边连续开始的 \(1\) 的个数已经从右边开始连续 \(1\) 的个数

那么如何合并呢，对于一个区间，如果左儿子全是 \(1\) ，那么这个区间的 \(pre\) 就是左儿子的个数+右儿子的 \(pre\) ，否则就是左儿子的 \(pre\)，对于 \(suf\) 以此类推

当一个区间修改的时候，最多需要修改的区间是它本身已经它的父节点，然而我们在 \(push\_up()\) 的时候能更新它的父节点

Code

#include<bits/stdc++.h>
using namespace std;

struct Seg_Tree{
    int n;
    vector<int> t,pre,suf; 

    Seg_Tree(int n){this->n=n;t.assign(n<<2,0);pre.assign(n<<2,0);suf.assign(n<<2,0);}

    void push_up(int x,int len){
        pre[x]=pre[x<<1];
        suf[x]=suf[x<<1|1];
        if(pre[x]==len-(len>>1)) pre[x]+=pre[x<<1|1];  //如果左儿子全是 1，那么左边的pre就是左儿子的个数加上右儿子的pre
        if(suf[x]==(len>>1)) suf[x]+=suf[x<<1];  //如果右儿子全是 1，那么右边的suf就是右儿子的个数加上左儿子的suf
    }

    void build(int x,int l,int r){
        if(l==r){t[x]=pre[x]=suf[x]=1;return ;}
        int mid=(l+r)>>1;
        build(x<<1,l,mid);
        build(x<<1|1,mid+1,r);
        push_up(x,r-l+1);
    }

    void update(int x,int l,int r,int pos,int val){ 
        if(l==r) {t[x]=pre[x]=suf[x]=val;return ;}
        int mid=(l+r)>>1;
        if(pos<=mid) update(x<<1,l,mid,pos,val);
        else update(x<<1|1,mid+1,r,pos,val);
        push_up(x,r-l+1);
    }

    int query(int x,int l,int r,int pos){
        if(l==r) return t[x];
        int mid=(l+r)>>1;
        if(pos<=mid){
            if(pos+suf[x<<1]>mid) return suf[x<<1]+pre[x<<1|1];
            else return query(x<<1,l,mid,pos);
        }
        else{
            if(mid+pre[x<<1|1]>=pos) return suf[x<<1]+pre[x<<1|1];
            else return query(x<<1|1,mid+1,r,pos);
        }
    }
};

int main(){
    // freopen("1540.in","r",stdin);
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF){
        Seg_Tree T(n); stack<int> st;
        T.build(1,1,n);
        while(m--){
            char op[10];scanf("%s",op);
            if(op[0]=='Q'){
                int x;scanf("%d",&x);
                printf("%d\n",T.query(1,1,n,x)); //询问 x 有多少 1 是和他连的
            }
            if(op[0]=='D'){
                int x;scanf("%d",&x);
                st.push(x);
                T.update(1,1,n,x,0); //摧毁 x 村庄
            }
            if(op[0]=='R'){
                int x=st.top();st.pop();
                T.update(1,1,n,x,1); //重建 x 村庄
            }
        }
    }
    return 0;
}