CF_46D
由于数据范围很小，实际上可以直接暴力的。但为了练练线段树合并区间的操作所以就用线段树写了。
更多和线段树合并区间有关的题目可以参考胡浩的博客：http://www.notonlysuccess.com/index.php/segment-tree-complete/。
#include<stdio.h> #include<string.h> #define MAXD 100210 #define MAXQ 110 int N, L, B, F, lc[4 * MAXD], mc[4 * MAXD], rc[4 * MAXD], to[4 * MAXD]; struct Car { int x, y; }car[MAXQ]; void build(int cur, int x, int y) { int mid = (x + y) >> 1, ls = cur << 1, rs = (cur << 1) | 1; mc[cur] = lc[cur] = rc[cur] = y - x + 1; to[cur] = -1; if(x == y) return ; build(ls, x, mid); build(rs, mid + 1, y); } int getmax(int x, int y) { return x > y ? x : y; } void update(int cur, int x, int y) { int mid = (x + y) >> 1, ls = cur << 1, rs = (cur << 1) | 1; mc[cur] = getmax(mc[ls], mc[rs]); mc[cur] = getmax(rc[ls] + lc[rs], mc[cur]); lc[cur] = lc[ls] + (lc[ls] == mid - x + 1 ? lc[rs] : 0); rc[cur] = rc[rs] + (rc[rs] == y - mid ? rc[ls] : 0); } void pushdown(int cur, int x, int y) { int mid = (x + y) >> 1, ls = cur << 1, rs = (cur << 1) | 1; if(to[cur] != -1) { to[ls] = to[rs] = to[cur]; mc[ls] = lc[ls] = rc[ls] = (to[cur] ? 0 : mid - x + 1); mc[rs] = lc[rs] = rc[rs] = (to[cur] ? 0 : y - mid); to[cur] = -1; } } int query(int cur, int x, int y, int z) { int mid = (x + y) >> 1, ls = cur << 1, rs = (cur << 1) | 1; if(x == y) return x; pushdown(cur, x, y); if(mc[rs] >= z) return query(rs, mid + 1, y, z); else if(rc[ls] + lc[rs] >= z) return mid + lc[rs]; else return query(ls, x, mid, z); } void refresh(int cur, int x, int y, int s, int t, int c) { int mid = (x + y) >> 1, ls = cur << 1, rs = (cur << 1) | 1; if(x >= s && y <= t) { to[cur] = c; mc[cur] = lc[cur] = rc[cur] = (c ? 0 : y - x + 1); return ; } pushdown(cur, x, y); if(mid >= s) refresh(ls, x, mid, s, t, c); if(mid + 1 <= t) refresh(rs, mid + 1, y, s, t, c); update(cur, x, y); } void solve() { int i, j, k, x, y, n, len; scanf("%d", &n); for(i = 1; i <= n; i ++) { scanf("%d", &j); if(j == 1) { scanf("%d", &len); if(mc[1] < len + B + F) printf("-1\n"); else { y = query(1, 1, N, len + B + F); printf("%d\n", N - y); car[i].x = y - B - len + 1, car[i].y = y - B; refresh(1, 1, N, car[i].x, car[i].y, 1); } } else { scanf("%d", &k); refresh(1, 1, N, car[k].x, car[k].y, 0); } } } void init() { N = L + B + F; build(1, 1, N); } int main() { while(scanf("%d%d%d", &L, &B, &F) == 3) { init(); solve(); } return 0; }