中文题面
思路：维和两个区间 一个是女神区间 一个是基友区间 如果是基友要预约时间 直接在基友区间查询可满足的起点 （这里先判tree[1].m >=length也就是有没有这样的区间满足时间length） 预约成功后更新基友区间
如果是女神要预约区间 先在基友区间预约看有没有满足的区间 （同样看根节点的m） 如果有 同时更新两个区间 如果没有继续在女神区间查找 如果女神区间有 则同时更新基友和女神区间 如果没有 那就真没有了直接输出 题目要求的话
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+;
struct Node{
int l,r;
int ml,mr,m;
}tree1[maxn*],tree2[maxn*];
void build(int x,int l,int r){
tree1[x].l=tree2[x].l=l;
tree1[x].r=tree2[x].r=r;
tree1[x].ml=tree2[x].ml=tree1[x].mr=tree2[x].mr=tree1[x].m=tree2[x].m=r-l+;
if(l==r)return ;
int mid=l+r>>;
build(x<<,l,mid);
build(x<<|,mid+,r);
}
void push_up(int x){
int mid=tree1[x].r+tree1[x].l>>;
tree1[x].ml=tree1[x<<].ml;
tree1[x].mr=tree1[x<<|].mr;
tree1[x].m=max(max(tree1[x<<].m,tree1[x<<|].m),tree1[x<<].mr+tree1[x<<|].ml);
if(tree1[x<<].ml==mid-tree1[x].l+)tree1[x].ml+=tree1[x<<|].ml;
if(tree1[x<<|].mr==tree1[x].r-mid)tree1[x].mr+=tree1[x<<].mr; tree2[x].ml=tree2[x<<].ml;
tree2[x].mr=tree2[x<<|].mr;
tree2[x].m=max(max(tree2[x<<].m,tree2[x<<|].m),tree2[x<<].mr+tree2[x<<|].ml);
if(tree2[x<<].ml==mid-tree2[x].l+)tree2[x].ml+=tree2[x<<|].ml;
if(tree2[x<<|].mr==tree2[x].r-mid)tree2[x].mr+=tree2[x<<].mr; }
void push_down(int x){
int mid=tree1[x].l+tree1[x].r>>;
if(tree1[x].m==tree1[x].r-tree1[x].l+){
tree1[x<<].ml=tree1[x<<].mr=tree1[x<<].m=mid-tree1[x].l+;
tree1[x<<|].ml=tree1[x<<|].mr=tree1[x<<|].m=tree1[x].r-mid;
}
else if(tree1[x].m==){
tree1[x<<].ml=tree1[x<<].mr=tree1[x<<].m=;
tree1[x<<|].ml=tree1[x<<|].mr=tree1[x<<|].m=;
} if(tree2[x].m==tree2[x].r-tree2[x].l+){
tree2[x<<].ml=tree2[x<<].mr=tree2[x<<].m=mid-tree2[x].l+;
tree2[x<<|].mr=tree2[x<<|].ml=tree2[x<<|].m=tree2[x].r-mid;
}
else if(tree2[x].m==){
tree2[x<<].ml=tree2[x<<].mr=tree2[x<<].m=;
tree2[x<<|].mr=tree2[x<<|].ml=tree2[x<<|].m=;
}
}
void update(int x,int l,int r,int value){
if(tree1[x].l>=l&&tree1[x].r<=r){
if(value==){
tree1[x].ml=tree1[x].mr=tree1[x].m=;
}
else if(value==){
tree1[x].ml=tree1[x].mr=tree1[x].m=;
tree2[x].ml=tree2[x].mr=tree2[x].m=;
}
else {
tree1[x].ml=tree1[x].mr=tree1[x].m=tree1[x].r-tree1[x].l+;
tree2[x].ml=tree2[x].mr=tree2[x].m=tree1[x].r-tree1[x].l+;
}
return ;
}
int mid=tree1[x].l+tree1[x].r>>;
push_down(x);
if(mid>=l)update(x<<,l,r,value);
if(mid<r)update(x<<|,l,r,value);
push_up(x);
}
int query(int x,int length,int value){
if(tree1[x].l==tree1[x].r)return tree1[x].l;
push_down(x);
int mid=tree1[x].l+tree1[x].r>>;
if(value==){
if(tree1[x<<].m>=length){
return query(x<<,length,value);
}
else if(tree1[x<<].mr+tree1[x<<|].ml>=length){
return mid-tree1[x<<].mr+;
}
else return query(x<<|,length,value);
}
else {
if(tree2[x<<].m>=length){
return query(x<<,length,value);
}
else if(tree2[x<<].mr+tree2[x<<|].ml>=length){
return mid-tree2[x<<].mr+;
}
else return query(x<<|,length,value);
}
}
int main(){
int t;
int kase=;
scanf("%d",&t);
char s[];
int temp;
int q;
int n;
while(t--){
printf("Case %d:\n",kase++);
scanf("%d%d",&n,&q);
build(,,n);
while(q--){
scanf("%s%d",s,&temp);
if(s[]=='D'){
if(tree1[].m>=temp){
int start=query(,temp,);
update(,start,start+temp-,);
printf("%d,let's fly\n",start);
}
else printf("fly with yourself\n");
}
else if(s[]=='N'){
if(tree1[].m>=temp){
int start=query(,temp,);
update(,start,start+temp-,);
printf("%d,don't put my gezi\n",start);
}
else if(tree2[].m>=temp){
int start=query(,temp,);
update(,start,start+temp-,);
printf("%d,don't put my gezi\n",start);
}
else printf("wait for me\n");
}
else {
int zz;
scanf("%d",&zz);
update(,temp,zz,);
printf("I am the hope of chinese chengxuyuan!!\n");
}
} }
return ;
}