hdu 4614 线段树

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4614
  1 #include <cstdio>
  2 #include <cmath>
  3 #include <algorithm>
  4 #include <iostream>
  5 #include <cstring>
  6 #include <queue>
  7 #include <vector>
  8 
  9 #define maxn 105000
 10 #define lson l,mid,u<<1
 11 #define rson mid+1,r,u<<1|1
 12 using namespace std;
 13 
 14 int seg[maxn<<2];
 15 int pau[maxn<<2];
 16 
 17 void PushDown(int l,int r,int u){
 18     if(pau[u] == 1){
 19         pau[u<<1] = pau[u<<1|1] = 1;   
 20         int mid = (l + r)>>1;
 21         seg[u<<1]   = (mid - l + 1);
 22         seg[u<<1|1] = (r - mid);
 23         pau[u] = -1 ;
 24     }
 25     else if(pau[u] == 0){
 26         pau[u<<1] = pau[u<<1|1] = 0;   
 27         int mid = (l + r)>>1;
 28         seg[u<<1]   = 0;
 29         seg[u<<1|1] = 0;
 30         pau[u] = -1 ;
 31     }
 32 }
 33 void PushUp(int u){
 34     seg[u] = seg[u<<1] + seg[u<<1|1];
 35 }
 36 void build(int l,int r,int u){
 37     pau[u] = -1;
 38     seg[u] = 0; 
 39     if(l == r){
 40         return;
 41     }
 42     int mid = (l + r)>>1;
 43     build(lson);
 44     build(rson);
 45 }
 46 void Update(int L,int R,int num,int l,int r,int u){
 47     if(L <= l && r <= R){
 48         pau[u] = num;
 49         seg[u] =(r - l + 1)*num;
 50         return;
 51     }
 52     PushDown(l,r,u);
 53     int mid = (l + r)>>1;
 54     if(L <= mid)    Update(L,R,num,lson);
 55     if(R >  mid)    Update(L,R,num,rson);
 56     PushUp(u);
 57 }
 58 int  Query(int L,int R,int l,int r,int u){
 59     if(L <= l && r <= R){
 60         return seg[u];
 61     }
 62     PushDown(l,r,u);
 63     int mid = (l + r)>>1;
 64     int ret = 0;
 65     if(L <= mid)  ret += Query(L,R,lson);
 66     if(R >  mid)  ret += Query(L,R,rson);
 67     return ret;
 68 }
 69 int bin_ser(int L,int R,int num,int N){ 
 70    //搜索0在L~R中第num次出现的位置； 
 71     int start = L;
 72     while(L < R){
 73         int mid = (L + R)/2;
 74         int temp = Query(start,mid,0,N-1,1);
 75         if(mid - start + 1 >= temp + num )
 76            R = mid;
 77         else
 78            L = mid + 1;  
 79     }
 80     return L;
 81 }
 82 int main()
 83 {
 84     if(freopen("input.txt","r",stdin)== NULL)  {printf("Error
"); exit(0);}
 85     int T;
 86     cin>>T; 
 87     int N,M,K;
 88     while(T--){
 89         scanf("%d%d",&N,&M);
 90         //build(0,N-1,1);    
 91         memset(pau,-1,sizeof(pau)); 
 92         memset(seg,0,sizeof(seg));   //两种方法都可以；都要写对。没想到会犯低级错害的Wa 
 93         for(int i=1;i<=M;i++){
 94             int a,b;
 95             int s,t;
 96             scanf("%d%d%d",&K,&a,&b);
 97             if(K == 1){  
 98                int right_sum =Query(a,N-1,0,N-1,1); //printf("res %d
",res);
 99                if(right_sum == N - a){
100                      printf("Can not put any one.
");
101                   }
102                else{
103                      int left_sum  = a==0 ? 0 : Query(0,a-1,0,N-1,1);
104                   s = bin_ser(0,N-1,a-left_sum+1,N);
105                     t = bin_ser(a,N-1,min(N - a - right_sum, b),N);
106                      
107                      printf("%d %d
",s,t);
108                      Update(s,t,1,0,N-1,1);
109                }
110             }
111             else{
112                printf("%d
",Query(a,b,0,N-1,1));
113                Update(a,b,0,0,N-1,1);    
114             } 
115         }
116         printf("
");
117     }
118 }
View Code