首页 > 代码库 > hdu 4614 Vases and Flowers

hdu 4614 Vases and Flowers

2024-07-17 05:35:03   220人阅读

http://acm.hdu.edu.cn/showproblem.php?pid=4614

题意：有N个花瓶，标号为0-N-1，往每一个花瓶放一朵花，然后有M个操作，输入a,b,c，如果a==1表示从b开始放花，期间有花就跳过，直到结束，如果没有放入一朵花，则输出“Can not put any one.”，否则输入第一朵花放的位置和最后一朵花放的位置。 如果a==2 则输出拔掉的花的朵数。

  1 #include <cstdio>  2 #include <cstring>  3 #include <algorithm>  4 #define maxn 500001  5 using namespace std;  6   7 int t,n,m;  8 struct node  9 { 10     int l,r; 11     int sum; 12     int add; 13 }tree[maxn*4]; 14  15 void build(int i,int l,int r) 16 { 17     tree[i].l=l; 18     tree[i].r=r; 19     tree[i].sum=0; 20     tree[i].add=-1; 21     if(l==r) return ; 22     int mid=(l+r)>>1; 23     build(i<<1,l,mid); 24     build(i<<1|1,mid+1,r); 25 } 26  27 void update(int i,int l,int r,int c) 28 { 29     if(tree[i].l==l&&tree[i].r==r) 30     { 31         tree[i].add=c; 32         tree[i].sum=(tree[i].r-tree[i].l+1)*c; 33         return ; 34     } 35     int mid=(tree[i].l+tree[i].r)>>1; 36     if(r<=mid) 37     { 38         update(i<<1,l,r,c); 39     } 40     else if(l>mid) 41     { 42         update(i<<1|1,l,r,c); 43     } 44     else 45     { 46         update(i<<1,l,mid,c); 47         update(i<<1|1,mid+1,r,c); 48     } 49     tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum; 50 } 51  52 int search1(int i,int l,int r) 53 { 54     if(tree[i].l==l&&tree[i].r==r) 55     { 56         return tree[i].sum; 57     } 58     if(tree[i].add>=0) 59     { 60         tree[i<<1].sum=(tree[i<<1].r-tree[i<<1].l+1)*tree[i].add; 61         tree[i<<1|1].sum=(tree[i<<1|1].r-tree[i<<1|1].l+1)*tree[i].add; 62         tree[i<<1].add=tree[i].add; 63         tree[i<<1|1].add=tree[i].add; 64         tree[i].add=-1; 65     } 66     int mid=(tree[i].l+tree[i].r)>>1; 67     if(r<=mid) 68     { 69         return search1(i<<1,l,r); 70     } 71     else if(l>mid) 72     { 73         return search1(i<<1|1,l,r); 74     } 75     else 76     { 77         return search1(i<<1,l,mid)+search1(i<<1|1,mid+1,r); 78     } 79 } 80  81 int bs(int l,int r,int c) 82 { 83      int ll=l,rr=r; 84      while(l<rr) 85      { 86          int mid=(l+rr)>>1; 87          if(mid-ll+1>=search1(1,ll,mid)+c) 88          { 89              rr=mid; 90          } 91          else 92             l=mid+1; 93      } 94      return l; 95 } 96  97 int main() 98 { 99     scanf("%d",&t);100     while(t--)101     {102         scanf("%d%d",&n,&m);103         n--;104         build(1,0,n);105         for(int i=1; i<=m; i++)106         {107             int ch,a,b;108             scanf("%d%d%d",&ch,&a,&b);109             if(ch==1)110             {111                 int m1=search1(1,a,n);112                 if(n-a+1==m1)113                 {114                     printf("Can not put any one.\n");115                     continue;116                 }117                 int m2;118                 if(a==0) m2=0;119                 else m2=search1(1,0,a-1);120                 int l1=bs(0,n,a-m2+1);121                 int r1=bs(a,n,min(n-a-m1+1,b));122                 printf("%d %d\n",l1,r1);123                 update(1,l1,r1,1);124             }125             else if(ch==2)126             {127                 printf("%d\n",search1(1,a,b));128                 update(1,a,b,0);129             }130         }131         printf("\n");132     }133     return 0;134 }
View Code

 


联系
我们