频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
poj 3667 Hotel 线段树 内存分配问题
2012-08-06 14:19:46           
收藏   我要投稿
我写这道提真是元气大伤,一开始写完,自己写几组数据都过不了,在网上看别人的解题报告,总是感觉代码太复杂,都不愿意看,还是改自己的吧,后来就有重写的欲望,删了一百多行,在写,有写测试数据的生成程序测,最后又写了一个暴力程序对拍,擦擦!!断断续续的整了两天,现在看自己的代码也很乱,我估计谁也看不进去
我就说一下大概思想吧,用mm表示中间连续最大值 mr表示右边连续 ml表示左边边连续 len表示整个线段连续
都不愿意写了,总之大部分设计 查找和删除都要lazy一下,
鼓励大家坚持自己的做,这种题看别人代码都感觉代码很恶心,看上去很复杂的样子
[cpp] 
#include<iostream> 
#include<cstdio> 
using namespace std; 
#define N 60005 
struct node{ 
    int l,r,ml,mr,mm,len; 
}a[N*4]; 
int n; 
void build(int i,int left,int right){ 
    a[i].l=left; 
    a[i].r=right; 
    a[i].ml=a[i].mr=a[i].mm=a[i].len=(right-left+1); 
    if(left==right) return ; 
    int mid=(left+right)>>1; 
    build(i*2,left,mid); 
    build(i*2+1,mid+1,right); 

int p; 
void lazy(int i){ 
    if(a[i].mr==a[i].r-a[i].l+1&&a[i].l!=a[i].r){ 
         a[i*2].ml=a[i*2].mr=a[i*2].mm=a[i*2].len=(a[i*2].r-a[i*2].l+1); 
         a[i*2+1].ml=a[i*2+1].mr=a[i*2+1].mm=a[i*2+1].len=(a[i*2+1].r-a[i*2+1].l+1); 
    } 
    if(a[i].ml==a[i].mr&&a[i].mr==a[i].mm&&a[i].mr==0){ 
        a[i*2].ml=a[i].ml; 
        a[i*2].mr=a[i].mr; 
        a[i*2].mm=a[i].mm; 
        a[i*2].len=a[i].len; 
        a[i*2+1].ml=a[i].ml; 
        a[i*2+1].mr=a[i].mr; 
        a[i*2+1].mm=a[i].mm; 
        a[i*2+1].len=a[i].len; 
    } 

void deal(int i,int left,int right){ 
    lazy(i); 
    if(a[i].l==left&&a[i].r==right){ 
        a[i].ml=a[i].mr=a[i].mm=a[i].len=0; 
        return ; 
    } 
    int mid=(a[i].l+a[i].r)>>1; 
    if(right<=mid) deal(i*2,left,right); 
    else if(left>mid) deal(i*2+1,left,right); 
    else{ 
 
        deal(i*2,left,mid); 
        deal(i*2+1,mid+1,right); 
    } 
    if(a[i*2].ml==(a[i*2].r-a[i*2].l+1)) 
        a[i].mm=a[i].ml=a[i*2].ml+a[i*2+1].ml; 
    else a[i].ml=a[i*2].ml; 
    if(a[i*2+1].ml==(a[i*2+1].r-a[i*2+1].l+1)) 
            a[i].mm=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].ml!=(a[i*2].r-a[i*2].l+1)&&a[i*2+1].mr!=(a[i*2+1].r-a[i*2+1].l+1)) 
        a[i].mm=max(a[i*2].mr+a[i*2+1].ml,max(a[i*2].mm,a[i*2+1].mm)); 
     a[i].len=max(a[i].mm,max(a[i].ml,a[i].mr)); 

void insert(int i,int k){ 
    lazy(i); 
    if(a[i].len>=k){ 
        if(a[i].ml>=k&&a[i*2].len<k&&a[i*2+1].len<k){ 
            p=a[i].l; 
            deal(1,a[i].l,a[i].l+k-1);//////////////////////////////////// 
             return ; 
        }else if(a[i].mm>=k&&(a[i*2].mr+a[i*2+1].ml>=k)&&a[i*2].len<k){//&&a[i*2+1].len<k 
            int temp=a[i*2].r-a[i*2].mr+1; 
            int tmr=a[i*2].mr; 
            if(a[i*2].mr==0) deal(1,a[i*2].r-a[i*2].mr+1,a[i*2].r+1);///////0///////这个边界文题,当a[i*2].mr==0时要特殊处理 
            else deal(1,a[i*2].r-a[i*2].mr+1,a[i*2].r); 
            deal(1,a[i*2+1].l,a[i*2+1].l+k-tmr-1);//////////////////////////// 
            p=temp; 
             return ; 
 
        }else if(a[i].mr>=k&&a[i*2].len<k&&a[i*2+1].len<k){ 
            int temp=a[i].r-a[i].mr+1; 
            deal(1,a[i].r-a[i].mr+1,a[i].r-a[i].mr+k); 
            p=temp; 
            return ; 
        } 
    } 
    int mid=(a[i].l+a[i].r)>>1; 
    if(a[i*2].len>=k) insert(i*2,k); 
    else if(a[i*2+1].len>=k) insert(i*2+1,k); 

void del(int i,int left,int right){ 
    if(left<1) left=1; 
    if(right>n) right=n; 
    if(a[i].l==left&&a[i].r==right){ 
        a[i].ml=a[i].mr=a[i].mm=a[i].len=(right-left+1); 
        return ; 
    } 
    lazy(i); 
    int mid=(a[i].l+a[i].r)>>1; 
    if(left>mid) del(i*2+1,left,right); 
    else if(right<=mid) del(i*2,left,right); 
    else{ 
        del(i*2,left,mid); 
        del(i*2+1,mid+1,right); 
    } 
    if(a[i*2].ml==(a[i*2].r-a[i*2].l+1)) 
        a[i].mm=a[i].ml=a[i*2].ml+a[i*2+1].ml; 
    else a[i].ml=a[i*2].ml; 
    if(a[i*2+1].ml==(a[i*2+1].r-a[i*2+1].l+1)) 
            a[i].mm=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].ml!=(a[i*2].r-a[i*2].l+1)&&a[i*2+1].mr!=(a[i*2+1].r-a[i*2+1].l+1)) 
        a[i].mm=max(a[i*2].mr+a[i*2+1].ml,max(a[i*2].mm,a[i*2+1].mm)); 
     a[i].len=max(a[i].mm,max(a[i].ml,a[i].mr)); 

int main(){ 
 //   freopen("in.txt","r",stdin); 
    int m,x,y,t; 
    while(~scanf("%d%d",&n,&m)){ 
        build(1,1,n); 
        while(m--){ 
            scanf("%d",&t); 
            if(t==2){ 
                scanf("%d%d",&x,&y); 
                del(1,x,x+y-1); 
            }else{ www.2cto.com
                scanf("%d",&x); 
                p=0; 
                insert(1,x); 
                printf("%d\n",p); 
            } 
        } 
    } 
    return 0; 

作者:youngyangyang04
点击复制链接 与好友分享!回本站首页
相关TAG标签 线段 内存 问题
上一篇:HDOJ 1248 寒冰王座 (完全背包)
下一篇:hdu 3473 Minimum Sum
相关文章
图文推荐
点击排行

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

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