HDU-1540-Tunnel Warfare(线段树的区间合并

Tunnel Warfare

思路：

• 这明明是单点查询，怎么说是区间合并呢？试问一下，题目要求是不是输出当前点连续的长度呢！！！

• 单点查询如何转换成区间查询？这就是题目的巧妙之处，查询的时候，在整个区间缩小为一个点的过程中，判断目标点是否在当前区间的连续区间内，如果在，我们再查询该连续区间的端点。（相当于感染）这样就可以查找到目标点所在的连续区间。

• 说的简单一点就是当前的点属于哪个较长的区间,这就不成区间查询了
  

  

• 首先是建树，在结构体里定义ls记录该区间左端点的最大连续个数，rs记录区间右端点开始的最大连续个数，ms表示该区间最大的连续个数。

#include<bits/stdc++.h>
using namespace std;
const int M=55000;
stack<int>s;
struct node
{
    int l,r;
    int ls,rs,ms;//ls从l开始左边最大连续，rs从r开始右边最大连续，整个l-s最长连续
} tree[M<<2];
void pushup(int root)
{
    tree[root].ls=tree[root<<1].ls;//左连续
    tree[root].rs=tree[root<<1|1].rs;//右连续
    tree[root].ms=max(max(tree[root<<1].ms,tree[root<<1|1].ms),tree[root<<1].rs+tree[root<<1|1].ls);
    //父亲区间内的最大区间必定是，左子树最大区间，右子树最大区间，左右子树连续区间合并的中间区间，三者中最大的区间值
    if(tree[root<<1].ls==tree[root<<1].r-tree[root<<1].l+1)//说明左子树全部连续
    {
        tree[root].ls+=tree[root<<1|1].ls;//左子树区间满了的话，父亲左区间要加上右子树的左连续
    }
    if(tree[root<<1|1].rs==tree[root<<1|1].r-tree[root<<1|1].l+1)//说明右子树全部连续
    {
        tree[root].rs+=tree[root<<1].rs;//右子树区间满了的话，父亲右区间就要加上左子树的右连续
    }
}
void build(int l,int r,int root)
{
    tree[root].l=l;
    tree[root].r=r;
    tree[root].ls=tree[root].rs=tree[root].ms=r-l+1;
    if(l!=r)
    {
        int mid=(l+r)>>1;
        build(l,mid,root<<1);
        build(mid+1,r,root<<1|1);
    }
}
// void print(int l,int r,int root)
// {
//     if(l==r)
//     {
//         printf("%d l %d\n",l,tree[root].ms);
//         return ;
//     }
//     int mid=(l+r)>>1;
//     print(l,mid,root<<1);
//     print(mid+1,r,root<<1|1);
// }
void update(int root,int pos,int flag)
{
    if(tree[root].l==tree[root].r)
    {
        if(flag==1)
        {
            tree[root].ls=tree[root].rs=tree[root].ms=1;//修复
        }
        else
        {
            tree[root].ls=tree[root].rs=tree[root].ms=0;//摧毁
        }
        return ;
    }
    int mid=(tree[root].l+tree[root].r)>>1;
    if(pos<=mid)
    {
        update(root<<1,pos,flag);
    }
    else
    {
        update(root<<1|1,pos,flag);
    }
    pushup(root);
}
int query(int root,int pos)
{
    if(tree[root].l==tree[root].r||tree[root].ms==0||tree[root].ms==tree[root].r-tree[root].l+1)
    {
        return tree[root].ms;//到了叶子节点或者该访问区间为空或者已满都不必要往下走了
    }
    int mid=(tree[root].l+tree[root].r)>>1;
    if(pos<=mid)
    {
        if(pos>=tree[root<<1].r-tree[root<<1].rs+1)//因为pos<=mid，看左子树，tree[root<<1].r-tree[root<<1].rs+1代表左子树右连续区间的左边界值，如果pos在左子树的右连续内，则要看右子树的左连续有多长并返回
        {
            return query(root<<1,pos)+query(root<<1|1,mid+1);
        }
        else
        {
            return query(root<<1,pos);//如果不在左子树的右连续区间内，则只需要看左子树
        }
    }
    else
    {
        if(pos<=tree[root<<1|1].l+tree[root<<1|1].ls-1)//因为pos>mid，看右子树,tree[root<1|1].l+tree[root<<1|1].ls-1代表右子树左连续区间的右边界值，如果pos在右子树的左连续内，则要看左子树的右连续有多长
        {
            return query(root<<1|1,pos)+query(root<<1,mid);
        }
        else
        {
            return query(root<<1|1,pos);//如果不在右子树的左连续区间内，则只需要看右子树
        }

    }
}
int main( )
{
    int n,q,x;
    char str[2];
    while(~scanf("%d%d",&n,&q))
    {
        while(!s.empty( ))
        {
            s.pop( );
        }
        build(1,n,1);
        //print(1,n,1);
        while(q--)
        {
            cin>>str;
            if(str[0]=='D')
            {
                cin>>x;
                s.push(x);
                update(1,x,0);
                //print(1,n,1);
            }
            if(str[0]=='Q')
            {
                cin>>x;
                cout<<query(1,x)<<endl;
            }
            if(str[0]=='R'&&!s.empty( ))
            {
                x=s.top( );
                s.pop( );
                update(1,x,1);
                //print(1,n,1);
            }

        }

    }
    return 0;
}