HDU - 1540 线段树的合并

#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdio.h>
using namespace std;
const int maxx = 1e5+7;
int s[maxx];
inline int L(int r){return r<<1;};
inline int R(int r){return r<<1|1;};
inline int MID(int l,int r){return (l+r)>>1;};
struct node{
  int l,r;
  int ls,rs,ms;//左段开始最大连续区间，右端开始最大连续区间，节点区间内最大连续区间
}tree[maxx<<2];
void buildtree(int root,int l,int r){
   tree[root].l=l;
   tree[root].r=r;
   tree[root].ls=(r-l+1);
   tree[root].rs=(r-l+1);
   tree[root].ms=(r-l+1);
   if(l==r){
      return;
   }
   int mid=MID(l,r);
   buildtree(L(root),l,mid);
   buildtree(R(root),mid+1,r);
}
void update(int root,int t,int op){
   int l=tree[root].l;
   int r=tree[root].r;
   if(l==r)//到叶节点
   {
       if (op==0){//如果是销毁操作
       tree[root].ls=tree[root].rs=tree[root].ms=0;
       }else{
       tree[root].ls=tree[root].rs=tree[root].ms=1;//恢复
       }
       return;
   }
    int mid=MID(l,r);
    if (t<=mid){
        update(L(root),t,op);
    }else{
        update(R(root),t,op);
    }
    tree[root].ls=tree[L(root)].ls;//把左儿子节点的左连续传给父亲节点
    tree[root].rs=tree[R(root)].rs;//把右儿子节点的右连续传给父亲节点
    tree[root].ms=max(max(tree[L(root)].ms,tree[R(root)].ms),tree[L(root)].rs+tree[R(root)].ls);
    //父亲节点区间内的最大连续是由三部分构成，左右儿子的最大连续，以及左儿子的最大右连续加上右儿子的最大左连续
    if (tree[L(root)].ls == tree[L(root)].r-tree[L(root)].l+1)//如果左儿子区间满了，
        tree[root].ls+=tree[R(root)].ls;//节点的左连续应该加上右儿子的左连续
    if (tree[R(root)].rs == tree[R(root)].r-tree[R(root)].l+1)//同理右儿子节点满了
        tree[root].rs+=tree[L(root)].rs;//节点的右连续应该加上左儿子的右连续
}
int query(int root,int t)
{
    int l=tree[root].l;
    int r=tree[root].r;
    if(l==r || tree[root].ms == 0 || tree[root].ms==r-l+1){
        //到达一个叶子节点//或者里面全是呗摧毁的点//或者是区间已满的点
        return tree[root].ms;
    }
    int mid=MID(l,r);
    if (t<=mid)
    {
        if(t>=tree[L(root)].r-tree[L(root)].rs+1)//t节点在看左子树，tree[2*i].r-tree[2*i].rs+1代表左子树右边连续区间的左边界值，如果t在左子树的右区间内，则要看右子树的左区间有多长并返回
           return query(L(root),t)+query(R(root),mid+1);
     else
        query(L(root),t);//如果不在左子树的右边界内，则只需要看左子树
    }else
    {
        if (t<=tree[R(root)].l+tree[R(root)].ls-1)//看右子树的左连续的右边界，如果t在在这个范围内，需要再次访问其从左儿子右边界开始的右连续从mid开始
            return query(R(root),t)+query(L(root),mid);
        else
            return query(R(root),t);
    }
}
int main(){
  int n,m;
  while(~scanf("%d%d",&n,&m)){
      buildtree(1,1,n);
      char op;
      int tmp;
      int top;
      while(m--){
         scanf(" %c",&op);
         if (op=='D'){
            scanf("%d",&tmp);
           s[top++]=tmp;
           update(1,tmp,0);
         }else if(op=='Q'){
             scanf("%d",&tmp);
             printf("%d\n",query(1,tmp));
          }else
          {
              if(tmp>0)
              {
                  tmp=s[--top];
                  update(1,tmp,1);
              }
          }
      }
  }
  return 0;
}