http://www.mamicode.com/info-detail-422707.html
线段树区间覆盖，开两个线段树，一个记录DS，一个NS
1 // #pragma comment(linker, "/STACK:1024000000,1024000000") 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <sstream> 6 #include <string> 7 #include <algorithm> 8 #include <list> 9 #include <map> 10 #include <vector> 11 #include <queue> 12 #include <stack> 13 #include <cmath> 14 #include <cstdlib> 15 #include <conio.h> 16 using namespace std; 17 #define clc(a,b) memset(a,b,sizeof(a)) 18 #define inf 0x3f3f3f3f 19 #define lson l,mid,rt<<1 20 #define rson mid+1,r,rt<<1|1 21 const int N = 100010; 22 const int MOD = 1e9+7; 23 #define LL long long 24 #define mi() (l+r)>>1 25 double const pi = acos(-1); 26 void fre() { 27 freopen("in.txt","r",stdin); 28 } 29 // inline int r() { 30 // int x=0,f=1;char ch=getchar(); 31 // while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();} 32 // while(ch>='0'&&ch<='9') { x=x*10+ch-'0';ch=getchar();}return x*f; 33 // } 34 struct Edge { 35 int l,r; 36 int lazy; 37 int lm,rm,mm; 38 } e1[N<<2],e2[N<<2]; 39 40 void pushdown(Edge e[],int rt) { 41 if(e[rt].lazy!=-1) { 42 if(e[rt].lazy==0) { 43 e[rt<<1].lm=e[rt<<1].rm=e[rt<<1].mm=e[rt<<1].r-e[rt<<1].l+1; 44 e[rt<<1|1].rm=e[rt<<1|1].lm=e[rt<<1|1].mm=e[rt<<1|1].r-e[rt<<1|1].l+1; 45 e[rt<<1].lazy=e[rt<<1|1].lazy=0; 46 } else { 47 e[rt<<1].lm=e[rt<<1].rm=e[rt<<1].mm=0; 48 e[rt<<1|1].rm=e[rt<<1|1].lm=e[rt<<1|1].mm=0; 49 e[rt<<1].lazy=e[rt<<1|1].lazy=1; 50 } 51 e[rt].lazy=-1; 52 } 53 } 54 55 void pushup(Edge e[],int rt) { 56 e[rt].lm=e[rt<<1].lm; 57 e[rt].rm=e[rt<<1|1].rm; 58 if(e[rt<<1].lm==e[rt<<1].r-e[rt<<1].l+1) { 59 e[rt].lm+=e[rt<<1|1].lm; 60 } 61 if(e[rt<<1|1].rm==e[rt<<1|1].r-e[rt<<1|1].l+1) { 62 e[rt].rm+=e[rt<<1].rm; 63 } 64 e[rt].mm=max(max(e[rt<<1].mm,e[rt<<1|1].mm),e[rt<<1].rm+e[rt<<1|1].lm); 65 } 66 void build(int l,int r,int rt,Edge a[]) { 67 a[rt].l=l; 68 a[rt].r=r; 69 a[rt].lm=a[rt].rm=a[rt].mm=(r-l+1); 70 a[rt].lazy=-1; 71 if(l==r) 72 return; 73 int mid=mi(); 74 build(lson,a); 75 build(rson,a); 76 } 77 78 void update(Edge e[],int l,int r,int rt,int x) { 79 if(e[rt].l==l&&e[rt].r==r) { 80 if(x==0) { 81 e[rt].lm=e[rt].rm=e[rt].mm=r-l+1; 82 e[rt].lazy=0; 83 } else { 84 e[rt].lm=e[rt].rm=e[rt].mm=0; 85 e[rt].lazy=1; 86 } 87 return; 88 } 89 pushdown(e,rt); 90 int mid=(e[rt].l+e[rt].r)>>1; 91 if(r<=mid) update(e,l,r,rt<<1,x); 92 else if(l>mid) update(e,l,r,rt<<1|1,x); 93 else { 94 update(e,l,mid,rt<<1,x); 95 update(e,mid+1,r,rt<<1|1,x); 96 } 97 pushup(e,rt); 98 } 99 100 int query(Edge e[],int rt,int c) { 101 if(e[rt].l==e[rt].r) { 102 return e[rt].l; 103 } 104 pushdown(e,rt); 105 int mid=(e[rt].l+e[rt].r)>>1; 106 if(e[rt<<1].mm>=c) { 107 return query(e,rt<<1,c); 108 } else if(e[rt<<1].rm+e[rt<<1|1].lm>=c) { 109 return mid-e[rt<<1].rm+1; 110 } else { 111 return query(e,rt<<1|1,c); 112 } 113 } 114 int main() { 115 // fre(); 116 int T; 117 int cas=1; 118 cin>>T; 119 while(T--) { 120 printf("Case %d: ",cas++); 121 int n,q; 122 cin>>n>>q; 123 build(1,n,1,e1);//D 124 build(1,n,1,e2);//N 125 while(q--) { 126 char s[20]; 127 int x,y; 128 scanf("%s",s); 129 if(s[0]=='S') { 130 cin>>x>>y; 131 update(e1,x,y,1,0); 132 update(e2,x,y,1,0); 133 printf("I am the hope of chinese chengxuyuan!! "); 134 } else if(s[0]=='D') { 135 cin>>x; 136 if(e1[1].mm<x) { 137 printf("fly with yourself "); 138 } else { 139 int s=query(e1,1,x); 140 printf("%d,let's fly ",s); 141 update(e1,s,s+x-1,1,1); 142 } 143 } else { 144 cin>>x; 145 if(e1[1].mm>=x) { 146 int s=query(e1,1,x); 147 printf("%d,don't put my gezi ",s); 148 update(e1,s,s+x-1,1,1); 149 update(e2,s,s+x-1,1,1); 150 } else if(e2[1].mm>=x) { 151 int s=query(e2,1,x); 152 printf("%d,don't put my gezi ",s); 153 update(e1,s,s+x-1,1,1); 154 update(e2,s,s+x-1,1,1); 155 } else { 156 printf("wait for me "); 157 } 158 } 159 } 160 } 161 return 0; 162 }