http://acm.hdu.edu.cn/showproblem.php?pid=4614
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
2 10 5 1 3 5 2 4 5 1 1 8 2 3 6 1 8 8 10 6 1 2 5 2 3 4 1 0 8 2 2 5 1 4 4 1 2 3
3 7 2 1 9 4 Can not put any one. 2 6 2 0 9 4 4 5 2 3
题目大意：
有n个花瓶，标号0 ~ n−1。有m个操作，
‘1 A F′，表示从A位置开始插F朵花，遇到有花的花瓶跳过。到最后一个花瓶都还有花剩余，丢弃剩下的花。
‘2 A B′，表示将区间[A,B]内的花瓶全部清空。(A≤B)
对于每个1操作，输出第一个和最后一个插花的位置，如果一朵花都插不了，输出‘Can not put any one.’；对于每个2操作，输出区间[A,B]内被清空的花瓶的数量。
解题思路：
直接线段树存区间内的空花瓶数量。原来标号0 ~ n−1，但我线段树序号习惯了1 ~ n。
设num(l,r)为区间[l,r]的空花瓶数。
对于一个1操作，首先判一下num(A,n)是否大于0。
因为区间[A,n]的空花瓶数是单调不递减的，所以可以通过二分查找到 一个最小的位置L，使得num(A,L)=1，则此时的L就是第一个插花的位置。
同样二分找到一个最小的位置R，使得num(A,R)=min(F,num(A,n))，则此时的R就是最后一个插花的位置。（输出时记得减1）
对于一个2操作，直接询问区间[A,B]的空花瓶数，拿总数一减，输出，然后更新区间即可。
代码如下：
1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4 #include <string> 5 #include <math.h> 6 #include <algorithm> 7 #include <vector> 8 #include <queue> 9 #include <set> 10 #include <stack> 11 #include <map> 12 #include <math.h> 13 const int INF=0x3f3f3f3f; 14 typedef long long LL; 15 const int mod=1e9+7; 16 const int maxn=1e5+10; 17 using namespace std; 18 19 struct SegTree_node 20 { 21 int l; 22 int r; 23 int num;//区间内空瓶的数量 24 int tag;//如果为-1则为初始状态,不用向下更新，如果为0意思将子区间内的花清空，为1为插满花 25 }SegTree[50005<<2]; 26 27 int n,m; 28 29 void PushUp(int rt)//向上传递区间信息 30 { 31 SegTree[rt].num=SegTree[rt<<1].num+SegTree[rt<<1|1].num; 32 } 33 34 void PushDown(int rt)//向下传递状态 35 { 36 if(SegTree[rt].tag!=-1) 37 { 38 SegTree[rt<<1].tag=SegTree[rt<<1|1].tag=SegTree[rt].tag; 39 int mid=(SegTree[rt].l+SegTree[rt].r)>>1; 40 SegTree[rt<<1].num=(mid-SegTree[rt].l+1)*SegTree[rt].tag; 41 SegTree[rt<<1|1].num=(SegTree[rt].r-mid)*SegTree[rt].tag; 42 SegTree[rt].tag=-1; 43 } 44 } 45 46 void Build(int l,int r,int rt) 47 { 48 SegTree[rt].l=l; 49 SegTree[rt].r=r; 50 SegTree[rt].num=r-l+1; 51 SegTree[rt].tag=-1; 52 if(l==r) 53 return ; 54 int mid=(l+r)>>1; 55 Build(l,mid,rt<<1); 56 Build(mid+1,r,rt<<1|1); 57 } 58 59 void Update(int L,int R,int f,int rt) 60 { 61 int l=SegTree[rt].l; 62 int r=SegTree[rt].r; 63 if(L<=l&&R>=r) 64 { 65 SegTree[rt].num=(r-l+1)*f;//先计算 66 SegTree[rt].tag=f;//标记当前区间 67 return ; 68 } 69 if(l==r)//不要忘记 70 return ; 71 PushDown(rt);//向下传递状态 72 int mid=(l+r)>>1; 73 if(L<=mid) 74 Update(L,R,f,rt<<1); 75 if(R>mid) 76 Update(L,R,f,rt<<1|1); 77 PushUp(rt); 78 } 79 80 int Query(int L,int R,int rt)//得到区间[L,R]中的空花瓶数 81 { 82 int l=SegTree[rt].l; 83 int r=SegTree[rt].r; 84 if(R<l||L>r) 85 return 0; 86 if(L<=l&&R>=r) 87 return SegTree[rt].num; 88 PushDown(rt); 89 int mid=(l+r)>>1; 90 int sum=0; 91 if(L<=mid) 92 sum+=Query(L,R,rt<<1); 93 if(R>mid) 94 sum+=Query(L,R,rt<<1|1); 95 return sum; 96 } 97 98 int dive(int x,int num)//二分查找，第一个为开始的位置，第二个参数为要插花的个数 99 { 100 int l=x; 101 int r=n; 102 int ans=0; 103 while(l<=r) 104 { 105 int mid=(l+r)>>1; 106 if(Query(x,mid,1)>=num) 107 { 108 ans=mid; 109 r=mid-1; 110 } 111 else 112 l=mid+1; 113 } 114 return ans; 115 } 116 117 int main() 118 { 119 int T; 120 scanf("%d",&T); 121 while(T--) 122 { 123 scanf("%d %d",&n,&m); 124 Build(1,n,1); 125 for(int i=1;i<=m;i++) 126 { 127 int op; 128 scanf("%d",&op); 129 if(op==1) 130 { 131 int A,F; 132 scanf("%d %d",&A,&F); 133 A++;//存储时序号从一开始，故序号要全加一，下同 134 int cnt=Query(A,n,1);//得到区间[A, n]中的空花瓶数 135 if(cnt==0) 136 printf("Can not put any one.\n"); 137 else 138 { 139 int L=dive(A,1);//二分左端点(第1个能插花的位置) 140 int R=dive(A,min(cnt,F));//二分右端点(最后一个能插花的位置) 141 Update(L,R,0,1);//将区间[L,R]的花瓶全部插满 142 printf("%d %d\n",L-1,R-1); 143 } 144 } 145 else if(op==2) 146 { 147 int A,B; 148 scanf("%d %d",&A,&B); 149 A++; 150 B++; 151 printf("%d\n",B-A+1-Query(A,B,1)); 152 Update(A,B,1,1);//将区间[A,B]的花瓶全部清空 153 } 154 } 155 printf("\n"); 156 } 157 return 0; 158 }
下面是kuangbin大佬用另一种模型的线段树写的，虽然有点麻烦，但是有空还是值得一看：https://www.cnblogs.com/kuangbin/p/3214805.html
HDU-4614 Vases and Flowers（线段树区间更新+二分查找）
原文：https://www.cnblogs.com/jiamian/p/11421671.html