HDU 1540 Tunnel Warfare（线段树区间合并）

题意：

现在有n个点，要进行一些操作，第一种是破坏某个点，第二个询问某个点所处的最长连续没破坏的区间长度，第三种修复最后一个被破坏的点

思路：

简单的区间合并
对于破坏和修复，是简单的单点修改，因为要修复最后一个，可以维护一个栈来方便记录一下，那么这个题需要思考的地方就只有怎么想最大区间了，我们可以这么想，如果这个点存在于我左右儿子的交界处，那么就可以直接输出这段的长度，否则，我们就要看这个点是处于我左儿子还是右儿子，因为它只可能属于左儿子或者右儿子或者中间，这样我们就可以递归地去找了
我的代码有个地方写的不好，就是每次进行完应该是要把栈pop空的，这个题数据不没卡这个地方，我没pop也AC了

错误及反思：

注意多组。。。

代码：

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<stack>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int N =50100;
int lsum[N<<2],rsum[N<<2],msum[N<<2];
int n,k,t;
stack<int> bef;
void pushup(int l,int r,int rt)
{
    int m=(l+r)/2;
    lsum[rt]=lsum[rt<<1];
    rsum[rt]=rsum[rt<<1|1];
    if(lsum[rt<<1]==m-l+1) lsum[rt]+=lsum[rt<<1|1];
    if(rsum[rt<<1|1]==r-m) rsum[rt]+=rsum[rt<<1];
    msum[rt]=max(lsum[rt<<1|1]+rsum[rt<<1],max(msum[rt<<1],msum[rt<<1|1]));
}
void build(int l,int r,int rt)
{
    if(l==r)
    {
        lsum[rt]=rsum[rt]=msum[rt]=1;
        return ;
    }
    int m=(l+r)/2;
    build(lson);
    build(rson);
    pushup(l,r,rt);
}
void update(int p,int v,int l,int r,int rt)
{
    if(l==r&&l==p)
    {
        lsum[rt]=rsum[rt]=msum[rt]=v;
        return ;
    }
    int m=(l+r)/2;
    if(p<=m) update(p,v,lson);
    else update(p,v,rson);
    pushup(l,r,rt);
    return ;
}
int query(int p,int l,int r,int rt)
{
    if(msum[rt]==r-l+1||msum[rt]==0||l==r)
        return msum[rt];
    int m=(l+r)/2;
    if(p<=m)
    {
        if(m-rsum[rt<<1]+1<=p) return rsum[rt<<1]+lsum[rt<<1|1];
        return query(p,lson);
    }
    else
    {
        if(m+lsum[rt<<1|1]>=p) return lsum[rt<<1|1]+rsum[rt<<1];
        return query(p,rson);
    }
}
int main()
{
    while(scanf("%d%d",&n,&k)!=EOF){
        build(1,n,1);
        while(k--)
        {
            char temp[10];
            scanf("%s",temp);
            if(temp[0]=='D')
            {
                scanf("%d",&t);
                update(t,0,1,n,1);
                bef.push(t);
            }
            else if(temp[0]=='R'){
                if(bef.size()){
                    update(bef.top(),1,1,n,1);
                    bef.pop();
                }
            }
            else
            {
                scanf("%d",&t);
                printf("%d\n",query(t,1,n,1));
            }   
        }
    }
}