频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
poj 1823 Hotel 线段树,注意懒惰标记,不标记就会超时滴
2012-07-30 14:09:23           
收藏   我要投稿

[cpp] 
这题就491个accepted,还挺吓人的,别被吓住哈,其实我被吓住了,嘻嘻,这泥玛做也是悲剧,但看分类上说属于中等题,我就猛憋一股气,三A ,呵呵 
这个题我们这需要在线段上用ml,mr,len表示左面有几个连续空位,右面有几个连续空位,中间有几个连续空位
在和并的时候注意更新规则
[cpp]
a[i].len=max(a[i*2].mr+a[i*2+1].ml,max(a[i*2].len,a[i*2+1].len));//这个好想 更新中间len的值 
    if(a[i*2+1].ml==(a[i*2+1].r-a[i*2+1].l+1))//如果右面孩子的ml=线段长度,也就是说右面孩子是全空的,那a[i].ml就是a[i*2].mr+右边整个长度 
        a[i].mr=a[i*2].mr+a[i*2+1].ml; 
    else 
        a[i].mr=a[i*2+1].mr;//如果说右面孩子是不是全空的,那a[i].mr久等于a[i*2+1].mr 
    if(a[i*2].mr==(a[i*2].r-a[i*2].l+1))//同上 
        a[i].ml=a[i*2+1].ml+a[i*2].mr; 
    else 
        a[i].ml=a[i*2].ml;// 

还有就是懒惰标记啦,不标记就超时啦
[cpp]
#include<iostream> 
#include<cstdio> 
using namespace std; 
#define N 16005 
struct node{ 
    int l,r,ml,mr,mm,len,sign; 
}a[N*4]; 
void build(int i,int left,int right){ 
    a[i].l=left; 
    a[i].r=right; 
    a[i].len=a[i].ml=a[i].mr=right-left+1; 
    a[i].mm=0; 
    a[i].sign=0;//表示这条边是否被用过 
    if(left==right) return ; 
    int mid=(a[i].l+a[i].r)>>1; 
    build(i*2,left,mid); 
    build(i*2+1,mid+1,right); 

void insert(int i,int left,int right,int sign){ 
//    cout<<a[i].l<<" "<<a[i].r<<"****"<<left<<" "<<right<<endl; 
    if(a[i].l>=left&&a[i].r<=right){ 
        a[i].sign=1; 
        if(sign==1){ 
            a[i].len=a[i].ml=a[i].mr=0; 
        }else{ 
            a[i].len=a[i].ml=a[i].mr=(a[i].r-a[i].l+1); 
        } 
        return ; 
    } 
    if(a[i].sign==1&&a[i].ml==0&&a[i].mr==0&&a[i].len==0){//懒惰标记 
        a[i*2+1].ml=a[i*2+1].mr=a[i*2+1].len=0; 
        a[i*2].ml=a[i*2].mr=a[i*2].len=0; 
        a[i*2+1].sign=a[i*2].sign=1; 
        a[i].sign=0; 
    } 
    if(a[i].sign==1&&a[i].ml==(a[i].r-a[i].l+1)&&a[i].mr==(a[i].r-a[i].l+1)&&a[i].len==(a[i].r-a[i].l+1)){//懒惰标记 
        a[i*2+1].ml=a[i*2+1].mr=a[i*2+1].len=(a[i*2+1].r-a[i*2+1].l+1); 
        a[i*2].ml=a[i*2].mr=a[i*2].len=(a[i*2].r-a[i*2].l+1); 
        a[i*2+1].sign=a[i*2].sign=1; 
        a[i].sign=0; 
    } 
    int mid=(a[i].l+a[i].r)>>1; 
    if(right<=mid) insert(i*2,left,right,sign); 
    else if(left>mid) insert(i*2+1,left,right,sign); 
    else{ 
        insert(i*2,left,mid,sign); 
        insert(i*2+1,mid+1,right,sign); 
    } 
    a[i].len=max(a[i*2].mr+a[i*2+1].ml,max(a[i*2].len,a[i*2+1].len)); 
    if(a[i*2+1].ml==(a[i*2+1].r-a[i*2+1].l+1)) 
        a[i].mr=a[i*2].mr+a[i*2+1].ml; 
    else 
        a[i].mr=a[i*2+1].mr; 
    if(a[i*2].mr==(a[i*2].r-a[i*2].l+1)) 
        a[i].ml=a[i*2+1].ml+a[i*2].mr; 
    else 
        a[i].ml=a[i*2].ml; 
 //   cout<<"l="<<a[i].l<<" r="<<a[i].r<<" "<<a[i].ml<<" "<<a[i].len<<" "<<a[i].mr<<endl; 

 
int main(){ 
    int n,p,m,x,y; 
    while(~scanf("%d%d",&n,&p)){ 
        build(1,1,n); 
        while(p--){ 
            scanf("%d",&m); 
            if(m==1){ 
                scanf("%d%d",&x,&y); 
//                cout<<"x+y-1="<<x+y-1<<endl; 
                insert(1,x,x+y-1,1); 
            }else if(m==2){ 
                scanf("%d%d",&x,&y); 
                insert(1,x,x+y-1,0); 
            } 
            else 
            printf("%d\n",max(a[1].ml,max(a[1].len,a[1].mr))); 
        } 
 
    } 


作者:youngyangyang04
点击复制链接 与好友分享!回本站首页
相关TAG标签 标记 线段
上一篇:poj 1051-P,MTHBGWB-Greater New York 2001
下一篇:分割平面问题
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站