The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

HDOJ 2871 Memory Control 经典线段树懒操作

这题有点像Hotel的包装版,非常经典,让我进一步熟悉了线段树的区间操作(主要是延迟标记的使用)。
唯一的问题出在自己写的二分函数上,死活都是TLE,后来参考了小HH的二分才过掉,不知道自己哪写挂了,郁闷。。。。
PS:顺便问一下,高质量的内存管理难道真的是用线段树实现的?
#include<iostream>
#include
<algorithm>
#include
<vector>
using namespace std;

int const maxn=50010;
int n,m;
#define LL(i) (i<<1)
#define RR(i) ((i<<1)|1)
struct node
{
    
int l,r;
    
int cval,lval,rval;
    
int st;
    
int len(){return r-l+1;}
    
void doit()
    
{
        
if(st==1)cval=lval=rval=0;
        
else cval=lval=rval=len();
    }

}
ST[maxn*8];

struct block
{
    
int s,t;
}
;
vector
<block>B;
/*
int Bfind(int x)//返回-1代表没找到
{
    int l=0;
    int r=B.size()-1;
    while(l<=r)
    {

        int mid=(l+r)>>1;
        if(x>=B[mid].s&&x<=B[mid].t)return mid;
        if(x<B[mid].s)r=mid-1;
        else if(x>B[mid].t)l=mid+1;
    }
    return -1;
}


int Infind(int x)//找到插入位置
{
    int l=0;
    int r=B.size()-1;
    int len=B.size();

    while(l<=r)
    {    
        if(x>B[len-1].t)
            return B.size();
        if(x<B[0].s)
            return 0;
        
        int mid=(l+r)>>1;
        if(x>B[mid].t&&x<B[mid+1].s)return mid+1;
        if(x<B[mid].s) r=mid-1;
        else if(x>B[mid].t)l=mid+1;
        
    }
       
}
*/


int Bin(int x) {
    
int lo = 0;
    
int hi =B.size()- 1;
    
while(lo <= hi) {
        
int mid = (lo + hi) >> 1;
        
if(B[mid].s<= x) {
            lo 
= mid + 1;
        }
 else {
            hi 
= mid - 1;
        }

    }

    
return lo;
}

//st为0时代表没覆盖
void Build(int l,int r,int i)
{
    ST[i].st
=0;
    ST[i].l
=l;
    ST[i].r
=r;
    
if(l==r){ST[i].cval=ST[i].lval=ST[i].rval=1;return;}
    
int mid=(ST[i].l+ST[i].r)>>1;
    Build(l,mid,LL(i));
    Build(mid
+1,r,RR(i));
    ST[i].cval
=ST[i].lval=ST[i].rval=ST[i].len();
    
}



void update(int l,int r,int op,int i)
{
    
if(l==ST[i].l&&r==ST[i].r)
    
{
        ST[i].st
=op;
        ST[i].doit();
        
return;
    }

    
if(ST[i].st!=-1)
    
{
        ST[LL(i)].st
=ST[RR(i)].st=ST[i].st;
        ST[LL(i)].doit();
        ST[RR(i)].doit();
        ST[i].st
=-1;
    }

    
int mid=(ST[i].l+ST[i].r)>>1;
    
if(r<=mid)update(l,r,op,LL(i));
    
else if(l>mid)update(l,r,op,RR(i));
    
else{
        update(l,mid,op,LL(i));
        update(mid
+1,r,op,RR(i));
    }

    ST[i].cval
=max(ST[LL(i)].cval,ST[RR(i)].cval);
    ST[i].cval
=max(ST[i].cval,ST[LL(i)].rval+ST[RR(i)].lval);
    
//
    ST[i].lval=ST[LL(i)].lval;
    ST[i].rval
=ST[RR(i)].rval;
    
//
    if(ST[LL(i)].lval==ST[LL(i)].len())
        ST[i].lval
+=ST[RR(i)].lval;
    
if(ST[RR(i)].rval==ST[RR(i)].len())
        ST[i].rval
+=ST[LL(i)].rval;
}



int Query(int w,int i)
{
    
if(ST[i].lval>=w)return ST[i].l;
    
if(ST[i].st!=-1)
    
{
        ST[LL(i)].st
=ST[RR(i)].st=ST[i].st;
        ST[LL(i)].doit();
        ST[RR(i)].doit();
        ST[i].st
=-1;
    }

    
else if(ST[LL(i)].cval>=w)return Query(w,LL(i));
    
else if(ST[LL(i)].rval+ST[RR(i)].lval>=w) return ST[LL(i)].r-ST[LL(i)].rval+1;
    
else if(ST[RR(i)].cval>=w)return Query(w,RR(i));
    
//else if(ST[RR(i)].rval>=w)return ST[RR(i)].r-ST[RR(i)].rval+1; 
    else return 0;
}


int main()
{
    
while(scanf("%d%d",&n,&m)!=EOF)
    
{

        Build(
1,n,1);
        B.clear();
        
for(int i=0;i<m;i++)
        
{
            
char op[9];
            scanf(
"%s",op);
            
if(op[0]=='N')
            
{
            
                
int w;
                scanf(
"%d",&w);
                
if(ST[1].cval<w)
                    puts(
"Reject New");
                
else
                
{
                
                    
//
                    int s=Query(w,1);
                    update(s,s
+w-1,1,1);
                    printf(
"New at %d\n",s);
                    
//
                    block tem;
                    tem.s
=s;
                    tem.t
=s+w-1;
                    
int pos=Bin(s);
                    B.insert(B.begin()
+pos,tem);
                }

            }

            
else if(op[0]=='R')
            
{
                update(
1,n,0,1);
                puts(
"Reset Now");
                B.clear();
            }

            
else if(op[0]=='G')
            
{
                
int x;
                scanf(
"%d",&x);
                
if(x>B.size())
                    puts(
"Reject Get");
                
else
                
{
                    printf(
"Get at %d\n",B[x-1].s);
                }


            }

            
else
            
{
                
int x;

                scanf(
"%d",&x);
                
int t=Bin(x)-1;
                
if(t==-1||B[t].t<x)
                    puts(
"Reject Free");
                
else
                
{
                    printf(
"Free from %d to %d\n",B[t].s,B[t].t);
                    update(B[t].s,B[t].t,
0,1);
                    B.erase(B.begin()
+t,B.begin()+t+1);
                }

            }

        }

        puts(
"");

    }



    
return 0;
}

posted on 2010-10-30 20:00 abilitytao 阅读(1672) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理