約會安排
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 81 Accepted Submission(s): 26
Problem Description
寒假來了，又到了小明和女神們約會的季節。
小明雖為屌絲級碼農，但非常活躍，女神們常常在小明網上的大段發言後熱情回復“呵呵”，所以，小明的最愛就是和女神們約會。與此同時，也有很多基友找他開黑，由於數量實在過於巨大，怎麼安排時間便成了小明的一大心事。
我們已知小明一共有T的空閒時間，期間會有很多女神或者基友來找小明。
作為一個操作系統曾經怒考71分的大神，小明想到了一個算法，即“首次適應算法”，根據操作系統課本的描述，就是找一段最靠前的符合要求的連續空間分配給每個請求，由此小明做出了一個決定：
當一個基友來找小明時，小明就根據“首次適應算法”來找一段空閒的時間來和基友約好，如果找到，就說“X,let’s fly”（此處，X為開始時間），否則就說“fly with yourself”；
當女神來找小明時，先使用一次“首次適應算法”，如果沒有找到，小明就冒著木叽叽的風險無視所有屌絲基友的約定，再次使用“無視基友首次適應算法”，兩次只要有一次找到，就說“X,don’t put my gezi”（此處，X為開始時間），否則就說“wait for me”
當然，我們知道小明不是一個節操負無窮的人，如果和女神約會完，還有剩余時間，他還是會和原來約好的基友去dota的。（舉個例子：小西（屌絲）和小明約好在1~5這個時間單位段內打dota，這時候，女神來和小明預約長度為3的時間段，那麼最終就是1~3小明去和女神約會，搞定後在4~5和小西打dota）
小明偶爾也會想要學習新知識，此時小明就會把某一個時間區間的所有已經預定的時間全部清空用來學習並且怒吼“I am the hope of chinese chengxuyuan!!”，不過小明一般都是三分鐘熱度，再有人來預定的話，小明就會按耐不住寂寞把學習新知識的時間分配出去。
Input
輸入第一行為CASE，表示有CASE組測試數據；
每組數據以兩個整數T，N開始，T代表總共的時間，N表示預約請求的個數；
接著的N行，每行表示一個女神或者基友的預約，“NS QT”代表一個女神來找小明約一段長為QT的時間，“DS QT”則代表一個屌絲的長為QT的請求，當然也有可能是小明想學知識了，“STUDY!! L R”代表清空L~R區間內的所有請求。
[Technical Specification]
1. 1 <= CASE <= 30
2. 1 <= T, N <= 100000
3. 1 <= QT <= 110000
4. 1 <= L <= R <=T
Output
對於每一個case，第一行先輸出“Case C:”代表是第幾個case，然後N行，每行對應一個請求的結果(參照描述)。
輸出樣本(可復制此處)：
“X,let's fly”,”fly with yourself”,”X,don't put my gezi”,”wait for me”,”I am the hope of chinese chengxuyuan!!”
Sample Input
1
5 6
DS 3
NS 2
NS 4
STUDY!! 1 5
DS 4
NS 2
Sample Output
Case 1:
1,let's fly
4,don't put my gezi
wait for me
I am the hope of chinese chengxuyuan!!
1,let's fly
1,don't put my gezi
Source
2013金山西山居創意游戲程序挑戰賽——初賽（3）
Recommend
liuyiding
解題思路：就是線段樹的區間合並，在每個區間內設置女神區間和屌絲區間，根據題意，每次詢問女神的時候，先看屌絲區間有無空位，有就插到屌絲區間內，同時更新女神區間，否則插到女神區間內，但同時也要更新屌絲區間，因為只有女神可以占用屌絲的時間，屌絲不能占用女神的時間，每次更新屌絲區間的時候直接更新即可，清空的話就是對屌絲和女神的區間都清空。
PS:這一題比賽的時候沒做出來可惜了，不過能做出來而且一次AC，本蒟蒻還是很開心的^-^!
[cpp] #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<string>
#include<set>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<stack>
#define Max 100005
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
struct
{
int lds;
int rds;
int mds;
int lns;
int rns;
int mns;
int coverds;
int coverns;
}tree[Max<<2];
void build(int l,int r,int rt)
{
tree[rt].lds=tree[rt].rns=tree[rt].rds=tree[rt].lns=tree[rt].mds=tree[rt].mns=r-l+1;
tree[rt].coverds=tree[rt].coverns=-1;
if(l==r)
return ;
int m=(l+r)>>1;
build(lson);
build(rson);
}
void push_up(int rt,int len,int p)
{
if(p==0)
{
tree[rt].lds=tree[rt<<1].lds;
tree[rt].rds=tree[rt<<1|1].rds;
if(tree[rt].lds==len-(len>>1))
tree[rt].lds+=tree[rt<<1|1].lds;
if(tree[rt].rds==(len>>1))
tree[rt].rds+=tree[rt<<1].rds;
tree[rt].mds=max(tree[rt<<1].rds+tree[rt<<1|1].lds,max(tree[rt<<1].mds,tree[rt<<1|1].mds));
}
else
{
tree[rt].lds=tree[rt<<1].lds;
tree[rt].rds=tree[rt<<1|1].rds;
if(tree[rt].lds==len-(len>>1))
tree[rt].lds+=tree[rt<<1|1].lds;
if(tree[rt].rds==(len>>1))
tree[rt].rds+=tree[rt<<1].rds;
tree[rt].mds=max(tree[rt<<1].rds+tree[rt<<1|1].lds,max(tree[rt<<1].mds,tree[rt<<1|1].mds));
tree[rt].lns=tree[rt<<1].lns;
tree[rt].rns=tree[rt<<1|1].rns;
if(tree[rt].lns==len-(len>>1))
tree[rt].lns+=tree[rt<<1|1].lns;
if(tree[rt].rns==(len>>1))
tree[rt].rns+=tree[rt<<1].rns;
tree[rt].mns=max(tree[rt<<1].rns+tree[rt<<1|1].lns,max(tree[rt<<1].mns,tree[rt<<1|1].mns));
}
}
void push_down(int rt,int len)
{
if(tree[rt].coverds!=-1)
{
tree[rt<<1].coverds=tree[rt<<1|1].coverds=tree[rt].coverds;
tree[rt<<1].lds=tree[rt<<1].rds=tree[rt<<1].mds=tree[rt].coverds?0:len-(len>>1);
tree[rt<<1|1].lds=tree[rt<<1|1].rds=tree[rt<<1|1].mds=tree[rt].coverds?0:(len>>1);
tree[rt].coverds=-1;
}
if(tree[rt].coverns!=-1)
{
tree[rt<<1].coverns=tree[rt<<1|1].coverns=tree[rt].coverns;
tree[rt<<1].lns=tree[rt<<1].rns=tree[rt<<1].mns=tree[rt].coverns?0:len-(len>>1);
tree[rt<<1|1].lns=tree[rt<<1|1].rns=tree[rt<<1|1].mns=tree[rt].coverns?0:(len>>1);
tree[rt].coverns=-1;
}
}
int query(int pos,int p,int l,int r,int rt)
{
if(l==r)
return l;
push_down(rt,r-l+1);
int m=(l+r)>>1;
if(p==0)
{
if(pos<=tree[rt<<1].mds)
return query(pos,p,lson);
else if(tree[rt<<1].rds+tree[rt<<1|1].lds>=pos)
return m-tree[rt<<1].rds+1;
else
return query(pos,p,rson);
}
else
{
if(pos<=tree[rt<<1].mns)
return query(pos,p,lson);
else if(tree[rt<<1].rns+tree[rt<<1|1].lns>=pos)
return m-tree[rt<<1].rns+1;
else
return query(pos,p,rson);
}
}
void update(int L,int R,int p,int c,int l,int r,int rt)
{
if(L<=l&&R>=r)
{
if(p==0)
{
tree[rt].lds=tree[rt].rds=tree[rt].mds=c?0:r-l+1;
tree[rt].coverds=c;
}
else
{
tree[rt].lns=tree[rt].rns=tree[rt].mns=c?0:r-l+1;
tree[rt].coverns=c;
}
return ;
}
push_down(rt,r-l+1);
int m=(l+r)>>1;
if(L<=m)
update(L,R,p,c,lson);
if(R>m)
update(L,R,p,c,rson);
push_up(rt,r-l+1,p);
}
int main()
{
int i,t,m,n,time,a,b,ans;
char op[10];
scanf("%d",&t);
for(i=1;i<=t;i++)
{
a=b=0;
scanf("%d%d",&n,&m);
build(1,n,1);
printf("Case %d:\n",i);
while(m--)
{
scanf("%s",op);
switch(op[0])
{
case 'D':
scanf("%d",&time);
if(time>tree[1].mds)
printf("fly with yourself\n");
else
{
ans=query(time,0,1,n,1);
printf("%d,let's fly\n",ans);
update(ans,ans+time-1,0,1,1,n,1);
}
break;
case 'N':
scanf("%d",&time);
if(time>tree[1].mds)
{
if(time>tree[1].mns)
printf("wait for me\n");
else
{
ans=query(time,1,1,n,1);
printf("%d,don't put my gezi\n",ans);
update(ans,ans+time-1,0,1,1,n,1);
update(ans,ans+time-1,1,1,1,n,1);
}
}
else
{
ans=query(time,0,1,n,1);
printf("%d,don't put my gezi\n",ans);
update(ans,ans+time-1,0,1,1,n,1);
update(ans,ans+time-1,1,1,1,n,1);
}
break;
case 'S':
scanf("%d%d",&a,&b);
printf("I am the hope of chinese chengxuyuan!!\n");
update(a,b,0,0,1,n,1);
update(a,b,1,0,1,n,1);
break;
}
}
}
return 0;
}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<string>
#include<set>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<stack>
#define Max 100005
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
struct
{
int lds;
int rds;
int mds;
int lns;
int rns;
int mns;
int coverds;
int coverns;
}tree[Max<<2];
void build(int l,int r,int rt)
{
tree[rt].lds=tree[rt].rns=tree[rt].rds=tree[rt].lns=tree[rt].mds=tree[rt].mns=r-l+1;
tree[rt].coverds=tree[rt].coverns=-1;
if(l==r)
return ;
int m=(l+r)>>1;
build(lson);
build(rson);
}
void push_up(int rt,int len,int p)
{
if(p==0)
{
tree[rt].lds=tree[rt<<1].lds;
tree[rt].rds=tree[rt<<1|1].rds;
if(tree[rt].lds==len-(len>>1))
tree[rt].lds+=tree[rt<<1|1].lds;
if(tree[rt].rds==(len>>1))
tree[rt].rds+=tree[rt<<1].rds;
tree[rt].mds=max(tree[rt<<1].rds+tree[rt<<1|1].lds,max(tree[rt<<1].mds,tree[rt<<1|1].mds));
}
else
{
tree[rt].lds=tree[rt<<1].lds;
tree[rt].rds=tree[rt<<1|1].rds;
if(tree[rt].lds==len-(len>>1))
tree[rt].lds+=tree[rt<<1|1].lds;
if(tree[rt].rds==(len>>1))
tree[rt].rds+=tree[rt<<1].rds;
tree[rt].mds=max(tree[rt<<1].rds+tree[rt<<1|1].lds,max(tree[rt<<1].mds,tree[rt<<1|1].mds));
tree[rt].lns=tree[rt<<1].lns;
tree[rt].rns=tree[rt<<1|1].rns;
if(tree[rt].lns==len-(len>>1))
tree[rt].lns+=tree[rt<<1|1].lns;
if(tree[rt].rns==(len>>1))
tree[rt].rns+=tree[rt<<1].rns;
tree[rt].mns=max(tree[rt<<1].rns+tree[rt<<1|1].lns,max(tree[rt<<1].mns,tree[rt<<1|1].mns));
}
}
void push_down(int rt,int len)
{
if(tree[rt].coverds!=-1)
{
tree[rt<<1].coverds=tree[rt<<1|1].coverds=tree[rt].coverds;
tree[rt<<1].lds=tree[rt<<1].rds=tree[rt<<1].mds=tree[rt].coverds?0:len-(len>>1);
tree[rt<<1|1].lds=tree[rt<<1|1].rds=tree[rt<<1|1].mds=tree[rt].coverds?0:(len>>1);
tree[rt].coverds=-1;
}
if(tree[rt].coverns!=-1)
{
tree[rt<<1].coverns=tree[rt<<1|1].coverns=tree[rt].coverns;
tree[rt<<1].lns=tree[rt<<1].rns=tree[rt<<1].mns=tree[rt].coverns?0:len-(len>>1);
tree[rt<<1|1].lns=tree[rt<<1|1].rns=tree[rt<<1|1].mns=tree[rt].coverns?0:(len>>1);
tree[rt].coverns=-1;
}
}
int query(int pos,int p,int l,int r,int rt)
{
if(l==r)
return l;
push_down(rt,r-l+1);
int m=(l+r)>>1;
if(p==0)
{
if(pos<=tree[rt<<1].mds)
return query(pos,p,lson);
else if(tree[rt<<1].rds+tree[rt<<1|1].lds>=pos)
return m-tree[rt<<1].rds+1;
else
return query(pos,p,rson);
}
else
{
if(pos<=tree[rt<<1].mns)
return query(pos,p,lson);
else if(tree[rt<<1].rns+tree[rt<<1|1].lns>=pos)
return m-tree[rt<<1].rns+1;
else
return query(pos,p,rson);
}
}
void update(int L,int R,int p,int c,int l,int r,int rt)
{
if(L<=l&&R>=r)
{
if(p==0)
{
tree[rt].lds=tree[rt].rds=tree[rt].mds=c?0:r-l+1;
tree[rt].coverds=c;
}
else
{
tree[rt].lns=tree[rt].rns=tree[rt].mns=c?0:r-l+1;
tree[rt].coverns=c;
}
return ;
}
push_down(rt,r-l+1);
int m=(l+r)>>1;
if(L<=m)
update(L,R,p,c,lson);
if(R>m)
update(L,R,p,c,rson);
push_up(rt,r-l+1,p);
}
int main()
{
int i,t,m,n,time,a,b,ans;
char op[10];
scanf("%d",&t);
for(i=1;i<=t;i++)
{
a=b=0;
scanf("%d%d",&n,&m);
build(1,n,1);
printf("Case %d:\n",i);
while(m--)
{
scanf("%s",op);
switch(op[0])
{
case 'D':
scanf("%d",&time);
if(time>tree[1].mds)
printf("fly with yourself\n");
else
{
ans=query(time,0,1,n,1);
printf("%d,let's fly\n",ans);
update(ans,ans+time-1,0,1,1,n,1);
}
break;
case 'N':
scanf("%d",&time);
if(time>tree[1].mds)
{
if(time>tree[1].mns)
printf("wait for me\n");
else
{
ans=query(time,1,1,n,1);
printf("%d,don't put my gezi\n",ans);
update(ans,ans+time-1,0,1,1,n,1);
update(ans,ans+time-1,1,1,1,n,1);
}
}
else
{
ans=query(time,0,1,n,1);
printf("%d,don't put my gezi\n",ans);
update(ans,ans+time-1,0,1,1,n,1);
update(ans,ans+time-1,1,1,1,n,1);
}
break;
case 'S':
scanf("%d%d",&a,&b);
printf("I am the hope of chinese chengxuyuan!!\n");
update(a,b,0,0,1,n,1);
update(a,b,1,0,1,n,1);
break;
}
}
}
return 0;
}
