http://www.mamicode.com/info-detail-422707.html
线段树区间覆盖，开两个线段树，一个记录DS，一个NS
// #pragma comment(linker, "/STACK:1024000000,1024000000")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <sstream>
#include <string>
#include <algorithm>
#include <list>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdlib>
#include <conio.h>
using namespace std;
#define clc(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
const int N = ;
const int MOD = 1e9+;
#define LL long long
#define mi() (l+r)>>1
double const pi = acos(-);
void fre() {
freopen("in.txt","r",stdin);
}
// inline int r() {
// int x=0,f=1;char ch=getchar();
// while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
// while(ch>='0'&&ch<='9') { x=x*10+ch-'0';ch=getchar();}return x*f;
// }
struct Edge {
int l,r;
int lazy;
int lm,rm,mm;
} e1[N<<],e2[N<<]; void pushdown(Edge e[],int rt) {
if(e[rt].lazy!=-) {
if(e[rt].lazy==) {
e[rt<<].lm=e[rt<<].rm=e[rt<<].mm=e[rt<<].r-e[rt<<].l+;
e[rt<<|].rm=e[rt<<|].lm=e[rt<<|].mm=e[rt<<|].r-e[rt<<|].l+;
e[rt<<].lazy=e[rt<<|].lazy=;
} else {
e[rt<<].lm=e[rt<<].rm=e[rt<<].mm=;
e[rt<<|].rm=e[rt<<|].lm=e[rt<<|].mm=;
e[rt<<].lazy=e[rt<<|].lazy=;
}
e[rt].lazy=-;
}
} void pushup(Edge e[],int rt) {
e[rt].lm=e[rt<<].lm;
e[rt].rm=e[rt<<|].rm;
if(e[rt<<].lm==e[rt<<].r-e[rt<<].l+) {
e[rt].lm+=e[rt<<|].lm;
}
if(e[rt<<|].rm==e[rt<<|].r-e[rt<<|].l+) {
e[rt].rm+=e[rt<<].rm;
}
e[rt].mm=max(max(e[rt<<].mm,e[rt<<|].mm),e[rt<<].rm+e[rt<<|].lm);
}
void build(int l,int r,int rt,Edge a[]) {
a[rt].l=l;
a[rt].r=r;
a[rt].lm=a[rt].rm=a[rt].mm=(r-l+);
a[rt].lazy=-;
if(l==r)
return;
int mid=mi();
build(lson,a);
build(rson,a);
} void update(Edge e[],int l,int r,int rt,int x) {
if(e[rt].l==l&&e[rt].r==r) {
if(x==) {
e[rt].lm=e[rt].rm=e[rt].mm=r-l+;
e[rt].lazy=;
} else {
e[rt].lm=e[rt].rm=e[rt].mm=;
e[rt].lazy=;
}
return;
}
pushdown(e,rt);
int mid=(e[rt].l+e[rt].r)>>;
if(r<=mid) update(e,l,r,rt<<,x);
else if(l>mid) update(e,l,r,rt<<|,x);
else {
update(e,l,mid,rt<<,x);
update(e,mid+,r,rt<<|,x);
}
pushup(e,rt);
} int query(Edge e[],int rt,int c) {
if(e[rt].l==e[rt].r) {
return e[rt].l;
}
pushdown(e,rt);
int mid=(e[rt].l+e[rt].r)>>;
if(e[rt<<].mm>=c) {
return query(e,rt<<,c);
} else if(e[rt<<].rm+e[rt<<|].lm>=c) {
return mid-e[rt<<].rm+;
} else {
return query(e,rt<<|,c);
}
}
int main() {
// fre();
int T;
int cas=;
cin>>T;
while(T--) {
printf("Case %d:\n",cas++);
int n,q;
cin>>n>>q;
build(,n,,e1);//D
build(,n,,e2);//N
while(q--) {
char s[];
int x,y;
scanf("%s",s);
if(s[]=='S') {
cin>>x>>y;
update(e1,x,y,,);
update(e2,x,y,,);
printf("I am the hope of chinese chengxuyuan!!\n");
} else if(s[]=='D') {
cin>>x;
if(e1[].mm<x) {
printf("fly with yourself\n");
} else {
int s=query(e1,,x);
printf("%d,let's fly\n",s);
update(e1,s,s+x-,,);
}
} else {
cin>>x;
if(e1[].mm>=x) {
int s=query(e1,,x);
printf("%d,don't put my gezi\n",s);
update(e1,s,s+x-,,);
update(e2,s,s+x-,,);
} else if(e2[].mm>=x) {
int s=query(e2,,x);
printf("%d,don't put my gezi\n",s);
update(e1,s,s+x-,,);
update(e2,s,s+x-,,);
} else {
printf("wait for me\n");
}
}
}
}
return ;
}