Tunnel warfare

区间合并

#include<cstdio>

using namespace std;
const int N = 50010;
int ls(int p){ return p<<1; }
int rs(int p){ return p<<1|1;}
int tree[N<<2], pre[N<<2], suf[N<<2];       //tree:记录元素的值；pre:前缀1的个数；suf：后缀1的个数
int history[N];                             //记录村庄被毁的历史
void push_up(int p,int len){                //上传：len是结点p的长度
  pre[p]=pre[ls(p)];                        //左儿子：父结点接收子结点的前缀信息
  suf[p]=suf[rs(p)];                        //右儿子：父结点接收子结点的后缀信息
  if(pre[ls(p)]==(len-(len>>1))) pre[p]=pre[ls(p)]+pre[rs(p)];      //左儿子都是1
  if(suf[rs(p)]==(len>>1)) suf[p]=suf[ls(p)]+suf[rs(p)];            //右儿子都是1
}
void build(int p, int pl,int pr){           //节点编号、左区间，右区间
  if(pl==pr){tree[p]=pre[p]=suf[p]=1; return;}                      //叶节点、前缀1、后缀1
  int mid = (pl+pr) >> 1;
  build(ls(p),pl,mid);
  build(rs(p),mid+1,pr);
  push_up(p,pr-pl+1);
}
void update(int x, int c, int p, int pl, int pr){                   //修改的节点编号、毁灭或重建、节点编号、左区间，右区间
  if(pl==pr){ tree[p]=suf[p]=pre[p]=c; return; }                    //更新叶子结点信息
  int mid=(pl+pr)>>1;
  if(x<=mid) update(x,c,ls(p),pl,mid);
  else update(x,c,rs(p),mid+1,pr);
  push_up(p,pr-pl+1);
}
int query(int x,int p,int pl,int pr){    //查询节点、节点编号、左区间，右区间
  if(pl==pr) return tree[p];             //返回叶子的值
  int mid=(pl+pr)>>1;
  if(x<=mid){                            //查询节点在左子树
    if(x + suf[ls(p)] > mid) return suf[ls(p)] + pre[rs(p)];        //判断查询节点x到mid中间有无零点，无零点加上mid到下一个零点或者右区间的长度
    else return query(x,ls(p),pl,mid);   //有零点递归下一个节点
  }
  else{                                  //查询节点在右子树
    if(mid + pre[rs(p)] >= x) return pre[rs(p)] + suf[ls(p)]; 
    else return query(x,rs(p),mid+1,pr);
  }
}
int main(){
  int n,m,x,tot;                        //村庄数量、操作次数、
  while(scanf("%d%d",&n,&m)>0) {
    build(1, 1,n);                      //建树
    tot = 0;
    while(m--){
      char op[10]; scanf("%s",op);
      if(op[0]=='Q'){scanf("%d",&x); printf("%d\n",query(x,1,1,n));}
      else if(op[0]=='D'){
        scanf("%d",&x);
        history[++tot]=x;              //记录毁灭的历史
       update(x,0,1,1,n);
     }
     else {x=history[tot--]; update(x,1,1,1,n); }                    //重建
    }
  }
  return 0;
}

笔记：pre和suf分别计算连续个数的左区间与右区间，在子节点合并父节点时如果父节点区间内都是 1 那保存区间长度的数字，如果不是，那就只上传左儿子长度或者右儿子长度