线段树的区间合并,其中lsum代表区间左边最大连续长度,rsum代表区间最大连续长度,msum代表区间
最大连续长度。因为本题是查询连续区间的左端点,那么如果左儿子满足条件,就继续查询左儿子,左儿
子不满足条件,就判断左儿子的rsum + 右儿子的lsum是不是满足条件,最后才查询右儿子。
/*Accepted 2236K 594MS C++ 2574B 2012-08-21 12:15:23*/ #include<stdio.h> #include<string.h> #include<stdlib.h> #include<algorithm> using namespace std; #define lson l, mid, rt << 1 #define rson mid + 1, r, rt << 1 | 1const int MAXN = 50050; int msum[MAXN << 2], lsum[MAXN << 2], rsum[MAXN << 2]; int col[MAXN << 2];void PushDown(int l, int r, int rt) {int mid = l + r >> 1;if(col[rt] != -1){col[rt << 1] = col[rt << 1 | 1] = col[rt];msum[rt << 1] = lsum[rt << 1] = rsum[rt << 1] = col[rt] ? 0 : mid - l + 1;msum[rt << 1 | 1] = lsum[rt << 1 | 1] = rsum[rt << 1 | 1]= col[rt] ? 0 : r - mid;col[rt] = -1;} }void PushUp(int l, int r, int rt) {int mid = l + r >> 1;lsum[rt] = lsum[rt << 1];rsum[rt] = rsum[rt << 1 | 1];if(lsum[rt] == mid - l + 1) lsum[rt] += lsum[rt << 1 | 1];if(rsum[rt] == r - mid) rsum[rt] += rsum[rt << 1];msum[rt] = max(lsum[rt << 1 | 1] + rsum[rt << 1],max(msum[rt << 1], msum[rt << 1 | 1])); }void build(int l, int r, int rt) {int mid = l + r >> 1;msum[rt] = lsum[rt] = rsum[rt] = r - l + 1;col[rt] = -1;if(l == r) return;build(lson);build(rson); }void update(int L, int R, int c, int l, int r, int rt) {int mid = l + r >> 1;if(L <= l && r <= R){msum[rt] = lsum[rt] = rsum[rt] = c ? 0 : r - l + 1;col[rt] = c;return;}PushDown(l, r, rt);if(L <= mid) update(L, R, c, lson);if(R > mid) update(L, R, c, rson);PushUp(l, r, rt); }int query(int w, int l, int r, int rt) {int mid = l + r >> 1;if(l == r) return l;PushDown(l, r, rt);if(msum[rt << 1] >= w) return query(w, lson);else if(lsum[rt << 1 | 1] + rsum[rt << 1] >= w)return mid - rsum[rt << 1] + 1;return query(w, rson); }int main() {int n, m;while(scanf("%d%d", &n, &m) == 2){build(1, n, 1);while(m --){int op, a, b;scanf("%d", &op);if(1 == op){scanf("%d", &a);if(a > msum[1]) puts("0");else{int p = query(a, 1, n, 1);printf("%d\n", p);update(p, p + a - 1, 1, 1, n, 1);}}else{scanf("%d%d", &a, &b);update(a, a + b - 1, 0, 1, n, 1);}}}return 0; }