裸上线段树，就是记的东西有点多。。。
每个点记区间左端最长0，右端最长0，中间最长0，和tag表示是否全为0/1
直接更新就好，查询的时候先查左儿子，然后查中间，最后查右儿子。。。
1 /************************************************************** 2 Problem: 1593 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:388 ms 7 Memory:4404 kb 8 ****************************************************************/ 9 10 #include <cstdio> 11 #include <algorithm> 12 13 using namespace std; 14 15 inline int read(); 16 17 struct seg { 18 seg *ls, *rs; 19 int mxl, mxm, mxr, len, tag; 20 21 #define Len (1 << 16) 22 void* operator new(size_t, int x) { 23 static seg *mempool, *c; 24 if (c == mempool) 25 mempool = (c = new seg[Len]) + Len; 26 c -> ls = c -> rs = NULL; 27 c -> mxl = c -> mxr = c -> mxm = c -> len = x, c -> tag = -1; 28 return c++; 29 } 30 #undef Len 31 32 #define mid (l + r >> 1) 33 #define Ls this -> ls 34 #define Rs this -> rs 35 inline void fill(int d) { 36 if (d) this -> mxl = this -> mxr = this -> mxm = 0; 37 else this -> mxl = this -> mxr = this -> mxm = this -> len; 38 this -> tag = d; 39 } 40 41 inline void push() { 42 if (~this -> tag) { 43 if (Ls) Ls -> fill(this -> tag); 44 if (Rs) Rs -> fill(this -> tag); 45 this -> tag = -1; 46 } 47 } 48 inline void update() { 49 this -> mxl = Ls -> mxl + (Ls -> mxl == Ls -> len ? Rs -> mxl : 0); 50 this -> mxr = Rs -> mxr + (Rs -> mxr == Rs -> len ? Ls -> mxr : 0); 51 this -> mxm = max(max(Ls -> mxm, Rs -> mxm), Ls -> mxr + Rs -> mxl); 52 } 53 54 void build(int l, int r) { 55 if (l == r) return; 56 Ls = new(mid - l + 1)seg, Ls -> build(l, mid); 57 Rs = new(r - mid)seg, Rs -> build(mid + 1, r); 58 } 59 60 void modify(int l, int r, int L, int R, int d) { 61 if (L <= l && r <= R) { 62 this -> fill(d); 63 return; 64 } 65 this -> push(); 66 if (L <= mid) Ls -> modify(l, mid, L, R, d); 67 if (mid < R) Rs -> modify(mid + 1, r, L, R, d); 68 this -> update(); 69 } 70 71 int query(int l, int r, int len) { 72 this -> push(); 73 if (this -> mxm < len) return 0; 74 if (Ls -> mxm >= len) return Ls -> query(l, mid, len); 75 if (Ls -> mxr + Rs -> mxl >= len) return mid - Ls -> mxr + 1; 76 if (Rs -> mxm >= len) return Rs -> query(mid + 1, r, len); 77 } 78 #undef mid 79 #undef Ls 80 #undef Rs 81 } *segment; 82 83 int n, m; 84 85 int main() { 86 int i, oper, x, y; 87 n = read(), m = read(); 88 segment = new(n)seg; 89 segment -> build(1, n); 90 for (i = 1; i <= m; ++i) { 91 oper = read(); 92 if (oper == 1) { 93 x = segment -> query(1, n, y = read()); 94 printf("%d ", x); 95 if (x) segment -> modify(1, n, x, x + y - 1, 1); 96 } else { 97 x = read(), y = read(); 98 segment -> modify(1, n, x, x + y - 1, 0); 99 } 100 } 101 return 0; 102 } 103 104 inline int read() { 105 static int x; 106 static char ch; 107 x = 0, ch = getchar(); 108 while (ch < '0' || '9' < ch) 109 ch = getchar(); 110 while ('0' <= ch && ch <= '9') { 111 x = x * 10 + ch - '0'; 112 ch = getchar(); 113 } 114 return x; 115 }