约会安排[HDU - 4553]( Problem - 4553 (hdu.edu.cn) ) T6 D24
思路：
线段树区间合并。线段树维护NS和DS的左连续区间和右连续区间，更新时按优先级顺序更新，学习>NS>DS
/*
#########
############
#############
## ###########
### ###### #####
### ####### ####
### ########## ####
#### ########### ####
##### ########### #####
###### ### ######## #####
##### ### ######## ######
###### ### ########### ######
###### #### ############## ######
####### ##################### #######
####### ##############################
####### ###### ################# #######
####### ###### ###### ######### ######
####### ## ###### ###### ######
####### ###### ##### #####
###### ##### ##### ####
##### #### ##### ###
##### ;### ### #
## #### ####
HDU - 4553 真折磨啊
*/
#include<iostream>
#include<algorithm>
#include<math.h>
#include<string>
#include<string.h>
#define ll long long
#define ls (p<<1)
#define rs ((p<<1)|1)
#define mid ((t[p].l+t[p].r)>>1)
using namespace std;
int read(){int x=0,f=1;char ch=getchar();while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘) f=-1;ch=getchar();}while(ch>=‘0‘&&ch<=‘9‘){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void Prin(int x){if(x < 0){putchar(‘-‘);x = -x;}if(x > 9) Prin(x / 10);putchar(x % 10 + ‘0‘);}
const int qs=2e5+7;
struct Tree{
int l,r,dl,dr,nl,nr,dsum,nsum,add,ann;
#define l(x) t[x].l
#define r(x) t[x].r
#define dl(x) t[x].dl
#define dr(x) t[x].dr
#define nl(x) t[x].nl
#define nr(x) t[x].nr
#define dsum(x) t[x].dsum
#define nsum(x) t[x].nsum
#define add(x) t[x].add
#define ann(x) t[x].ann
}t[qs<<2];
void pushup(int p){
dl(p)=dl(ls)+(dl(ls)==r(ls)-l(ls)+1 ? dl(rs) : 0);
dr(p)=dr(rs)+(dr(rs)==r(rs)-l(rs)+1 ? dr(ls) : 0);
dsum(p)=max(max(dsum(ls),dsum(rs)),dr(ls)+dl(rs));
nl(p)=nl(ls)+(nl(ls)==r(ls)-l(ls)+1 ? nl(rs) : 0);
nr(p)=nr(rs)+(nr(rs)==r(rs)-l(rs)+1 ? nr(ls) : 0);
nsum(p)=max(max(nsum(ls),nsum(rs)),nr(ls)+nl(rs));
}
void build(int p,int l,int r){
l(p)=l,r(p)=r;
add(p)=ann(p)=-1;
if(l==r) {
dl(p)=dr(p)=dsum(p)=1;
nl(p)=nr(p)=nsum(p)=1;
return;
}
build(ls,l,mid);
build(rs,mid+1,r);
pushup(p);
}
void down(int p){
if(add(p)!=-1){
dl(ls)=dr(ls)=dsum(ls)=(r(ls)-l(ls)+1)*add(p);
dl(rs)=dr(rs)=dsum(rs)=(r(rs)-l(rs)+1)*add(p);
add(ls)=add(rs)=add(p);
}
if(ann(p)!=-1){
nl(ls)=nr(ls)=nsum(ls)=(r(ls)-l(ls)+1)*ann(p);
nl(rs)=nr(rs)=nsum(rs)=(r(rs)-l(rs)+1)*ann(p);
ann(ls)=ann(rs)=ann(p);
}
add(p)=ann(p)=-1;
}
void update(int p,int l,int r,int k,int nk){
down(p);
if(l<=l(p)&&r>=r(p)){
dl(p)=dr(p)=dsum(p)=(r(p)-l(p)+1)*k;
if(nk!=-1) nl(p)=nr(p)=nsum(p)=(r(p)-l(p)+1)*nk;
add(p)=k;
ann(p)=nk;
return;
}
if(l<=mid) update(ls,l,r,k,nk);
if(r>mid) update(rs,l,r,k,nk);
pushup(p);
}
int ask(int p,int len,int k){
down(p);
if(l(p)==r(p)) return 1;
if(k==1){
if(dsum(ls)>=len) return ask(ls,len,k);
else if(dl(rs)+dr(ls)>=len) return mid-dr(ls)+1;
else return ask(rs,len,k);
}
else{
if(nsum(ls)>=len) return ask(ls,len,k);
else if(nl(rs)+nr(ls)>=len) return mid-nr(ls)+1;
else return ask(rs,len,k);
}
return 0;
}
int T,n,q;
int main(){
T=read();
for(int ti=1;ti<=T;++ti){
printf("Case %d:\n",ti);
n=read(),q=read();
build(1,1,n);
while(q--){
string s;
int l,len,r;
cin>>s;
if(s=="DS"){
len=read();
if(dsum(1)<len){
printf("fly with yourself\n");
continue;
}
int ans=ask(1,len,1);
printf("%d,let‘s fly\n",ans);
update(1,ans,ans+len-1,0,-1);
}
else if(s=="NS"){
len=read();
if(dsum(1)<len){
if(nsum(1)<len){
printf("wait for me\n");
continue;
}
int ans=ask(1,len,2);
printf("%d,don‘t put my gezi\n",ans);
update(1,ans,ans+len-1,0,0);
continue;
}
int ans=ask(1,len,1);
printf("%d,don‘t put my gezi\n",ans);
update(1,ans,ans+len-1,0,0);
}
else{
l=read(),r=read();
update(1,l,r,1,1);
printf("I am the hope of chinese chengxuyuan!!\n");
}
}
}
return 0;
}