hdu4614 Vases and Flowers 线段树

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

Alice is so popular that she can receive many flowers everyday. She has N vases numbered from 0 to N-1. When she receive some flowers, she will try to put them in the vases, one flower in one vase. She randomly choose the vase A and try to put a flower in the vase. If the there is no flower in the vase, she will put a flower in it, otherwise she skip this vase. And then she will try put in the vase A+1, A+2, ..., N-1, until there is no flower left or she has tried the vase N-1. The left flowers will be discarded. Of course, sometimes she will clean the vases. Because there are too many vases, she randomly choose to clean the vases numbered from A to B(A <= B). The flowers in the cleaned vases will be discarded.

题意：有 0~n-1 共 n 个花瓶，一个花瓶可以插一束花，现在有两个操作，一个是从 A 号花瓶开始插 k 束花，若花瓶有花就顺延到下一个花瓶，直到插完 k 束花或插完 n-1 号花瓶，问她插的第一个和最后一个花瓶编号。第二个操作是清空一段区间的花，问共丢掉多少花。

线段树保存区间空瓶数、首个空瓶和末个空瓶。树上二分查找 k 个空瓶，并更新最大最小空瓶位置。区间清除。

 #include<stdio.h>

 #include<string.h>

 const int maxm=;

 const int INF=0x3f3f3f3f;

 int st[maxm<<],ma[maxm<<],mi[maxm<<];

 int ch[maxm<<];

 int maxx,minn,k;

 inline int max(int a,int b){return a>b?a:b;}

 inline int min(int a,int b){return a<b?a:b;}

 void build(int o,int l,int r){

     ma[o]=r;

     mi[o]=l;

     st[o]=r-l+;

     ch[o]=;

     if(l==r)return;

     int m=l+((r-l)>>);

     build(o<<,l,m);

     build(o<<|,m+,r);

 }

 void pushdown(int o,int l,int r){

     if(ch[o]==){

         ch[o<<]=ch[o<<|]=;

         int m=l+((r-l)>>);

         st[o<<]=st[o<<|]=;

         ma[o<<]=ma[o<<|]=-;

         mi[o<<]=mi[o<<|]=INF;

         ch[o]=;

     }

     else if(ch[o]==){

         ch[o<<]=ch[o<<|]=;

         int m=l+((r-l)>>);

         st[o<<]=m-l+;

         st[o<<|]=r-m;

         ma[o<<]=m;

         ma[o<<|]=r;

         mi[o<<]=l;

         mi[o<<|]=m+;

         ch[o]=;

     }

 }

 void update1(int o,int l,int r,int ql,int qr){

     if(ql<=l&&qr>=r){

         if(k>=st[o]){

             k-=st[o];

             maxx=max(maxx,ma[o]);

             minn=min(minn,mi[o]);

             ma[o]=-;

             mi[o]=INF;

             st[o]=;

             ch[o]=;

             return;

         }

         else if(l==r)return;

     }

     pushdown(o,l,r);

     int m=l+((r-l)>>);

     if(ql<=m&&k)update1(o<<,l,m,ql,qr);

     if(qr>=m+&&k)update1(o<<|,m+,r,ql,qr);

     ma[o]=max(ma[o<<],ma[o<<|]);

     mi[o]=min(mi[o<<],mi[o<<|]);

     st[o]=st[o<<]+st[o<<|];

 }

 int update2(int o,int l,int r,int ql,int qr){

     if(ql<=l&&qr>=r){

         int ans=r-l+-st[o];

         st[o]=r-l+;

         ma[o]=r;

         mi[o]=l;

         ch[o]=;

         return ans;

     }

     pushdown(o,l,r);

     int m=l+((r-l)>>);

     int ans=;

     if(ql<=m)ans+=update2(o<<,l,m,ql,qr);

     if(qr>=m+)ans+=update2(o<<|,m+,r,ql,qr);

     ma[o]=max(ma[o<<],ma[o<<|]);

     mi[o]=min(mi[o<<],mi[o<<|]);

     st[o]=st[o<<]+st[o<<|];

     return ans;

 }

 int main(){

     int T;

     scanf("%d",&T);

     while(T--){

         int n,m;

         scanf("%d%d",&n,&m);

         build(,,n-);

         for(int i=;i<=m;++i){

             int t;

             scanf("%d",&t);

             if(t==){

                 int a;

                 scanf("%d%d",&a,&k);

                 maxx=-;

                 minn=INF;

                 update1(,,n-,a,n-);

                 if(maxx==-&&minn==INF)printf("Can not put any one.\n");

                 else printf("%d %d\n",minn,maxx);

             }

             else if(t==){

                 int a,b;

                 scanf("%d%d",&a,&b);

                 printf("%d\n",update2(,,n-,a,b));

             }

         }

         printf("\n");

     }

     return ;

 }