当前位置:编程学习 > C/C++ >>

POJ3667[线段树、最大连续区间]

线段树暂时最后一题了吧,线段树果然可以做的很多很多,和DP结合起来对自己的要求更高了。
自己要做的还差很远~
 
这题调试了好长时间。。。
 题意:1a:询问是不是有连续长度为a的空房间,有的话住进最左边
          2a b:将[a,a+b-1]的房间清空
          思路:记录区间中最长的空房间
         线段树操作:update:区间替换query:询问满足条件的最左断点
 
主要难点在于 
void pushup(int rt,int m)
{
    lsum[rt]=lsum[rt<<1];
    rsum[rt]=rsum[rt<<1|1]; //这几步的处理!
    if(lsum[rt]==(m-m/2))
        lsum[rt]+=lsum[rt<<1|1];
    if(rsum[rt]==m/2)
        rsum[rt]+=rsum[rt<<1];
    msum[rt]=max(rsum[rt<<1]+lsum[rt<<1|1],max(msum[rt<<1],msum[rt<<1|1]));
}
 
理解了就好了~
 
顺便自己对pushdown又错了一次,pushdown是传给子孙结点的。
 
 
#include <iostream>  
#include <cstdio>  
#include <cstring>  
  
using namespace std;  
  
#define lson rt<<1,l,m  
#define rson rt<<1|1,m+1,r  
  
const int maxn=50005;  
//经典做法 //msum最大一段连续区间 lsum,rsum从左,右边起最大连续区间  
int cover[maxn<<8],msum[maxn<<8],lsum[maxn<<8],rsum[maxn<<8];  
  
  
void build(int rt,int l,int r)  
{  
    cover[rt]=-1;  
    msum[rt]=lsum[rt]=rsum[rt]=r-l+1;  
    if(l==r) return;  
    int m=(l+r)>>1;  
    build(lson);  
    build(rson);  
}  
void pushdown(int rt,int m) {  
    if (cover[rt] != -1) {  
        cover[rt<<1] = cover[rt<<1|1] = cover[rt];  
        msum[rt<<1] = lsum[rt<<1] = rsum[rt<<1] = cover[rt] ? 0 : m - (m >> 1);  
        msum[rt<<1|1] = lsum[rt<<1|1] = rsum[rt<<1|1] = cover[rt] ? 0 : (m >> 1);  
        cover[rt] = -1;  
    }  
}  
void pushup(int rt,int m)  
{  
    lsum[rt]=lsum[rt<<1];  
    rsum[rt]=rsum[rt<<1|1]; //这几步的处理!  
    if(lsum[rt]==(m-m/2))  
        lsum[rt]+=lsum[rt<<1|1];  
    if(rsum[rt]==m/2)  
        rsum[rt]+=rsum[rt<<1];  
    msum[rt]=max(rsum[rt<<1]+lsum[rt<<1|1],max(msum[rt<<1],msum[rt<<1|1]));  
}  
void update(int ql,int qr,int ch,int rt,int l,int r)  
{  
    if(ql<=l&&qr>=r)  
    {  
        cover[rt]=ch;  
        if(ch==0)  
          msum[rt]=lsum[rt]=rsum[rt]=r-l+1;  
        else if(ch==1)  
          msum[rt]=lsum[rt]=rsum[rt]=0;  
        return;  
    }  
  
    pushdown(rt,r-l+1);  
  
    int m=(l+r)>>1;  
    if(ql<=m)  
        update(ql,qr,ch,lson);  
    if(qr>m)  
        update(ql,qr,ch,rson);  
  
    pushup(rt,r-l+1);  
}  
int query(int ch,int rt,int l,int r)  
{  
    //要返回的是左坐标  
    if(l==r) return l;  
    //呵呵。。。  
    pushdown(rt,r-l+1);  
    int m=(l+r)>>1;  
    if(msum[rt<<1]>=ch)  
        return query(ch,lson);  
    else if((rsum[rt<<1]+lsum[rt<<1|1])>=ch)  
        return m-rsum[rt<<1]+1; //这一步return最为经典  
    else  
        return query(ch,rson);  
}  
  
int main()  
{  
    int n,m,a,b,c;  
    while(scanf("%d%d",&n,&m)!=EOF)  
    {  
        build(1,1,n);  
        for(int i=1;i<=m;i++)  
        {  
            scanf("%d",&a);  
            if(a==1)  
            {  
                scanf("%d",&b);  
                if(msum[1]<b) //利用根结点判断是否有大于b的  
                    printf("0\n");  
                else  
                {  
                    int pos=query(b,1,1,n);  
                    printf("%d\n",pos);  
                    update(pos,pos+b-1,1,1,1,n);  
                }  
            }  
            else  
            {  
                scanf("%d%d",&b,&c);  
                update(b,b+c-1,0,1,1,n);  
            }  
        }  
    }  
    return 0;  
}  

 


补充:软件开发 , C++ ,
CopyRight © 2012 站长网 编程知识问答 www.zzzyk.com All Rights Reserved
部份技术文章来自网络,