/* 题意：输入 1 a:询问是不是有连续长度为a的空房间,有的话住进最左边 输入 2 a b:将[a,a+b-1]的房间清空 线段树(区间合并)：lsum[]统计从左端点起最长连续空房间数，rsum[]类似，sum[]统计区间最长连续的空房间数， 它有三种情况：1.纯粹是左端点起的房间数；2.纯粹是右端点的房间数；3.当从左(右)房间起都连续时，加上另一个子节点 从左(右)房间起的数，sum[]再求最大值更新维护。理解没错，表达能力不足 详细解释：http://www.cnblogs.com/scau20110726/archive/2013/05/07/3065418.html*/#include#include #include using namespace std;#define lson l, mid, rt << 1#define rson mid + 1, r, rt << 1 | 1const int MAXN = 5e4 + 10;const int INF = 0x3f3f3f3f;struct Segment_Tree { int sum[MAXN<<2], lsum[MAXN<<2], rsum[MAXN<<2], cover[MAXN<<2]; void push_up(int rt, int len) { lsum[rt] = lsum[rt<<1]; rsum[rt] = rsum[rt<<1|1]; if (lsum[rt] == len - (len>>1)) lsum[rt] += lsum[rt<<1|1]; if (rsum[rt] == len>>1) rsum[rt] += rsum[rt<<1]; sum[rt] = max (rsum[rt<<1] + lsum[rt<<1|1], max (sum[rt<<1], sum[rt<<1|1])); } void push_down(int rt, int len) { if (cover[rt] != -1) { cover[rt<<1] = cover[rt<<1|1] = cover[rt]; sum[rt<<1] = lsum[rt<<1] = rsum[rt<<1] = cover[rt] ? 0 : len - (len>>1); sum[rt<<1|1] = lsum[rt<<1|1] = rsum[rt<<1|1] = cover[rt] ? 0 : len >> 1; cover[rt] = -1; } } void build(int l, int r, int rt) { sum[rt] = lsum[rt] = rsum[rt] = r - l + 1; cover[rt] = -1; if (l == r) return ; int mid = (l + r) >> 1; build (lson); build (rson); } void updata(int ql, int qr, int c, int l, int r, int rt) { if (ql <= l && r <= qr) { sum[rt] = lsum[rt] = rsum[rt] = c ? 0 : (r - l + 1); cover[rt] = c; return ; } push_down (rt, r - l + 1); int mid = (l + r) >> 1; if (ql <= mid) updata (ql, qr, c, lson); if (qr > mid) updata (ql, qr, c, rson); push_up (rt, r - l + 1); } int query(int w, int l, int r, int rt) { if (l == r) return l; push_down (rt, r - l + 1); int mid = (l + r) >> 1; if (sum[rt<<1] >= w) return query (w, lson); else if (rsum[rt<<1] + lsum[rt<<1|1] >= w) return mid - rsum[rt<<1] + 1; else return query (w, rson); }}st;int main(void) { //POJ 3667 Hotel int n, m; while (scanf ("%d%d", &n, &m) == 2) { st.build (1, n, 1); for (int i=1; i<=m; ++i) { int op, a, b; scanf ("%d%d", &op, &a); if (op == 1) { if (st.sum[1] < a) puts ("0"); else { int p = st.query (a, 1, n, 1); printf ("%d\n", p); st.updata (p, p + a - 1, 1, 1, n, 1); } } else { scanf ("%d", &b); st.updata (a, a + b - 1, 0, 1, n, 1); } } } return 0;}