HDU 4614 Vases and Flowers 线段树+二分

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4614

题意：N个花瓶，两种操作。

操作1：从第a个花瓶开始放花，放最多f个，如果花瓶已经有花就跳过，直到放完，或者无更多花瓶，要求输出这次放花的第一个位置和最后一个位置，如果没放就输出Cannot。。。

操作2：将花瓶a到b区间内的花都扔了，然后输出扔掉的花的数目。

解题思路：花瓶有花为0，无花为1，那么实际上这是一个区间更新以及求和，求左右端点的问题。线段树节点维护一个 sum--区间和，lid--最左端为1的点，rid--最右端为1的点。对于操作1，首先找到放的区间。即如果能放这么多花，最后一个可以放的位置在哪。当然如果不能放花则直接输出cannot。。。如果能放的比要放的少就是从a到n，否则二分查找以a为起点的空花瓶个数为要放的花的数目f的位置，查询，更新就行。

理清思路的话，不算难，就是过程略复杂。

顺便说下这几天做线段树对延迟标记的理解：延迟标记的作用不用多说，要注意的是更新到一个区间时，如果包含了整个区间的话，就加上延迟标记，同时要更新整个区间的值。如果需要往左右孩子更新的话，那么就将延迟标记传递给左右孩子，同时更新他们节点的值。所以，对于延迟标记来讲，一个要求就是能直接计算出它所带来的属性值的变化。

代码：

  1 const int maxn = 5e4 + 5;
  2 struct node{
  3     int sum, lazy;
  4     int lid, rid;
  5 };
  6 node tree[maxn * 4];
  7 int n, m;
  8 
  9 
 10 void build(int l, int r, int k){
 11     tree[k].sum = (r - l + 1);tree[k].lazy = 0;
 12     tree[k].lid = l; tree[k].rid = r;
 13     if(l == r) return;
 14     int mid = (l + r) >> 1, lc = k << 1, rc = k << 1 | 1;
 15     build(l, mid, lc);
 16     build(mid + 1, r, rc);
 17 }
 18 void pushdown(int l, int r, int k){
 19     if(tree[k].lazy == 0) return;
 20     int mid = (l + r) >> 1, lc = k << 1, rc = k << 1 | 1;
 21     if(tree[k].lazy == 1){
 22         tree[lc].lazy = 1; tree[rc].lazy = 1;
 23         tree[lc].sum = (mid - l + 1); tree[lc].lid = l; tree[lc].rid = mid;
 24         tree[rc].sum = (r - mid); tree[rc].lid = mid + 1; tree[rc].rid = r;
 25     }
 26     else if(tree[k].lazy == -1){
 27         tree[lc].lazy = -1; tree[rc].lazy = -1;
 28         tree[lc].sum = 0; tree[lc].lid = 0; tree[lc].rid = 0;
 29         tree[rc].sum = 0; tree[rc].lid = 0; tree[rc].rid = 0;
 30     }
 31     tree[k].lazy = 0;
 32 }
 33 void pushup(int l, int r, int k){
 34     int mid = (l + r) >> 1, lc = k << 1, rc = k << 1 | 1;
 35     tree[k].sum = tree[lc].sum + tree[rc].sum;
 36     if(tree[lc].lid != 0) tree[k].lid = tree[lc].lid;
 37     else if(tree[rc].lid != 0) tree[k].lid = tree[rc].lid;
 38     else tree[k].lid = 0;
 39     if(tree[rc].rid != 0) tree[k].rid = tree[rc].rid;
 40     else if(tree[lc].rid != 0) tree[k].rid = tree[lc].rid;
 41     else tree[k].rid = 0;
 42 }
 43 void update(int ul, int ur, int x, int l, int r, int k){
 44     if(ul <= l && ur >= r){
 45         tree[k].lazy = x;
 46         if(x == 1){
 47             tree[k].sum = (r - l + 1);
 48             tree[k].lid = l; tree[k].rid = r;
 49         }
 50         else if(x == -1){
 51             tree[k].sum = 0;
 52             tree[k].lid = tree[k].rid = 0;
 53         }
 54         return;
 55     }
 56     if(ul > r || ur < l) return;
 57     int mid = (l + r) >> 1, lc = k << 1, rc = k << 1 | 1;
 58     pushdown(l, r, k);
 59     update(ul, ur, x, l, mid, lc);
 60     update(ul, ur, x, mid + 1, r, rc);
 61     pushup(l, r, k);
 62 }
 63 int query_left(int ql, int qr, int l, int r, int k){
 64     if(ql <= l && qr >= r){
 65         return tree[k].lid;
 66     }
 67     if(ql > r || qr < l) return 0;
 68     pushdown(l, r, k);
 69     int mid = (l + r) >> 1, lc = k << 1, rc = k << 1 | 1;
 70     int q1 = query_left(ql, qr, l, mid, lc);
 71     int q2 = query_left(ql, qr, mid + 1, r, rc);
 72     if(q1 == 0) return q2;
 73     return q1;
 74 }
 75 int query_right(int ql, int qr, int l, int r, int k){
 76     if(ql <= l && qr >= r){
 77         return tree[k].rid;
 78     }
 79     if(ql > r || qr < l) return 0;
 80     pushdown(l, r, k);
 81     int mid = (l + r) >> 1, lc = k << 1, rc = k << 1 | 1;
 82     int q1 = query_right(ql, qr, l, mid, lc);
 83     int q2 = query_right(ql, qr, mid + 1, r, rc);
 84     if(q2 == 0) return q1;
 85     return q2;
 86 }
 87 int sum(int sl, int sr, int l, int r, int k){
 88     if(sl <= l && sr >= r){
 89         return tree[k].sum;
 90     }
 91     if(sl > r || sr < l) return 0;
 92     pushdown(l, r, k);
 93     int mid = (l + r) >> 1, lc = k << 1, rc = k << 1 | 1;
 94     return sum(sl, sr, l, mid, lc) + sum(sl, sr, mid + 1, r, rc);
 95 }
 96 int check(int u, int f){
 97     int tmp = sum(u, n, 1, n, 1);
 98     if(tmp == 0) return -1;
 99     else if(tmp <= f) return n;
100     int l = u, r = n;
101     while(l < r){
102         int mid = (l + r) >> 1;
103         tmp = sum(u, mid, 1, n, 1);
104         if(tmp >= f) r = mid;
105         else l = mid + 1;
106     }
107     return l;
108 }
109 
110 int main(){
111     int T;
112     scanf("%d", &T);
113     while(T--){
114         memset(tree, 0, sizeof(tree));
115         scanf("%d %d", &n, &m);
116         build(1, n, 1);
117         while(m--){
118             int k, a, b;
119             scanf("%d %d %d", &k, &a, &b);
120             if(k == 1){
121                 a++;
122                 int tmp = check(a, b);
123                 if(tmp == -1) {
124                     puts("Can not put any one.");
125                     continue;
126                 }
127                 int u = query_left(a, tmp, 1, n, 1);
128                 int v = query_right(a, tmp, 1, n, 1);
129                 printf("%d %d
", u - 1, v - 1);
130                 update(a, tmp, -1, 1, n, 1);
131             }
132             else{
133                 a++;b++;
134                 int u = b - a + 1 - sum(a, b, 1, n, 1);
135                 printf("%d
", u);
136                 update(a, b, 1, 1, n, 1);
137             }
138         }
139         puts("");
140     }
141 }

题目：

Vases and Flowers

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 3574 Accepted Submission(s): 1460

Problem Description

　　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.

Input

　　The first line contains an integer T, indicating the number of test cases.
　　For each test case, the first line contains two integers N(1 < N < 50001) and M(1 < M < 50001). N is the number of vases, and M is the operations of Alice. Each of the next M lines contains three integers. The first integer of one line is K(1 or 2). If K is 1, then two integers A and F follow. It means Alice receive F flowers and try to put a flower in the vase A first. If K is 2, then two integers A and B follow. It means the owner would like to clean the vases numbered from A to B(A <= B).

Output

　　For each operation of which K is 1, output the position of the vase in which Alice put the first flower and last one, separated by a blank. If she can not put any one, then output 'Can not put any one.'. For each operation of which K is 2, output the number of discarded flowers.
　　Output one blank line after each test case.

Sample Input

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

Sample Output

[pre]3 7 2 1 9 4 Can not put any one. 2 6 2 0 9 4 4 5 2 3 [/pre]

Author

SYSU

Source

2013 Multi-University Training Contest 2