?
题意：宾馆有n个房间。有人来入住。共有2种操作
输入1和d，表示查询
最左的连续d个空房间数的起始位置。 输入2，x和d，表示将从x开始长度为d的连续的房间清空。
思路：裸的区间合并。每个结点区间[l，r]存从左端点l开始向右最大连续空房间数lm，从右端点r开始向左最大连续空房间数rm和当前区间内最大连续空房间数。
代码：
#include
#include
#include
#include
#include
#include
using namespace std; #define lson l, m, rt << 1 #define rson m + 1, r, rt << 1 | 1 const int N = 5e5 + 10; const int INF = 0x7f7f7f7f; struct Node { int lm; int rm; int mx; Node() {} Node(int x, int y, int z) { lm = x; rm = y; mx = z; } }; Node node[N << 2]; int lazy[N << 2]; void pushup(int rt, int l, int r) { int m = (l + r) >> 1; node[rt].mx = max(node[rt << 1].rm + node[rt << 1 | 1].lm, max(node[rt << 1].mx, node[rt << 1 | 1].mx)); if (node[rt << 1].lm == m - l + 1) node[rt].lm = node[rt << 1].lm + node[rt << 1 | 1].lm; else node[rt].lm = node[rt << 1].lm; if (node[rt << 1 | 1].rm == r - m) node[rt].rm = node[rt << 1 | 1].rm + node[rt << 1].rm; else node[rt].rm = node[rt << 1 | 1].rm; } void pushdown(int rt, int l, int r) { if (lazy[rt] != -1) { lazy[rt << 1] = lazy[rt << 1 | 1] = lazy[rt]; int m = (l + r) >> 1; int lenl = m - l + 1; int lenr = r - m; if (lazy[rt] == 1) { node[rt << 1] = Node(lenl, lenl, lenl); node[rt << 1 | 1] = Node(lenr, lenr, lenr); } else { node[rt << 1] = Node(0, 0, 0); node[rt << 1 | 1] = Node(0, 0, 0); } lazy[rt] = -1; } } void build(int l, int r, int rt) { lazy[rt] = -1; node[rt].lm = node[rt].rm = node[rt].mx = r - l + 1; if (l == r) return ; int m = (l + r) >> 1; build(lson); build(rson); } void update(int t, int L, int R, int l, int r, int rt) { if (L <= l && r <= R) { if (t == 1) node[rt] = Node(r - l + 1, r - l + 1, r - l + 1); else node[rt] = Node(0, 0, 0); lazy[rt] = t; return ; } if (l == r) return ; pushdown(rt, l, r); int m = (l + r) >> 1; if (L <= m) update(t, L, R, lson); if (R > m) update(t, L, R, rson); pushup(rt, l, r); } int query(int t, int l, int r, int rt) { if (l == r) return l; int m = (l + r) >> 1; pushdown(rt, l, r); int p; if (node[rt << 1].mx >= t) p = query(t, lson); else if (node[rt << 1].rm + node[rt << 1 | 1].lm >= t) p = m - node[rt << 1].rm + 1; else p = query(t, rson); pushup(rt, l, r); return p; } int main() { int n, m; while (scanf(%d%d, &n, &m) != EOF) { build(1, n, 1); for (int i_q = 1; i_q <= m; i_q++) { int q; scanf(%d, &q); if (q == 1) { int d; scanf(%d, &d); if (node[1].mx < d) {//不需要更新。wa了n发 puts(0); continue; } int l = query(d, 1, n, 1); printf(%d , l); update(0, l, l + d - 1, 1, n, 1); } else { int x, d; scanf(%d%d, &x, &d); update(1, x, x + d - 1, 1, n, 1); } } } return 0; }
?