HDU1540(Tunnel Warfare )

链接：https://vjudge.net/problem/HDU-1540
思路：这个题真的想透我感觉能明白线段树很多本质，首先我们要思考区间合并信息时我们需要什么，因为是左区间的右端点和右区间的左端点进行合并，所以我们需要记录左区间的最大长度和右区间的最大长度，再维护一个当前区间的最大长度用于求合并的最大长度(合并后的最大长度可能是左右区间中某一个不含端点的区间)，合并的时候注意判断。因为是单点更新，我们考虑直接更新到叶节点，查询的时候我们考虑对于需要查询的点，往左右两个区间转移，如果在左子树且在右区间范围，那么结果就是左子树的右区间长度+右子树的左区间长度，如果在左子树但是不在其右区间范围内，那么查询左子树，如果在右子树同理可推(在这里wa了两个小时，我直接查询的左右区间，这样当查询点不在当前区间内也会有返回值)。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<stack>
using namespace std;

const int maxn = 1e5+10;
int sum[maxn<<2],ll[maxn<<2],rr[maxn<<2];
int n,q;

inline void pushup(int o,int m){//判断各种合并情况
    if(ll[o<<1]==(m-(m>>1)))ll[o] = ll[o<<1] + ll[o<<1|1];
    else ll[o] = ll[o<<1];
    if(rr[o<<1|1]==(m>>1))rr[o] = rr[o<<1|1] + rr[o<<1];
    else rr[o] = rr[o<<1|1];
    sum[o] = max(max(sum[o<<1],sum[o<<1|1]),rr[o<<1]+ll[o<<1|1]);
}

void build(int o,int l,int r){
  if(l<r){
    int mid = l+r>>1;
    build(o<<1,l,mid);
    build(o<<1|1,mid+1,r);
    pushup(o,r-l+1);
  }
  else{
    sum[o] = 1;
    ll[o] = 1;
    rr[o] = 1;
  }
}

void destroy(int o,int tl,int tr,int v){
    if(v<tl||v>tr)return;
  if(tl==tr){
      ll[o] = 0;
      rr[o] = 0;
      sum[o] = 0;
      return ;
  }
  int mid = (tl+tr)>>1;
  destroy(o<<1,tl,mid,v);
  destroy(o<<1|1,mid+1,tr,v);
  pushup(o,tr-tl+1);
} 

void rebuild(int o,int tl,int tr,int v){
     if(v<tl||v>tr)return;
    if(tl==tr){
      ll[o] = 1;
      rr[o] = 1;
      sum[o] = 1;
      return ;
  }
  int mid = (tl+tr)>>1;
  rebuild(o<<1,tl,mid,v);
  rebuild(o<<1|1,mid+1,tr,v);
  pushup(o,tr-tl+1);
}

int query(int o,int tl,int tr,int v){
  if(sum[o]==tr-tl+1||sum[o]==0||tr==tl)return sum[o];
  int mid = (tl+tr)>>1;
  if(v<=mid){
      if(v>=mid-rr[o<<1]+1)return rr[o<<1]+ll[o<<1|1];
      else return query(o<<1,tl,mid,v);
  }
  else{
      if(v<=mid+ll[o<<1|1])return rr[o<<1]+ll[o<<1|1];
      else return query(o<<1|1,mid+1,tr,v);
  }
}

stack<int> s;
char ch[10];

int main(){ 
    while(~scanf("%d%d",&n,&q)){
        while(!s.empty())s.pop();
        memset(sum,0,sizeof(sum));
        memset(ll,0,sizeof(ll));
        memset(rr,0,sizeof(rr));
        build(1,1,n);
    for(int i=0;i<q;i++){
        int o;
        scanf("%s",ch);
        if(ch[0]=='D'){
            scanf("%d",&o);
            destroy(1,1,n,o);
            s.push(o);
        }
        if(ch[0]=='R'){
            if(!s.empty()){
            int p = s.top();
            s.pop();
            rebuild(1,1,n,p);
            }
        }
        if(ch[0]=='Q'){
            scanf("%d",&o);
            printf("%d\n",query(1,1,n,o));
        }
    }
    }
    return  0;
}