Vases and Flowers

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]

题解：用线段树维护每个区间最左端能放花的位置，最右端能放花的位置，以及整个区间能放花的位置的个数。k=1时，二分枚举最后一束花放的位置，然后再更新这段

区间。k=2时，先查询这段区间能放花的位置的个数，答案就是这段区间的长度减去查询得到的值，然后再更新整段区间。这里将两种标记当做一种来操作，向下传递的

时候分类讨论。好题。

  1 #pragma warning(disable:4996)
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<iostream>
  5 #include<algorithm>
  6 using namespace std;
  7 
  8 const int maxn = 200100;
  9 const int INF = 1e9 + 7;
 10 
 11 struct node {
 12     int l, r;
 13     int ls, rs, sum, add;
 14 }Tree[maxn];
 15 
 16 int n, m;
 17 int ansl, ansr;
 18 
 19 #define lson root<<1
 20 #define rson root<<1|1
 21 
 22 void Pushdown(int root) {
 23     Tree[lson].add = Tree[root].add;
 24     Tree[rson].add = Tree[root].add;
 25     if (Tree[root].add == 1) {
 26 
 27         Tree[lson].ls = Tree[lson].l;
 28         Tree[lson].rs = Tree[lson].r;
 29 
 30         Tree[rson].ls = Tree[rson].l;
 31         Tree[rson].rs = Tree[rson].r;
 32 
 33         Tree[lson].sum = (Tree[lson].r - Tree[lson].l + 1);
 34         Tree[rson].sum = (Tree[rson].r - Tree[rson].l + 1);
 35     }
 36     else {
 37 
 38         Tree[lson].ls = -1;
 39         Tree[lson].rs = -1;
 40 
 41         Tree[rson].ls = -1;
 42         Tree[rson].rs = -1;
 43 
 44         Tree[lson].sum = 0;
 45         Tree[rson].sum = 0;
 46     }
 47     Tree[root].add = 0;
 48 }
 49 
 50 void Pushup(int root) {
 51     if (Tree[lson].ls == -1) Tree[root].ls = Tree[rson].ls;
 52     else Tree[root].ls = Tree[lson].ls;
 53     if (Tree[rson].rs == -1) Tree[root].rs = Tree[lson].rs;
 54     else Tree[root].rs = Tree[rson].rs;
 55     Tree[root].sum = Tree[lson].sum + Tree[rson].sum;
 56 }
 57 
 58 void Build(int l, int r, int root) {
 59     Tree[root].l = l;
 60     Tree[root].r = r;
 61     Tree[root].add = 0;
 62     if (l == r) {
 63         Tree[root].ls = Tree[root].rs = l;
 64         Tree[root].sum = 1;
 65         return;
 66     }
 67     int mid = (l + r) >> 1;
 68     Build(l, mid, lson);
 69     Build(mid + 1, r, rson);
 70     Pushup(root);
 71 }
 72 void UPdate(int L, int R, int l, int r, int root, int c) {
 73     if (l>R || r<L) return;
 74     if (L <= l && r <= R) {
 75         if (c == 1) {
 76             Tree[root].sum = (r - l + 1);
 77             Tree[root].add = c;
 78 
 79             Tree[root].ls = l;
 80             Tree[root].rs = r;
 81         }
 82         else {
 83             Tree[root].sum = 0;
 84             Tree[root].add = c;
 85 
 86             Tree[root].ls = -1;
 87             Tree[root].rs = -1;
 88         }
 89         return;
 90     }
 91     if (Tree[root].add) Pushdown(root);
 92     int mid = (l + r) >> 1;
 93     UPdate(L, R, l, mid, lson, c);
 94     UPdate(L, R, mid + 1, r, rson, c);
 95     Pushup(root);
 96 }
 97 
 98 int Query(int L, int R, int l, int r, int root) {
 99     if (l > R || r < L) return 0;
100     if (L <= l && r <= R) {
101         if (Tree[root].ls != -1) ansl = min(ansl, Tree[root].ls);
102         if (Tree[root].rs != -1) ansr = max(ansr, Tree[root].rs);
103         return Tree[root].sum;
104     }
105     if (Tree[root].add) Pushdown(root);
106     int mid = (l + r) >> 1;
107     int ans = 0;
108     ans += Query(L, R, l, mid, lson);
109     ans += Query(L, R, mid + 1, r, rson);
110     return ans;
111 }
112 
113 // c=0 代表查右端点
114 // c=1 代表查左端点
115 
116 void Binary_pos(int bottom, int top, int num) {
117 
118     int l = bottom, r = top;
119     int cnt = 0;
120     
121     for (int i = 1; i <= 20; i++) {
122         ansl = INF;
123         ansr = 0;
124         int mid = (l + r) >> 1;
125         cnt = Query(bottom, mid, 1, n, 1);
126         if (cnt >= num) r = mid;
127         else l = mid + 1;
128     }
129 }
130 
131 int main() {
132     int kase;
133     scanf("%d", &kase);
134     while (kase--) {
135         scanf("%d%d", &n, &m);
136         Build(1, n, 1);
137         for (int i = 1; i <= m; i++) {
138             int k, x, y;
139             scanf("%d%d%d", &k, &x, &y);
140             if (k == 1) {
141                 x++;
142                 int empty = Query(x, n, 1, n, 1);
143                 if (empty == 0) printf("Can not put any one.
");
144                 else {
145                     y = min(y, empty);
146                     Binary_pos(x, n, y);
147 
148                     ansl--;
149                     ansr--;
150                     
151                     printf("%d %d
", ansl, ansr);
152                     UPdate(ansl + 1, ansr + 1, 1, n, 1, 2);
153                 }
154             }
155             else {
156                 x++;
157                 y++;
158                 printf("%d
", (y - x + 1 - Query(x, y, 1, n, 1)));
159                 UPdate(x, y, 1, n, 1, 1);
160             }
161         }
162         printf("
");
163     }
164     return 0;
165 }