题目链接：约会安排 - HDU 4553 - Virtual Judge (ppsucxtt.cn)
由于题目是中文的，题目大意我就不说了，下面直接说思路：
对于屌丝的邀请，我们不能使用任何已经被占用的时间，而对于女神的邀请我们却可以无视屌丝的邀请，这就意味着他们之间的关系是具有优先级的，我们需要建立两棵线段树，一棵维护女神和屌丝的共同占用时间，另一棵只维护女神的占用时间。对于屌丝的邀请，我们只能在屌丝和女生共用的那棵线段树上查找，而对于女神的邀请我们就可以在两棵树上查找，只是我们要先在屌丝和女生共用的那棵线段树上查找，如果找不到合适时间再从女神独自占有的那棵线段树上查找。对于每次查找，都是寻找一块连续时间，所以我们要记录区间的最大连续未被占用的时间，这显然就是一个区间合并问题，在这里对区间合并方面的细节我就不赘述了，不明白的小伙伴可以看下我之前的博客，现在给出区间合并的博客地址：
(33条消息) LCIS（线段树+区间合并）_AC__dream的博客-CSDN博客
对于查找连续时间我们可以从头开始二分查找，注意左边界一直是1，如果找到了最小右边界，则满足条件的左边界就是右边界-时间长度+1了。最后的操作就是一个区间清空操作，这就是一个简单的置0操作，由于0是一个操作数，所以我们的lazy数组应该初始化为-1，其他的就没什么可说的了，下面上代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
const int N=2e6+10;
int l[2][N],r[2][N],head[2][N],tail[2][N],maxx[2][N],lazy[2][N];
//head[i][j]表示第i棵线段树的第j个区间以区间左边界开头的最长连续1的个数
//tail[i][j]表示第i棵线段树的第j个区间以区间右边界结尾的最长连续1的个数
//maxx[i][j]表示第i棵线段树的第j个区间内的最长连续1的个数
void pushup(int k,int id)
{
if(head[k][id<<1]==r[k][id<<1]-l[k][id<<1]+1)
head[k][id]=head[k][id<<1]+head[k][id<<1|1];
else
head[k][id]=head[k][id<<1];
if(tail[k][id<<1|1]==r[k][id<<1|1]-l[k][id<<1|1]+1)
tail[k][id]=tail[k][id<<1]+tail[k][id<<1|1];
else
tail[k][id]=tail[k][id<<1|1];
maxx[k][id]=max(maxx[k][id<<1],maxx[k][id<<1|1]);
if(tail[k][id<<1]&&head[k][id<<1|1])
maxx[k][id]=max(maxx[k][id],tail[k][id<<1]+head[k][id<<1|1]);
}
void pushdown(int k,int id)
{
if(lazy[k][id]!=-1)
{
lazy[k][id<<1]=lazy[k][id];
lazy[k][id<<1|1]=lazy[k][id];
maxx[k][id<<1]=head[k][id<<1]=tail[k][id<<1]=(r[k][id<<1]-l[k][id<<1]+1)*lazy[k][id];
maxx[k][id<<1|1]=head[k][id<<1|1]=tail[k][id<<1|1]=(r[k][id<<1|1]-l[k][id<<1|1]+1)*lazy[k][id];
lazy[k][id]=-1;
}
}
void build(int k,int id,int L,int R)
{
l[k][id]=L;r[k][id]=R;head[k][id]=tail[k][id]=maxx[k][id]=R-L+1;lazy[k][id]=-1;
if(L==R) return ;
int mid=L+R>>1;
build(k,id<<1,L,mid);
build(k,id<<1|1,mid+1,R);
pushup(k,id);
return ;
}
void update_interval(int k,int id,int L,int R,int val)
{
if(l[k][id]>=L&&r[k][id]<=R)
{
lazy[k][id]=val;
head[k][id]=tail[k][id]=maxx[k][id]=(r[k][id]-l[k][id]+1)*val;
return ;
}
pushdown(k,id);
int mid=l[k][id]+r[k][id]>>1;
if(L<=mid) update_interval(k,id<<1,L,R,val);
if(mid+1<=R) update_interval(k,id<<1|1,L,R,val);
pushup(k,id);
}
int query_interval(int k,int id,int L,int R)
{
if(r[k][id]<L||l[k][id]>R) return 0;
if(l[k][id]>=L&&r[k][id]<=R) return maxx[k][id];
pushdown(k,id);
int mid=l[k][id]+r[k][id]>>1;
int ans=max(query_interval(k,id<<1,L,R),query_interval(k,id<<1|1,L,R));
ans=max(ans,min(tail[k][id<<1],r[k][id<<1]-L+1)+min(head[k][id<<1|1],R-l[k][id<<1|1]+1));//防止越界
return ans;
}
int main()
{
int T;
cin>>T;
for(int i=1;i<=T;i++)
{
int t,n;
printf("Case %d:\n",i);
scanf("%d%d",&t,&n);
build(0,1,1,t);//维护屌丝和女神的线段树
build(1,1,1,t);//维护女神的线段树
while(n--)
{
char op[20];
int l,r,tt;
scanf("%s",op);
if(op[0]=='D')
{
scanf("%d",&tt);
//屌丝的邀请只能在屌丝和女神共有的线段树上二分查找
if(query_interval(0,1,1,t)<tt)
puts("fly with yourself");
else
{
int ll=1,rr=t;
while(ll<rr)
{
int mid=ll+rr>>1;
if(query_interval(0,1,1,mid)>=tt) rr=mid;
else ll=mid+1;
}
printf("%d,let's fly\n",ll-tt+1);
update_interval(0,1,ll-tt+1,ll,0);
}
}
else if(op[0]=='N')
{
scanf("%d",&tt);
//女神的邀请可以在两棵线段树上二分查找，先查屌丝和女神共有的线段树
if(query_interval(0,1,1,t)>=tt)
{
int ll=1,rr=t;
while(ll<rr)
{
int mid=ll+rr>>1;
if(query_interval(0,1,1,mid)>=tt) rr=mid;
else ll=mid+1;
}
printf("%d,don't put my gezi\n",ll-tt+1);
update_interval(0,1,ll-tt+1,ll,0);
update_interval(1,1,ll-tt+1,ll,0);
}
else if(query_interval(1,1,1,t)>=tt)
{
int ll=1,rr=t;
while(ll<rr)
{
int mid=ll+rr>>1;
if(query_interval(1,1,1,mid)>=tt) rr=mid;
else ll=mid+1;
}
printf("%d,don't put my gezi\n",ll-tt+1);
//将两棵线段树对应位置都填满
update_interval(0,1,ll-tt+1,ll,0);
update_interval(1,1,ll-tt+1,ll,0);
}
else
puts("wait for me");
}
else
{
scanf("%d%d",&l,&r);
//将两棵线段树对应位置都清空
update_interval(0,1,l,r,1);
update_interval(1,1,l,r,1);
puts("I am the hope of chinese chengxuyuan!!");
}
}
}
return 0;
}