PKU 3667 Hotel

 维护左、右、总的连续区间长度，在 update 求总的最大长度时，写成了

tsum[r] = Max(rsum[ls]+lsum[rs], Max(lsum[r], rsum[r])); 所以一直出错。

/*
notepad++ 调用 g++ 编译
cmd /k C:\ACMSOFT\DEVC\Bin\g++.exe -g -W -Wall -o $(CURRENT_DIRECTION)\$(NAME_PART).exe $(FULL_CURRENT_PATH)
*/

# include <stdio.h>

# define ls ((r)<<1)
# define rs ((r)<<1|1)
# define mid (((x)+(y))>>1)

# define N 50005

int n, m;
char cover[N<<2];
int lsum[N<<2], rsum[N<<2], tsum[N<<2];

int Max(int x, int y)
{
    return x > y ? x : y;
}

void build(int r, int x, int y)
{
    cover[r] = -1;
    lsum[r] = rsum[r] = tsum[r] = y-x+1;
    if (x == y) return;
    build(ls, x, mid);
    build(rs, mid+1, y);
}

void update(int r, int x, int y)
{
    lsum[r] = lsum[ls], rsum[r] = rsum[rs];
    if (lsum[ls] == (mid-x+1)) lsum[r] += lsum[rs];
    if (rsum[rs] == (y-mid)) rsum[r] += rsum[ls];
    tsum[r] = Max(rsum[ls]+lsum[rs], Max(tsum[ls], tsum[rs]));
}

void pushdown(int r, int x, int y)
{
    if (cover[r] != -1)
    {
        cover[ls] = cover[rs] = cover[r];
        tsum[ls] = lsum[ls] = rsum[ls] = (cover[r] ? 0:(mid-x+1));
        tsum[rs] = lsum[rs] = rsum[rs] = (cover[r] ? 0:(y-mid));
        cover[r] = -1;
    }
}

void change(int r, int x, int y, int s, int t, int val)
{
    if (s<=x && y<=t)
    {
        cover[r] = val;
        lsum[r] = rsum[r] = tsum[r] = (val ? 0:y-x+1);
        return ;
    }
    pushdown(r, x, y);
    if  (s <= mid) change(ls, x, mid, s, t, val);
    if (mid+1<=t) change(rs, mid+1, y, s, t, val);
    update(r, x, y);
}

int query(int r, int x, int y, int w)
{
    if (x == y) return x;
    pushdown(r, x, y);
    if (tsum[ls] >= w) return query(ls, x, mid, w);
    else if (rsum[ls]+lsum[rs] >= w) return mid-rsum[ls]+1;
    else if (tsum[rs] >= w) return query(rs, mid+1, y, w);
}

void solve(void)
{
    int i, op, s,  w;
    scanf("%d%d", &n, &m);
    build(1, 1, n);
    for (i = 0; i < m; ++i)
    {
        scanf("%d", &op);
        if (op == 1)
        {
            scanf("%d", &w);
            if (tsum[1] < w) printf("0\n");
            else
            {
                s = query(1, 1, n, w);
                printf("%d\n", s);
                change(1, 1, n, s, s+w-1, 1);
            }
        }
        else
        {
            scanf("%d%d", &s, &w);
            change(1, 1, n, s, s+w-1, 0);
        }
    }
}

int main()
{
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);

        solve();

    return 0;
}

 563ms。