线段树加二分查找

1 #include
     
        2 #include
      
         3 #include
       
          4 using namespace std;  5 const int maxn=50001;  6 const int INF=100000;  7 int sum[maxn<<2];  8 int left[maxn<<2];  9 int right[maxn<<2]; 10 int setv[maxn<<2]; 11 int ansl,ansr; 12 void push_up(int rt) 13 { 14     sum[rt]=sum[rt<<1]+sum[rt<<1|1]; 15     if(left[rt<<1]&&left[rt<<1|1]) 16     left[rt]=min(left[rt<<1],left[rt<<1|1]); 17     else if (left[rt<<1]) left[rt]=left[rt<<1]; 18     else if(left[rt<<1|1]) left[rt]=left[rt<<1|1]; 19     else left[rt]=0; 20  21     if(right[rt<<1]&&right[rt<<1|1]) 22     right[rt]=max(right[rt<<1],right[rt<<1|1]); 23     else if(right[rt<<1]) right[rt]=right[rt<<1]; 24     else if (right[rt<<1|1])right[rt]=right[rt<<1|1]; 25     else right[rt]=0; 26 } 27 void build(int l,int r,int rt) 28 { 29     if(l==r) 30     { 31         sum[rt]=0; 32         left[rt]=l;right[rt]=r; 33         return ; 34     } 35     int m=(l+r)>>1; 36     build(l,m,rt<<1); 37     build(m+1,r,rt<<1|1); 38     push_up(rt); 39 } 40 void push_down(int l,int r,int rt) 41 { 42     if(setv[rt]!=-1) 43     { 44         int len=r-l+1; 45         int m=(l+r)>>1; 46         sum[rt<<1]=setv[rt]*(len-len/2); 47         sum[rt<<1|1]=setv[rt]*(len/2); 48  49         if(sum[rt<<1]) left[rt<<1]=right[rt<<1]=0; 50         else {left[rt<<1]=l;right[rt<<1]=m;} 51  52         if(sum[rt<<1|1]) left[rt<<1|1]=right[rt<<1|1]=0; 53         else {left[rt<<1|1]=m+1;right[rt<<1|1]=r;} 54  55         setv[rt<<1]=setv[rt<<1|1]=setv[rt]; 56         setv[rt]=-1; 57     } 58 } 59 void update(int L ,int R,int v,int l,int r,int rt) 60 { 61     if(L<=l&&r<=R) 62     { 63         sum[rt]=v*(r-l+1); 64         if(sum[rt]) left[rt]=right[rt]=0; 65         else {left[rt]=l;right[rt]=r;} 66         setv[rt]=v; 67         return; 68     } 69     push_down(l,r,rt); 70     int m=(l+r)>>1; 71     if(L<=m) update(L,R,v,l,m,rt<<1); 72     if(R>m) update(L,R,v,m+1,r,rt<<1|1); 73     push_up(rt); 74 } 75 int query(int L,int R,int l,int r,int rt) 76 { 77     if(L<=l&&r<=R) 78     { 79         if(left[rt]) 80         ansl=min(ansl,left[rt]); 81         if(right[rt]) 82         ansr=max(ansr,right[rt]); 83         return sum[rt]; 84     } 85     push_down(l,r,rt); 86     int m=(l+r)>>1; 87     int ret=0; 88     if(L<=m) ret+=query(L,R,l,m,rt<<1); 89     if(R>m) ret+=query(L,R,m+1,r,rt<<1|1); 90     return ret; 91 } 92 int main() 93 { 94     int t; 95     scanf("%d",&t); 96     while(t--) 97     { 98         memset(sum,0,sizeof(sum)); 99         memset(left,0,sizeof(left));100         memset(right,0,sizeof(right));101         memset(setv,-1,sizeof(setv));102         int n,m;103         scanf("%d%d",&n,&m);104         build(1,n,1);105         while(m--)106         {107             int com,a,b;108             scanf("%d%d%d",&com,&a,&b);109             if(com==1)110             {111                 ansl=INF;ansr=-INF;112                 a++;113                 int len=n-a+1;114               if(query(a,n,1,n,1)==len)115               {116                   printf("Can not put any one.\n");117                   continue;118               }119               if(b>len-query(a,n,1,n,1))120                {121                    printf("%d %d\n",ansl-1,ansr-1);122                    update(a,n,1,1,n,1);123                    continue;124                }125                int l=a,r=n;126                while(l
        
         >1;129                    int len=mid-a+1;130                    if(b<=len-query(a,mid,1,n,1))131                      r=mid;132                    else133                      l=mid+1;134                }135                printf("%d %d\n",ansl-1,l-1);136                update(a,l,1,1,n,1);137             }138             else139             {140                 printf("%d\n",query(a+1,b+1,1,n,1));141                 update(a+1,b+1,0,1,n,1);142             }143         }144          printf("\n");145     }146     return 0;147 }