题意：
分析：
涉及区间修改和区间查询。而且，每次查询是否存在一定长度的区间，并且要求区间起点尽可能靠前。同时，要区分两种不同的查询。
可用时间为 (1)，不可用时间为 (0)。建立维护两棵线段树，一个单独维护 (NS) 的操作，一个维护 (NS) 和 (DS) 的操作。每棵维护区间的最大连续长度，以区间左端点为起点的最大连续子段长，以区间右端点为终点的最大连续子段和。
分析：
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
struct node
{
int len,ren,maxn,lazy;
}tre1[N<<2],tre2[N<<2];//维护区间最大子段和
int ans;
void pushup(node tre[],int rt,int l,int r)
{
tre[rt].maxn=max(tre[rt<<1].maxn,tre[rt<<1|1].maxn);
if(tre[rt<<1].ren+tre[rt<<1|1].len>tre[rt].maxn)
tre[rt].maxn=tre[rt<<1].ren+tre[rt<<1|1].len;
int mid=(l+r)>>1;
if(tre[rt<<1].len==mid-l+1)
tre[rt].len=tre[rt<<1].len+tre[rt<<1|1].len;
else
tre[rt].len=tre[rt<<1].len;
if(tre[rt<<1|1].ren==r-mid)
tre[rt].ren=tre[rt<<1|1].ren+tre[rt<<1].ren;
else
tre[rt].ren=tre[rt<<1|1].ren;
}
void pushdown(node tre[],int rt,int ln,int rn)
{
if(tre[rt].lazy>-1)//直接赋值，因为一个时间点只能用一次
{
tre[rt<<1].lazy=tre[rt].lazy;
tre[rt<<1|1].lazy=tre[rt].lazy;
tre[rt<<1].maxn=ln*tre[rt].lazy;
tre[rt<<1|1].maxn=rn*tre[rt].lazy;
tre[rt<<1].len=tre[rt<<1].maxn;
tre[rt<<1].ren=tre[rt<<1].maxn;
tre[rt<<1|1].len=tre[rt<<1|1].maxn;
tre[rt<<1|1].ren=tre[rt<<1|1].maxn;
tre[rt].lazy=-1;
}
}
void build(int l,int r,int rt)
{
tre1[rt].lazy=-1;
tre2[rt].lazy=-1;
if(l==r)
{
tre1[rt]=node{1,1,1,-1};
tre2[rt]=node{1,1,1,-1};
return;
}
int mid=(l+r)>>1;
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
pushup(tre1,rt,l,r);
pushup(tre2,rt,l,r);
}
void update(node tre [],int l,int r,int L,int R,int val,int rt)
{
if(L<=l&&r<=R)
{
tre[rt].maxn=val*(r-l+1);
tre[rt].lazy=val;
tre[rt].len=tre[rt].maxn;
tre[rt].ren=tre[rt].maxn;
return;
}
int mid=(l+r)>>1;
pushdown(tre,rt,mid-l+1,r-mid);
if(L<=mid)
update(tre,l,mid,L,R,val,rt<<1);
if(R>mid)
update(tre,mid+1,r,L,R,val,rt<<1|1);
pushup(tre,rt,l,r);
}
void query(node tre [],int l,int r,int num,int rt)
{
if(tre[rt].maxn<num)
return;
int mid=(l+r)>>1;
pushdown(tre,rt,mid-l+1,r-mid);
if(tre[rt<<1].maxn>=num)
query(tre,l,mid,num,rt<<1);
else if(tre[rt<<1].ren+tre[rt<<1|1].len>=num)
{
ans=mid-tre[rt<<1].ren+1;
return;
}
else if(tre[rt<<1|1].maxn>=num)
query(tre,mid+1,r,num,rt<<1|1);
}
int main()
{
int cas,qt,t,n,ca=0;
scanf("%d",&cas);
while(cas--)
{
scanf("%d%d",&t,&n);
printf("Case %d:
",++ca);
build(1,t,1);
while(n--)
{
char op[10]={};
scanf("%s",op);
if(strcmp(op,"NS")==0)
{
scanf("%d",&qt);
ans=-1;
query(tre2,1,t,qt,1);
if(ans<0)
{
query(tre1,1,t,qt,1);
if(ans>0)
{
update(tre1,1,t,ans,ans+qt-1,0,1);
update(tre2,1,t,ans,ans+qt-1,0,1);
}
}
else
{
update(tre1,1,t,ans,ans+qt-1,0,1);
update(tre2,1,t,ans,ans+qt-1,0,1);//cout<<"ans="<<ans<<endl;
}
if(ans>0)
printf("%d,don't put my gezi
",ans);
else
printf("wait for me
");
}
else if(strcmp(op,"DS")==0)
{
scanf("%d",&qt);
ans=-1;
query(tre2,1,t,qt,1);
if(ans>0)
update(tre2,1,t,ans,ans+qt-1,0,1);
if(ans>0)
printf("%d,let's fly
",ans);
else
printf("fly with yourself
");
}
else
{
int l,r;
scanf("%d%d",&l,&r);
update(tre1,1,t,l,r,1,1);
update(tre2,1,t,l,r,1,1);
printf("I am the hope of chinese chengxuyuan!!
");
}
}
}
return 0;
}