POJ 1823 Hotel 线段树

题意：

一个Hotel有N个房间，一开始全部为空。

接下来有M个询问。

输入1，代表房间被占用，然后输入两个数代表房间被占用的房间号和数量。

输入2，代表房间被置空，输入两个数代表房间被清空的房间号和数量。

输入3，输出连续最长没有被占用的房间数量。

思路：

线段树。。。。。。。。

写了好久，一开始更新节点各种WA，写不出来，参考了一段别人的代码，加上自己的理解，终于A了。

最近做了几道线段树，感觉运用的时候还是要灵活，每个节点变量的更新还得多琢磨一下。

然后是这道题，因为要寻找最长的置空的区间，那么有些置空的区间并不是线段树的节点，这时要更新置空区间的最大值的时候就的把左子树的右值和右子树的左值加起来在比较大小。

    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <string>
    #include <cmath>
    #include <cstring>
    #include <queue>
    #include <set>
    #include <vector>
    #include <stack>
    #include <map>
    #include <iomanip>
    #define PI acos(-1.0)
    #define Max 16005
    #define inf 1<<28
    #define LL(x) (x<<1)
    #define RR(x)(x<<1|1)
    using namespace std;

    int n;
    struct kdq
    {
        int l,r;
        int in;//记录该区间是否被覆盖，0代表未覆盖，1代表部分覆盖，2代表完全覆盖
        int maxl,max,maxr;//记录节点，左边的最大长度maxl，右边的最大长度maxr，和该节点区间的最大长度max
    } tree[Max*4];

    void build_tree(int l,int r,int u)//建树
    {
        tree[u].l=l;
        tree[u].r=r;
        tree[u].in=0;
        if(l==r)
        {
            tree[u].max=tree[u].maxr=tree[u].maxl=1;
            return ;
        }
        int mid=(l+r)/2;
        build_tree(l,mid,LL(u));
        build_tree(mid+1,r,RR(u));
        tree[u].max=tree[u].maxl=tree[u].maxr=tree[LL(u)].max+tree[RR(u)].max;
    }

    void update(int u)//更新节点的最大值
    {
        if(!tree[LL(u)].in)//如果该节点的左子树未被覆盖
            tree[u].maxl=tree[LL(u)].max+tree[RR(u)].maxl;//则该节点左边maxl的最大值为：左子树的最大值加上右子树的左边值
        else
            tree[u].maxl=tree[LL(u)].maxl;//否则该节点的左边值就等于左子树的左边值
        if(!tree[RR(u)].in)//同理更新节点的右值
            tree[u].maxr=tree[LL(u)].maxr+tree[RR(u)].max;
        else
            tree[u].maxr=tree[RR(u)].maxr;
        //下面一步是更新节点的max。
        int maxl=max(tree[u].maxl,tree[u].maxr);//找出节点左右值的最大值。
        int maxm=tree[LL(u)].maxr+tree[RR(u)].maxl;//该节点左子树和右子树中间的值。
        int maxr=max(tree[LL(u)].max,tree[RR(u)].max);//左右子树的最大值
        int maxmax=max(max(maxl,maxm),maxr);
        tree[u].max=maxmax;//更新最大值
        if(tree[LL(u)].in==tree[RR(u)].in)
            tree[u].in=tree[LL(u)].in;
    }
    void insert(int l,int r,int u)//插入
    {
        if(l==tree[u].l&&tree[u].r==r)//如果区间相等
        {
            tree[u].in=2;//则完全覆盖
            tree[u].maxl=tree[u].maxr=tree[u].max=0;//长度为0
            return ;
        }
        if(!tree[u].in)//如果没被覆盖
        {
            tree[u].in=1;
            tree[LL(u)].in=0;
            tree[RR(u)].in=0;
            //更新左右子树的最大值为区间长度
            tree[LL(u)].maxl=tree[LL(u)].maxr=tree[LL(u)].max=tree[LL(u)].r-tree[LL(u)].l+1;
            tree[RR(u)].maxl=tree[RR(u)].max=tree[RR(u)].maxr=tree[RR(u)].r-tree[RR(u)].l+1;
        }
        //向下递归
        int mid=(tree[u].l+tree[u].r)>>1;
        if(r<=mid)
            insert(l,r,LL(u));
        else if(l>mid)
            insert(l,r,RR(u));
        else
        {
            insert(l,mid,LL(u));
            insert(mid+1,r,RR(u));
        }
        update(u);//更新节点的最大值
    }

    void remove(int l,int r,int u)//同插入
    {
        if(l==tree[u].l&&tree[u].r==r)//如果相等
        {
            tree[u].in=0;//则全部移除，为0。
            tree[u].maxl=tree[u].maxr=tree[u].max=tree[u].r-tree[u].l+1;//更新最大值为区间长度
            return ;
        }
        if(tree[u].in==2)//如果该节点被完全覆盖
        {
            tree[u].in=1;
            tree[LL(u)].in=2;
            tree[RR(u)].in=2;
            //更新左右子树的最大值为0.（完全覆盖）
            tree[LL(u)].maxl=tree[LL(u)].max=tree[LL(u)].maxr=0;
            tree[RR(u)].maxl=tree[RR(u)].max=tree[RR(u)].maxr=0;
        }
        //向下递归
        int mid=(tree[u].l+tree[u].r)>>1;
        if(r<=mid)
            remove(l,r,LL(u));
        else if(l>mid)
            remove(l,r,RR(u));
        else
        {
            remove(l,mid,LL(u));
            remove(mid+1,r,RR(u));
        }
        update(u);//更新节点的最大值
    }
    int main()
    {
        int i,j,k,l,n,m;
        scanf("%d%d",&n,&m);
        int a,b;
        build_tree(1,n,1);
        while(m--)
        {
            scanf("%d",&k);
            if(k==1)
            {
                scanf("%d%d",&a,&b);
                insert(a,a+b-1,1);
            }
            else if(k==2)
            {
                scanf("%d%d",&a,&b);
                remove(a,a+b-1,1);
            }
            else
                printf("%d\n",tree[1].max);
        }
        return 0;
    }

。。

更多详细信息请查看java教程网 http://www.itchm.com/forum-59-1.html