poj 3667 Hotel(線分樹区間連結&Splay解法)
Hotel
Time Limit: 3000MS
Memory Limit: 65536K
Total Submissions: 6224
Accepted: 2546
Description
The cows are journeying north to Thunder Bay in Canada to gain cultural enrichment and enjoy a vacation on the sunny shores of Lake Superior. Bessie, ever the competent travel agent, has named the Bullmoose Hotel on famed Cumberland Street as their vacation residence. This immense hotel has N (1 ≤ N ≤ 50,000) rooms all located on the same side of an extremely long hallway (all the better to see the lake, of course).
The cows and other visitors arrive in groups of size Di (1 ≤ Di ≤ N) and approach the front desk to check in. Each group i requests a set of Di contiguous rooms from Canmuu, the moose staffing the counter. He assigns them some set of consecutive room numbers r..r+Di-1 if they are available or, if no contiguous set of rooms is available, politely suggests alternate lodging. Canmuu always chooses the value of r to be the smallest possible.
Visitors also depart the hotel from groups of contiguous rooms. Checkout i has the parameters Xi and Di which specify the vacating of rooms Xi ..Xi +Di-1 (1 ≤ Xi ≤ N-Di+1). Some (or all) of those rooms might be empty before the checkout.
Your job is to assist Canmuu by processing M (1 ≤ M < 50,000) checkin/checkout requests. The hotel is initially unoccupied.
Input
* Line 1: Two space-separated integers: N and M * Lines 2..M+1: Line i+1 contains request expressed as one of two possible formats: (a) Two space separated integers representing a check-in request: 1 and Di (b) Three space-separated integers representing a check-out: 2, Xi, and Di
Output
* Lines 1.....: For each check-in request, output a single line with a single integer r, the first room in the contiguous sequence of rooms to be occupied. If the request cannot be satisfied, output 0.
Sample Input
USACO 2008 February Gold
タイトル:http://poj.org/problem?id=3667
标题:宿には1~nの番号の部屋があり、今はm波人が借家を過ぎている可能性があり、波人ごとに連続したd部屋を予約しなければならない可能性があり、もしあれば番号はできるだけ小さく、なければ0と言い、d人がチェックアウトする可能性もあり、彼らの部屋は連続したx~x+d-1の数部屋である..
解析:この問題はセグメントツリー区間のマージに属しますが、比較的簡単です.のまず、もちろん1つの区間の最も長い連続値を記録しなければなりません.この便利な値を取り、それから1つの区間がどのようにその2つのサブ区間から移行するかを考えなければなりません.この最も長い値は必ず1つの値区間の最も長い値の大きい者を記録することができます.もちろん、2つのサブ区間が合併して、より長いものが得られる可能性があります.このより長い肯定は中間で、左のサブ区間が右端から左端までの最も長い連続値を記録する必要があります.右サブ区間の左端から右端までの最長連続値を記録して、新しい値はこの2つの値を加算して、もちろん、どの区間が左区間なのか分からないので、各区間はこの3つの値を記録しなければなりません.もちろん、遅延フラグもあります.TLEではありませんか.
2012-10-7:
最近はsplayを強化しているので、これまではsplayをどうやって使うか考えていませんでしたが、その時は線分木の遅延マークが分からなかったようで、今日はわざわざ考えてみましたが、実は線分木の遅延マークをそのままそのまま使えばいいのです.
各ノードは5つの値ドメインを維持し、
1.val現在のノードがマークされているかどうか(部屋が占有されている)l
2.dly現在のノードの遅延フラグ3
3.len現在のノードがサブノードを含む最大連続空き部屋
4.ll現在のノードの全体の木は自身が代表する区間を含んで、一番左から、一番長い連続空き部屋
5.rl現在のノードの木全体には、自分が代表する区間が含まれており、最も右から最も長い連続空き部屋があります.
残りの自分YY、ほほほ
コード:
Splayコード:
Time Limit: 3000MS
Memory Limit: 65536K
Total Submissions: 6224
Accepted: 2546
Description
The cows are journeying north to Thunder Bay in Canada to gain cultural enrichment and enjoy a vacation on the sunny shores of Lake Superior. Bessie, ever the competent travel agent, has named the Bullmoose Hotel on famed Cumberland Street as their vacation residence. This immense hotel has N (1 ≤ N ≤ 50,000) rooms all located on the same side of an extremely long hallway (all the better to see the lake, of course).
The cows and other visitors arrive in groups of size Di (1 ≤ Di ≤ N) and approach the front desk to check in. Each group i requests a set of Di contiguous rooms from Canmuu, the moose staffing the counter. He assigns them some set of consecutive room numbers r..r+Di-1 if they are available or, if no contiguous set of rooms is available, politely suggests alternate lodging. Canmuu always chooses the value of r to be the smallest possible.
Visitors also depart the hotel from groups of contiguous rooms. Checkout i has the parameters Xi and Di which specify the vacating of rooms Xi ..Xi +Di-1 (1 ≤ Xi ≤ N-Di+1). Some (or all) of those rooms might be empty before the checkout.
Your job is to assist Canmuu by processing M (1 ≤ M < 50,000) checkin/checkout requests. The hotel is initially unoccupied.
Input
* Line 1: Two space-separated integers: N and M * Lines 2..M+1: Line i+1 contains request expressed as one of two possible formats: (a) Two space separated integers representing a check-in request: 1 and Di (b) Three space-separated integers representing a check-out: 2, Xi, and Di
Output
* Lines 1.....: For each check-in request, output a single line with a single integer r, the first room in the contiguous sequence of rooms to be occupied. If the request cannot be satisfied, output 0.
Sample Input
10 6
1 3
1 3
1 3
1 3
2 5 5
1 6
1
4
7
0
5
USACO 2008 February Gold
タイトル:http://poj.org/problem?id=3667
标题:宿には1~nの番号の部屋があり、今はm波人が借家を過ぎている可能性があり、波人ごとに連続したd部屋を予約しなければならない可能性があり、もしあれば番号はできるだけ小さく、なければ0と言い、d人がチェックアウトする可能性もあり、彼らの部屋は連続したx~x+d-1の数部屋である..
解析:この問題はセグメントツリー区間のマージに属しますが、比較的簡単です.のまず、もちろん1つの区間の最も長い連続値を記録しなければなりません.この便利な値を取り、それから1つの区間がどのようにその2つのサブ区間から移行するかを考えなければなりません.この最も長い値は必ず1つの値区間の最も長い値の大きい者を記録することができます.もちろん、2つのサブ区間が合併して、より長いものが得られる可能性があります.このより長い肯定は中間で、左のサブ区間が右端から左端までの最も長い連続値を記録する必要があります.右サブ区間の左端から右端までの最長連続値を記録して、新しい値はこの2つの値を加算して、もちろん、どの区間が左区間なのか分からないので、各区間はこの3つの値を記録しなければなりません.もちろん、遅延フラグもあります.TLEではありませんか.
2012-10-7:
最近はsplayを強化しているので、これまではsplayをどうやって使うか考えていませんでしたが、その時は線分木の遅延マークが分からなかったようで、今日はわざわざ考えてみましたが、実は線分木の遅延マークをそのままそのまま使えばいいのです.
各ノードは5つの値ドメインを維持し、
1.val現在のノードがマークされているかどうか(部屋が占有されている)l
2.dly現在のノードの遅延フラグ3
3.len現在のノードがサブノードを含む最大連続空き部屋
4.ll現在のノードの全体の木は自身が代表する区間を含んで、一番左から、一番長い連続空き部屋
5.rl現在のノードの木全体には、自分が代表する区間が含まれており、最も右から最も長い連続空き部屋があります.
残りの自分YY、ほほほ
コード:
#include<cstdio>
#include<iostream>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
const int mm=55555;
int dly[mm<<2],mlen[mm<<2],llen[mm<<2],rlen[mm<<2];
/**mlen ，llen ，rlen */
void check(int rt,int val,int len)
{
llen[rt]=rlen[rt]=mlen[rt]=(val-1)*len;
dly[rt]=val;
}
void pushdown(int rt,int l1,int l2)
{
check(rt<<1,dly[rt],l1);
check(rt<<1|1,dly[rt],l2);
dly[rt]=0;
}
void pushup(int rt,int l1,int l2)
{
mlen[rt]=max(rlen[rt<<1]+llen[rt<<1|1],max(mlen[rt<<1],mlen[rt<<1|1]));
llen[rt]=llen[rt<<1],rlen[rt]=rlen[rt<<1|1];
if(llen[rt]>=l1)llen[rt]+=llen[rt<<1|1];
if(rlen[rt]>=l2)rlen[rt]+=rlen[rt<<1];
}
void build(int l,int r,int rt)
{
dly[rt]=0;
if(l==r)
{
mlen[rt]=llen[rt]=rlen[rt]=1;
return;
}
int m=(l+r)>>1;
build(lson);
build(rson);
pushup(rt,m-l+1,r-m);
}
void updata(int L,int R,int val,int l,int r,int rt)
{
if(L<=l&&R>=r)
{
check(rt,val,r-l+1);
return;
}
int m=(l+r)>>1;
if(dly[rt])pushdown(rt,m-l+1,r-m);
if(L<=m)updata(L,R,val,lson);
if(R>m)updata(L,R,val,rson);
pushup(rt,m-l+1,r-m);
}
int query(int s,int l,int r,int rt)
{
if(llen[rt]>=s)return l;
int m=(l+r)>>1,ret;
if(dly[rt])pushdown(rt,m-l+1,r-m);
if(mlen[rt<<1]>=s)ret=query(s,lson);
else if(rlen[rt<<1]+llen[rt<<1|1]>=s)ret=m-rlen[rt<<1]+1;
else ret=query(s,rson);
pushup(rt,m-l+1,r-m);
return ret;
}
int main()
{
int i,j,k,n,m;
while(~scanf("%d%d",&n,&m))
{
build(1,n,1);
while(m--)
{
scanf("%d%d",&k,&i);
if(k==2)
{
scanf("%d",&j);
updata(i,i+j-1,2,1,n,1);
}
else if(mlen[1]>=i)
{
j=query(i,1,n,1);
printf("%d
",j);
updata(j,j+i-1,1,1,n,1);
}
else puts("0");
}
}
return 0;
}
Splayコード:
#include<cstdio>
#include<iostream>
using namespace std;
const int mm=55555;
struct SplayTree
{
int son[mm][2],far[mm],num[mm],val[mm],len[mm],ll[mm],rl[mm],dly[mm];
int rt,size;
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;
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;
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];
}
void PushDown(int x)
{
if(!dly[x])return;
val[x]=dly[x]>0?1:0;
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]);
ll[x]=ll[a],rl[x]=rl[b];
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;
}
}
int Come(int a)
{
if(len[rt]<a)return 0;
int x=rt,y,b=a,l=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;
l+=num[son[x][0]]+1,x=son[x][1];
}
PushDown(x);
}
l+=num[son[x][0]]-a+1;
x=Select(l-1,0);
y=Select(l+a,rt);
Check(son[y][0],1);
Splay(y,0);
return l;
}
void Leave(int x,int a)
{
int l=Select(x-1,0);
int y=Select(x+a,rt);
Check(son[y][0],-1);
Splay(y,0);
}
}spt;
int i,j,k,n,m;
int main()
{
while(~scanf("%d%d",&n,&m))
{
spt.Prepare(n);
while(m--)
{
scanf("%d%d",&k,&i);
if(k==1)printf("%d
",spt.Come(i));
else scanf("%d",&j),spt.Leave(i,j);
}
}
return 0;
}