首页 > 代码库 > hdu 4614 Vases and Flowers
hdu 4614 Vases and Flowers
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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。