HDu 2871 Memory Control(線分ツリーの各種操作&Splay解法)

12554 ワード
vector インテグ Build each out put Training
Memory Control
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2043    Accepted Submission(s): 480
Problem Description
Memory units are numbered from 1 up to N.
A sequence of memory units is called a memory block. 
The memory control system we consider now has four kinds of operations:
1.  Reset Reset all memory units free.
2.  New x Allocate a memory block consisted of x continuous free memory units with the least start number
3.  Free x Release the memory block which includes unit x
4.  Get x Return the start number of the xth memory block(Note that we count the memory blocks allocated from left to right)
Where 1<=x<=N.You are request to find out the output for M operations. 
 
Input
Input contains multiple cases.
Each test case starts with two integer N,M(1<=N,M<=50000) ,indicating that there are N units of memory and M operations.
Follow by M lines,each line contains one operation as describe above.
 
Output
For each “Reset” operation, output “Reset Now”.
For each “New” operation, if it’s possible to allocate a memory block,
output “New at A”,where Ais the least start number,otherwise output “Reject New”.
For each “Free” operation, if it’s possible to find a memory block occupy unit x,
output “Free from A to B”,where A and B refer to the start and end number of the memory block,otherwise output “Reject Free”.
For each “Get” operation, if it’s possible to find the xth memory blocks,
output “Get at A”,where A is its start number,otherwise output “Reject Get”.
Output one blank line after each test case.
 
Sample Input 

   
   
   
   

    
    
    
    6 10
New 2
New 5
New 2
New 2
Free 3
Get 1
Get 2
Get 3
Free 3
Reset

 
Sample Output 

   
   
   
   

    
    
    
    New at 1
Reject New
New at 3
New at 5 
Free from 3 to 4
Get at 1
Get at 5
Reject Get
Reject Free
Reset Now

 
Source
2009 Multi-University Training Contest 7 - Host by FZU
 
Recommend
gaojie
 
タイトル:http://acm.hdu.edu.cn/showproblem.php?pid=2871
标题:メモリ制御をシミュレートして、連続x個の空間を申請したり、番号の最小の位置を返したり、xユニットを含む空間全体を空にしたり、空間の頭と尾を返したり、左から右までのx番目の空間を取得したり、メモリ全体を空にリセットしたりすることができます..
分析:申請空間と解放空間は、この問題とよく似ていて、申請時に上書きされたものをどのidに上書きされたかに変更し、このidの頭と尾を配列して記録し、解放時に上書きされたidを見つけることができ、さらに頭と尾を探して、メモリをリセットすることは実はメモリ全体を解放することです.関数をたくさん書く必要はありません...x番目の空間を探すのは面倒で、もし別の線分の木を開いて統計するならば、私はたくさん書きたいと思って、単点の更新とセグメントのクリア、遅延マークでいいですが、私は最後に直接書くことを選んで、これは2つの遅延マークがあって、1つの記録が累積するかどうか、1つの記録がクリアするかどうか、もちろん、クリアするときは累積マークもクリアします...
最初はクリアマークが少なくなり、クリアとアキュムレータを混ぜてしまいましたが、何度もwaしてしまいましたね...どうせ書くのが面倒だから、2本の線分樹にすればいいのかもしれないが、最初は2本の線分樹だと思っていたので、朝急に1本==と書きたくなったが、他の人はvectorで記録しているようだ...あまり使われていません
2012-10-7:
この問題はsplayでやって、まるで自虐ですね.一晩中デバッグしました.の
実は考え方は線分の木のあれらの標識をそのまま運んで、残りはsplayの更新操作の境界の処理が比較的に面倒で、普通はすべて最大と最小の2つのノードを加えて境界を無視して、しかしこのようにして更に多くの面倒なT_を招くようですT
どうせ私は転勤して死んだ...400++ms过ぎて、コードは大きく挫折して、多く言いたくなくて、疲れて、具体的にコードを见て、とても分かりやすいです
コード:
#include<cstdio>
#include<iostream>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define uprt rt,m-l+1,r-m
using namespace std;
const int mm=55555;
const int mn=mm<<2;
int dly[mn],add[mn],clr[mn],sum[mn],ml[mn],lm[mn],rm[mn];
int sl[mm],sr[mm];
void set(int rt,int id,int len)
{
    ml[rt]=lm[rt]=rm[rt]=id?0:len;
    if(!id)sum[rt]=add[rt]=0,clr[rt]=1;
    dly[rt]=id;
}
void pushdown(int rt,int l1,int l2)
{
    if(dly[rt]>-1)
    {
        set(rt<<1,dly[rt],l1);
        set(rt<<1|1,dly[rt],l2);
        dly[rt]=-1;
    }
    if(clr[rt])
    {
        sum[rt<<1]=sum[rt<<1|1]=add[rt<<1]=add[rt<<1|1]=0;
        clr[rt<<1]=clr[rt<<1|1]=1;
        clr[rt]=0;
    }
    if(add[rt])
    {
        ++sum[rt<<1],add[rt<<1]=1;
        add[rt]=0;
    }
}
void pushup(int rt,int l1,int l2)
{
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
    ml[rt]=max(rm[rt<<1]+lm[rt<<1|1],max(ml[rt<<1],ml[rt<<1|1]));
    lm[rt]=lm[rt<<1],rm[rt]=rm[rt<<1|1];
    if(lm[rt]>=l1)lm[rt]+=lm[rt<<1|1];
    if(rm[rt]>=l2)rm[rt]+=rm[rt<<1];
}
void build(int l,int r,int rt)
{
    dly[rt]=-1,clr[rt]=add[rt]=sum[rt]=0;
    ml[rt]=lm[rt]=rm[rt]=r-l+1;
    if(l==r)return;
    int m=(l+r)>>1;
    build(lson);
    build(rson);
}
void updata(int L,int R,int id,int l,int r,int rt)
{
    if(L<=l&&R>=r)
    {
        set(rt,id,r-l+1);
        if(id&&L==l)++sum[rt],add[rt]=1;
        return;
    }
    int m=(l+r)>>1;
    pushdown(uprt);
    if(L<=m)updata(L,R,id,lson);
    if(R>m)updata(L,R,id,rson);
    pushup(uprt);
}
int NEW(int x,int l,int r,int rt)
{
    if(lm[rt]>=x)return l;
    int m=(l+r)>>1,ret;
    pushdown(uprt);
    if(ml[rt<<1]>=x)ret=NEW(x,lson);
    else if(rm[rt<<1]+lm[rt<<1|1]>=x)ret=m-rm[rt<<1]+1;
    else ret=NEW(x,rson);
    pushup(uprt);
    return ret;
}
int FREE(int x,int l,int r,int rt)
{
    if(dly[rt]>-1)return dly[rt];
    if(l==r)return 0;
    int m=(l+r)>>1,ret;
    pushdown(uprt);
    if(x<=m)ret=FREE(x,lson);
    else ret=FREE(x,rson);
    pushup(uprt);
    return ret;
}
int GET(int x,int l,int r,int rt)
{
    if(l==r)return l;
    int m=(l+r)>>1,ret;
    pushdown(uprt);
    if(sum[rt<<1]>=x)ret=GET(x,lson);
    else ret=GET(x-sum[rt<<1],rson);
    pushup(uprt);
    return ret;
}
int main()
{
    int x,n,m,top;
    char op[55];
    while(~scanf("%d%d",&n,&m))
    {
        build(1,n,1);
        top=0;
        while(m--)
        {
            scanf("%s",op);
            if(op[0]=='R')
            {
                updata(1,n,0,1,n,1);
                puts("Reset Now");
            }
            else scanf("%d",&x);
            if(op[0]=='N')
            {
                if(ml[1]>=x)
                {
                    ++top;
                    sl[top]=NEW(x,1,n,1);
                    sr[top]=sl[top]+x-1;
                    updata(sl[top],sr[top],top,1,n,1);
                    printf("New at %d
",sl[top]);
                }
                else puts("Reject New");
            }
            if(op[0]=='F')
            {
                x=FREE(x,1,n,1);
                if(x)
                {
                    updata(sl[x],sr[x],0,1,n,1);
                    printf("Free from %d to %d
",sl[x],sr[x]);
                }
                else puts("Reject Free");
            }
            if(op[0]=='G')
            {
                if(sum[1]>=x)printf("Get at %d
",GET(x,1,n,1));
                else puts("Reject Get");
            }
        }
        puts("");
    }
    return 0;
}

splayコード:
#include<cstdio>
#include<iostream>
using namespace std;
const int mm=55555;
int l[mm],r[mm];
struct SplayTree
{
    int son[mm][2],far[mm],num[mm],val[mm],len[mm],blk[mm],ll[mm],rl[mm],lv[mm],rv[mm],dly[mm];
    int rt,size,col;
    void Link(int x,int y,int c)
    {
        far[x]=y,son[y][c]=x;
    }
    void Rotate(int x,int c)
    {
        int y=far[x];
        PushDown(y);
        PushDown(x);
        Link(x,far[y],son[far[y]][1]==y);
        Link(son[x][!c],y,c);
        Link(y,x,!c);
        PushUp(y);
    }
    void Splay(int x,int g)
    {
        for(PushDown(x);far[x]!=g;)
        {
            int y=far[x],cx=son[y][1]==x,cy=son[far[y]][1]==y;
            if(far[y]==g)Rotate(x,cx);
            else
            {
                if(cx==cy)Rotate(y,cy);
                else Rotate(x,cx);
                Rotate(x,cy);
            }
        }
        PushUp(x);
        if(!g)rt=x;
    }
    int Select(int k,int g)
    {
        int x=rt;
        PushDown(x);
        while(num[son[x][0]]!=k)
        {
            if(num[son[x][0]]>k)x=son[x][0];
            else k-=num[son[x][0]]+1,x=son[x][1];
            PushDown(x);
        }
        Splay(x,g);
        return x;
    }
    void NewNode(int y,int &x)
    {
        x=++size;
        far[x]=y,num[x]=1,ll[x]=rl[x]=len[x]=1;
        blk[x]=lv[x]=rv[x]=val[x]=dly[x]=son[x][0]=son[x][1]=0;
    }
    void Make(int l,int r,int &x,int y)
    {
        if(l>r)return;
        int m=(l+r)>>1;
        NewNode(y,x);
        Make(l,m-1,son[x][0],x);
        Make(m+1,r,son[x][1],x);
        PushUp(x);
    }
    void Prepare(int n)
    {
        NewNode(size=0,rt);
        NewNode(rt,son[rt][1]);
        val[1]=val[2]=-1,len[1]=len[2]=0;
        lv[1]=rv[1]=lv[2]=rv[2]=0;
        col=ll[1]=rl[1]=ll[2]=rl[2]=0;
        Make(1,n,son[2][0],2);
        Splay(2,0);
    }
    void Check(int x,int d)
    {
        if(!x)return;
        dly[x]=d;
        len[x]=ll[x]=rl[x]=(d<0)*num[x];
        val[x]=lv[x]=rv[x]=d>0?d:0;
        blk[x]=d>0;
    }
    void PushDown(int x)
    {
        if(!dly[x])return;
        Check(son[x][0],dly[x]);
        Check(son[x][1],dly[x]);
        dly[x]=0;
    }
    void PushUp(int x)
    {
        int a=son[x][0],b=son[x][1];
        num[x]=1+num[a]+num[b];
        len[x]=max(len[a],len[b]);
        blk[x]=blk[a]+blk[b];
        if(rv[a]&&rv[a]==lv[b])--blk[x];
        ll[x]=ll[a],rl[x]=rl[b];
        lv[x]=a>2?lv[a]:val[x],rv[x]=b>2?rv[b]:val[x];
        if(!val[x])
        {
            len[x]=max(len[x],rl[a]+ll[b]+1);
            if(len[a]>=num[a])ll[x]+=ll[b]+1;
            if(len[b]>=num[b])rl[x]+=rl[a]+1;
        }
        else if(x>2&&val[x]!=rv[a]&&val[x]!=lv[b])++blk[x];
    }
    void NEW(int a)
    {
        if(len[rt]<a)
        {
            puts("Reject New");
            return;
        }
        int x=rt,y,b=a,p=0;
        PushDown(x);
        while(x)
        {
            if(len[son[x][0]]>=b)x=son[x][0];
            else if(rl[son[x][0]]+!val[x]==b)break;
            else
            {
                if(!val[x]&&rl[son[x][0]]+ll[son[x][1]]+1>=b)b-=rl[son[x][0]]+1;
                p+=num[son[x][0]]+1,x=son[x][1];
            }
            PushDown(x);
        }
        p+=num[son[x][0]]-a+1;
        x=Select(p-1,0);
        y=Select(p+a,rt);
        Check(son[y][0],++col);
        Splay(y,0);
        l[col]=p,r[col]=p+a-1;
        printf("New at %d
",p);
    }
    void FREE(int x)
    {
        x=Select(x,0);
        if(val[x])
        {
            int t=val[x];
            Select(l[t]-1,0);
            int y=Select(r[t]+1,rt);
            Check(son[y][0],-1);
            Splay(y,0);
            printf("Free from %d to %d
",l[t],r[t]);
        }
        else puts("Reject Free");
    }
    void GET(int a)
    {
        if(a>blk[rt])
        {
            puts("Reject Get");
            return;
        }
        int x=rt,y;
        PushDown(x);
        while(x)
        {
            y=son[x][0];
            if(blk[y]>=a)x=y;
            else if(x>2&&val[x]&&val[x]!=rv[y]&&blk[y]+1==a)break;
            else
            {
                a-=blk[y];
                if(x>2&&val[x])
                {
                    if(val[x]!=rv[y]&&val[x]!=lv[son[x][1]])--a;
                    if(val[x]==rv[y]&&val[x]==lv[son[x][1]])++a;
                }
                x=son[x][1];
            }
            PushDown(x);
        }
        Splay(x,0);
        printf("Get at %d
",l[val[x]]);
    }
    void Reset()
    {
        Splay(1,0);
        Splay(2,1);
        Check(son[2][0],-1);
        Splay(2,0);
        puts("Reset Now");
    }
}spt;
int i,n,m;
char op[22];
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        spt.Prepare(n);
        while(m--)
        {
            scanf("%s",op);
            if(op[0]!='R')scanf("%d",&i);
            if(op[0]=='N')spt.NEW(i);
            if(op[0]=='F')spt.FREE(i);
            if(op[0]=='G')spt.GET(i);
            if(op[0]=='R')spt.Reset();
        }
        puts("");
    }
    return 0;
}
2021年版Let's EncryptでのSSL証明書の発行方法/SSL化の方法
JAVAでファイルの文字化けしを読み取る解決策