题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4553
题目大意：就是有三种操作：
①DS x，安排一段长度为x的空闲时间跟屌丝一起，输出这段时间的起点，若没有则输出“fly with yourself”。
②NS x，安排一段长度为x的空闲时间跟女神在一起，若没有则可以无视屌丝的时间再找一次，输出这段时间的起点，若两次都没有则输出“wait for me”。
③STUDY!! l r，清空l~r这段时间的所有安排。
解题思路：区间合并问题，但是要分为屌丝、女神两种标记，就是每种操作基本都要来双份代码变长了。。。找一段空闲时间的起点一开始不会的，后来学习了一下。其他的没什么要特别注意的地方。
代码：
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<string>
#define LC(a) (a<<1)
#define RC(a) (a<<1|1)
#define MID(a,b) ((a+b)>>1)
using namespace std;
typedef long long LL;
const int INF=0x3f3f3f3f;
const int N=1e5+; struct node{
int l,r;
int dls,dms,drs;//屌丝
int nls,nms,nrs;//女神
}tree[N<<]; int x; void pushup(int p){
//屌丝
if(tree[LC(p)].dls==tree[LC(p)].r-tree[LC(p)].l+)
tree[p].dls=tree[LC(p)].dls+tree[RC(p)].dls;
else
tree[p].dls=tree[LC(p)].dls;
if(tree[RC(p)].drs==tree[RC(p)].r-tree[RC(p)].l+)
tree[p].drs=tree[RC(p)].drs+tree[LC(p)].drs;
else
tree[p].drs=tree[RC(p)].drs;
tree[p].dms=max(tree[LC(p)].drs+tree[RC(p)].dls,max(tree[LC(p)].dms,tree[RC(p)].dms));
//女神
if(tree[LC(p)].nls==tree[LC(p)].r-tree[LC(p)].l+)
tree[p].nls=tree[LC(p)].nls+tree[RC(p)].nls;
else
tree[p].nls=tree[LC(p)].nls;
if(tree[RC(p)].nrs==tree[RC(p)].r-tree[RC(p)].l+)
tree[p].nrs=tree[RC(p)].nrs+tree[LC(p)].nrs;
else
tree[p].nrs=tree[RC(p)].nrs;
tree[p].nms=max(tree[LC(p)].nrs+tree[RC(p)].nls,max(tree[LC(p)].nms,tree[RC(p)].nms));
} void pushdown(int p){
//屌丝
if(tree[p].dms==tree[p].r-tree[p].l+){
tree[LC(p)].dls=tree[LC(p)].dms=tree[LC(p)].drs=tree[LC(p)].r-tree[LC(p)].l+;
tree[RC(p)].dls=tree[RC(p)].dms=tree[RC(p)].drs=tree[RC(p)].r-tree[RC(p)].l+;
}
else if(tree[p].dms==){
tree[LC(p)].dls=tree[LC(p)].dms=tree[LC(p)].drs=;
tree[RC(p)].dls=tree[RC(p)].dms=tree[RC(p)].drs=;
}
//女神
if(tree[p].nms==tree[p].r-tree[p].l+){
tree[LC(p)].nls=tree[LC(p)].nms=tree[LC(p)].nrs=tree[LC(p)].r-tree[LC(p)].l+;
tree[RC(p)].nls=tree[RC(p)].nms=tree[RC(p)].nrs=tree[RC(p)].r-tree[RC(p)].l+;
}
else if(tree[p].nms==){
tree[LC(p)].nls=tree[LC(p)].nms=tree[LC(p)].nrs=;
tree[RC(p)].nls=tree[RC(p)].nms=tree[RC(p)].nrs=;
}
} void build(int p,int l,int r){
tree[p].l=l;
tree[p].r=r;
if(l==r){
tree[p].dls=tree[p].dms=tree[p].drs=tree[p].nls=tree[p].nms=tree[p].nrs=;
return;
}
build(LC(p),l,MID(l,r));
build(RC(p),MID(l,r)+,r);
pushup(p);
} void update(int p,int l,int r,int op){
if(l>tree[p].r||r<tree[p].l)
return;
if(l<=tree[p].l&&r>=tree[p].r){
if(op==)
tree[p].dls=tree[p].dms=tree[p].drs=;
else if(op==)
tree[p].nls=tree[p].nms=tree[p].nrs=;
else
tree[p].dls=tree[p].dms=tree[p].drs=tree[p].nls=tree[p].nms=tree[p].nrs=tree[p].r-tree[p].l+;
return;
}
pushdown(p);
update(LC(p),l,r,op);
update(RC(p),l,r,op);
pushup(p);
} int query(int p,int l,int r,char op){
//这句一定要加，否则当所需时间为1时，可能会陷入无限递归
if(l==r)
return l;
pushdown(p);
if(op=='D'){
if(tree[LC(p)].dms>=x)
return query(LC(p),l,MID(l,r),op);
else if(tree[LC(p)].drs+tree[RC(p)].dls>=x){
int t=tree[LC(p)].r-tree[LC(p)].drs+;
return t;
}
else
return query(RC(p),MID(l,r)+,r,op);
}
else{
if(tree[LC(p)].nms>=x)
return query(LC(p),l,MID(l,r),op);
else if(tree[LC(p)].nrs+tree[RC(p)].nls>=x){
int t=tree[LC(p)].r-tree[LC(p)].nrs+;
return t;
}
else
return query(RC(p),MID(l,r)+,r,op);
}
pushup(p);
} int main(){
int T;
scanf("%d",&T);
int cas=;
while(T--){
int n,q;
scanf("%d%d",&n,&q);
build(,,n);
printf("Case %d:\n",++cas);
while(q--){
char op[];
scanf("%s",op);
if(op[]=='D'){
scanf("%d",&x);
if(tree[].dms>=x){
int l=query(,,n,'D');
update(,l,l+x-,);
printf("%d,let's fly\n",l);
}
else
puts("fly with yourself");
}
else if(op[]=='N'){
scanf("%d",&x);
int l;
if(tree[].dms>=x){
l=query(,,n,'D');
//把屌丝和女神的这段时间都安排上，因为无论对屌丝还是女神来说这段时间都被安排了。
update(,l,l+x-,);
update(,l,l+x-,);
printf("%d,don't put my gezi\n",l);
}
else if(tree[].nms>=x){
l=query(,,n,'N');
update(,l,l+x-,);
update(,l,l+x-,);
printf("%d,don't put my gezi\n",l);
}
else
puts("wait for me");
}
else{
int l,r;
scanf("%d%d",&l,&r);
update(,l,r,);
puts("I am the hope of chinese chengxuyuan!!");
}
}
}
return ;
}