HDU-4614 Vases and Flowers 线段树区间更新

　　题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4614
　　线段树保存区间是否被覆盖以及区间的和即可，在询问的时候在线段树上二分查找就可以了。。。代码写得比较挫><
  1 //STATUS:C++_AC_359MS_1728KB
  2 #include <functional>
  3 #include <algorithm>
  4 #include <iostream>
  5 //#include <ext/rope>
  6 #include <fstream>
  7 #include <sstream>
  8 #include <iomanip>
  9 #include <numeric>
 10 #include <cstring>
 11 #include <cassert>
 12 #include <cstdio>
 13 #include <string>
 14 #include <vector>
 15 #include <bitset>
 16 #include <queue>
 17 #include <stack>
 18 #include <cmath>
 19 #include <ctime>
 20 #include <list>
 21 #include <set>
 22 #include <map>
 23 #pragma comment(linker,"/STACK:102400000,102400000")
 24 using namespace std;
 25 //using namespace __gnu_cxx;
 26 //define
 27 #define pii pair<int,int>
 28 #define mem(a,b) memset(a,b,sizeof(a))
 29 #define lson l,mid,rt<<1
 30 #define rson mid+1,r,rt<<1|1
 31 #define PI acos(-1.0)
 32 //typedef
 33 typedef __int64 LL;
 34 typedef unsigned __int64 ULL;
 35 //const
 36 const int N=50010,M=2000010;
 37 const int INF=0x3f3f3f3f;
 38 const int MOD=100000,STA=8000010;
 39 const LL LNF=1LL<<60;
 40 const double EPS=1e-8;
 41 const double OO=1e15;
 42 const int dx[4]={-1,0,1,0};
 43 const int dy[4]={0,1,0,-1};
 44 const int day[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
 45 //Daily Use ...
 46 inline int sign(double x){return (x>EPS)-(x<-EPS);}
 47 template<class T> T gcd(T a,T b){return b?gcd(b,a%b):a;}
 48 template<class T> T lcm(T a,T b){return a/gcd(a,b)*b;}
 49 template<class T> inline T lcm(T a,T b,T d){return a/d*b;}
 50 template<class T> inline T Min(T a,T b){return a<b?a:b;}
 51 template<class T> inline T Max(T a,T b){return a>b?a:b;}
 52 template<class T> inline T Min(T a,T b,T c){return min(min(a, b),c);}
 53 template<class T> inline T Max(T a,T b,T c){return max(max(a, b),c);}
 54 template<class T> inline T Min(T a,T b,T c,T d){return min(min(a, b),min(c,d));}
 55 template<class T> inline T Max(T a,T b,T c,T d){return max(max(a, b),max(c,d));}
 56 //End
 57 
 58 int c[N<<2],sum[N<<2];
 59 int T,n,m,a,b,tot,w;
 60 
 61 void pushup(int rt)
 62 {
 63     sum[rt]=sum[rt<<1]+sum[rt<<1|1];
 64     if(c[rt<<1]==c[rt<<1|1] && c[rt<<1]!=-1)c[rt]=c[rt<<1];
 65     else c[rt]=-1;
 66 }
 67 
 68 void pushdown(int rt,int l,int r,int mid)
 69 {
 70     c[rt<<1]=c[rt<<1|1]=c[rt];
 71     sum[rt<<1]=(mid-l+1)*(!c[rt]);
 72     sum[rt<<1|1]=(r-mid)*(!c[rt]);
 73 }
 74 
 75 void build(int l,int r,int rt)
 76 {
 77     if(l==r){
 78         sum[rt]=1;
 79         return;
 80     }
 81     int mid=(l+r)>>1;
 82     build(lson);
 83     build(rson);
 84     sum[rt]=r-l+1;
 85 }
 86 
 87 void update(int l,int r,int rt,int val)
 88 {
 89     if(a<=l && r<=b){
 90         c[rt]=val;
 91         sum[rt]=(r-l+1)*(!val);
 92         return ;
 93     }
 94     int mid=(l+r)>>1;
 95     if(c[rt]!=-1)pushdown(rt,l,r,mid);
 96     if(a<=mid)update(lson,val);
 97     if(b>mid)update(rson,val);
 98     pushup(rt);
 99 }
100 
101 int query_sum(int l,int r,int rt)
102 {
103     if(a<=l && r<=b){
104         return sum[rt];
105     }
106     int mid=(l+r)>>1,tot=0;
107     if(c[rt]!=-1)pushdown(rt,l,r,mid);
108     if(a<=mid)tot+=query_sum(lson);
109     if(b>mid)tot+=query_sum(rson);
110     return tot;
111 }
112 
113 void queryw(int l,int r,int rt)
114 {
115     if(l==r){
116         w=l;
117         tot-=sum[rt];
118         return;
119     }
120     int mid=(l+r)>>1;
121     if(c[rt]!=-1)pushdown(rt,l,r,mid);
122     if(sum[rt<<1]>=tot)queryw(lson);
123     else if(mid<a || (sum[rt<<1]<tot && sum[rt<<1|1])){
124         tot-=sum[rt<<1];
125         queryw(rson);
126     }
127     else queryw(lson);
128     pushup(rt);
129 }
130 
131 int main()
132 {
133  //   freopen("in.txt","r",stdin);
134     int i,j,op,x,y;
135     scanf("%d",&T);
136     while(T--)
137     {
138         scanf("%d%d",&n,&m);
139         n--;
140         mem(c,0);
141         build(0,n,1);
142         while(m--){
143             scanf("%d%d%d",&op,&x,&y);
144             if(op==1){
145                 tot=y;
146                 int t;
147                 if(x>0){
148                     a=0,b=x-1;
149                     t=query_sum(0,n,1);
150                     tot+=t;
151                 }
152                 else t=0;
153                 a=x;
154                 queryw(0,n,1);
155                 if(tot==y)
156                     printf("Can not put any one.
");
157                 else {
158                     int en=w;
159                     a=x;tot=t+1;
160                     queryw(0,n,1);
161                     printf("%d %d
",w,en);
162                     a=w,b=en;
163                     update(0,n,1,1);
164                 }
165             }
166             else {
167                 a=x,b=y;
168                 printf("%d
",b-a+1-query_sum(0,n,1));
169                 update(0,n,1,0);
170             }
171         }
172         putchar('
');
173     }
174     return 0;
175 }