插花花

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <algorithm>
  4 using namespace std;
  5 
  6 inline int id(int u, int v) { return (u + v) | (u < v); }
  7 inline int md(int u, int v) { return (u + v) >> 1; }
  8 
  9 const int N = 50010;
 10 int h[N << 1];
 11 int g[N << 1];
 12 
 13 void down(int u, int v) {
 14   int d = md(u, v);
 15   int t = id(u, v);
 16   int l = id(u, d);
 17   int r = id(d + 1, v);
 18 
 19   if (!g[t]) {
 20     g[t] = 1;
 21     if (h[t] == 0) {
 22       h[l] = h[r] = 0;
 23     } else if (h[t] == v - u + 1) {
 24       h[l] = d - u + 1;
 25       h[r] = v - (d + 1) + 1;
 26     }
 27     g[l] = g[r] = 0;
 28   }
 29 }
 30 
 31 void set(int u, int v, int a, int b) {
 32   int d = md(u, v);
 33   int t = id(u, v);
 34   int l = id(u, d);
 35   int r = id(d + 1, v);
 36 
 37   if (u == a && v == b) {
 38     h[t] = v - u + 1;
 39     g[t] = 0;
 40     return;
 41   }
 42 
 43   down(u, v);
 44 
 45   if (b <= d)
 46     set(u, d, a, b);
 47   else if (d + 1 <= a)
 48     set(d + 1, v, a, b);
 49   else {
 50     set(u, d, a, d);
 51     set(d + 1, v, d + 1, b);
 52   }
 53 
 54   h[t] = h[l] + h[r];
 55 }
 56 
 57 void clear(int u, int v, int a, int b) {
 58   int d = md(u, v);
 59   int t = id(u, v);
 60   int l = id(u, d);
 61   int r = id(d + 1, v);
 62 
 63   if (u == a && v == b) {
 64     h[t] = 0;
 65     g[t] = 0;
 66     return;
 67   }
 68 
 69   down(u, v);
 70 
 71   if (b <= d)
 72     clear(u, d, a, b);
 73   else if (d + 1 <= a)
 74     clear(d + 1, v, a, b);
 75   else {
 76     clear(u, d, a, d);
 77     clear(d + 1, v, d + 1, b);
 78   }
 79 
 80   h[t] = h[l] + h[r];
 81 }
 82 
 83 int find(int u, int v, int a, int b) {
 84   int d = md(u, v);
 85   int t = id(u, v);
 86   int l = id(u, d);
 87   int r = id(d + 1, v);
 88 
 89   if (!g[t]) {
 90     if (h[t] == v - u + 1)
 91       return b - a + 1;
 92     else if (h[t] == 0)
 93       return 0;
 94   }
 95 
 96   if (u == a && v == b) {
 97     return h[t];
 98   }
 99 
100   if (b <= d)
101     return find(u, d, a, b);
102   else if (d + 1 <= a)
103     return find(d + 1, v, a, b);
104   else
105     return find(u, d, a, d) + find(d + 1, v, d + 1, b);
106 }
107 
108 int n, q;
109 
110 int main() {
111 //  freopen("in.txt", "r", stdin);
112 //  freopen("out.txt", "w", stdout);
113   int T; scanf("%d", &T);
114   while (T--) {
115     scanf("%d %d", &n, &q);
116     memset(h, 0, sizeof(h));
117     memset(g, 0, sizeof(g));
118     while (q--) {
119       int c, u, v, f;
120       int l, r, d, first, second;
121       scanf("%d %d %d", &c, &u, &v);
122       f = v;
123       switch (c) {
124         case 1:
125           l = u - 1, r = n;
126           while (l + 1 < r) {
127             d = (l + r) >> 1;
128             if (find(0, n - 1, u, d) < d - u + 1)
129               r = d;
130             else
131               l = d;
132           }
133           first = r;
134 
135           if (first >= n || !f) {
136             puts("Can not put any one.");
137           } else {
138             u = first;
139             l = u, r = n;
140             while (l + 1 < r) {
141               d = (l + r) >> 1;
142               if (d - u + 1 - find(0, n - 1, u, d) <= f)
143                 l = d;
144               else
145                 r = d;
146             }
147             v = l;
148 
149             l = u, r = v + 1;
150             while (l + 1 < r) {
151               d = (l + r) >> 1;
152               if (find(0, n - 1, d, v) < v - d + 1)
153                 l = d;
154               else
155                 r = d;
156             }
157             second = l;
158 
159             printf("%d %d
", first, second);
160             set(0, n - 1, first, second);
161           }
162           break;
163         case 2:
164           printf("%d
", find(0, n - 1, u, v));
165           clear(0, n - 1, u, v);
166           break;
167       }
168     }
169   }
170   return 0;
171 }
View Code