L - Vases and Flowers HDU - 4614 线段树+二分

题意给出一排空花瓶有两种操作 1是从A花瓶开始放F朵花如果当前瓶有花就跳过前往下一个直到花用完或者瓶子到了最后一个为止输出成功放花的第一个和最后一个如果没有输出 can not.......

2是清空一段区间的花并输出清空了多少朵花

思路：用线段树维护一段区间有多少空花瓶 1操作就是两次二分分别求起点和终点起点 check条件是 query(1,a,mid)>0 终点是 query(1,二分出的起点，mid)>=min(f,query(1,a,n-1)) 这里min是因为有可能总共就没有那么多空瓶子而二分要求的是最后一个放的空瓶子如果不min 一旦不够每次二分出的都是n-1就不符合题意了

还有就是吐槽一下vj爬网页爬出 [pre]到输出了我说怎么会有那么奇葩的输出。。。

 #include<bits/stdc++.h>

 using namespace std;

 const int maxn=+;

 int n;

 struct Node{

     int l,r;

     long long sum;

     int flag=-;

     void update(int value){

         if(value==){

         sum=r-l+;

         flag=;

         }else if(value==){

             sum=;

             flag=;

         }

     }

 }tree[maxn*];

 void push_up(int x){

     tree[x].sum=tree[x<<].sum+tree[x<<|].sum;

 }

 void push_down(int x){

     if(tree[x].flag==){

         tree[x<<].sum=tree[x<<].r-tree[x<<].l+;

         tree[x<<|].sum=tree[x<<|].r-tree[x<<|].l+;

         tree[x<<|].flag=tree[x<<].flag=;

         tree[x].flag=-;

     }

     else if(tree[x].flag==){

         tree[x<<].sum=;

         tree[x<<|].sum=;

         tree[x<<|].flag=tree[x<<].flag=;

         tree[x].flag=-;

     }

 }

 void update(int x,int l,int r,int value){

     if(tree[x].l>=l&&tree[x].r<=r){

         tree[x].update(value);

             return ;

     }

     int mid=tree[x].l+tree[x].r>>;

     push_down(x);

     if(mid>=l)update(x<<,l,r,value);

     if(mid<r)update(x<<|,l,r,value);

     push_up(x);

 }

 int  query(int x,int l,int r){

     if(tree[x].l>=l&&tree[x].r<=r){

     return     tree[x].sum;

     }

     int mid=tree[x].l+tree[x].r>>;

     push_down(x);

     long long ans=;

     if(mid>=l)ans+=query(x<<,l,r);

     if(mid<r)ans+=query(x<<|,l,r);

     return ans;

 }

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

     tree[x].l=l,tree[x].r=r;

     tree[x].sum=r-l+;

     tree[x].flag=-;

     if(l==r)return ;

     int mid=l+r>>;

     build(x<<,l,mid);

     build(x<<|,mid+,r);

 }

 void work(int a,int f){

     int l=a,r=n-;

     int ans1=-;

     int temp=query(,a,n-);

     if(temp==){

         printf("Can not put any one.\n");

         return ;

     }

     while(l<=r){

         int mid=l+r>>;

         if(query(,a,mid)!=){

             ans1=mid;

             r=mid-;

         }

         else l=mid+;

     }

     l=ans1,r=n-;

     int ans2=-;

     f=min(f,temp);

     while(l<=r){

         int mid=l+r>>;

         if(query(,ans1,mid)>=f){

             ans2=mid;

             r=mid-;

         }

         else l=mid+;

     }

     printf("%d %d\n",ans1,ans2);

     update(,ans1,ans2,);

 }

 int main(){

     int t ,m;

     scanf("%d",&t);

     while(t--){

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

         build(,,n-);

         int a,b,c;

         while(m--){

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

         if(a==){

             work(b,c);

         }

         if(a==){

             printf("%d\n",c-b+-query(,b,c));

             update(,b,c,);

         }

         }

         printf("\n");

     }

     return ;

 }

巴特西

L - Vases and Flowers HDU - 4614 线段树+二分

最新文章

热门文章