POJ 3667 Hotel

解法

SegTree。区間は以下の3つの情報を持つ必要がある。

• 区間内で最大の連続した空きスペース
• 区間の左端から連続した空きスペース
• 区間の右端から連続した空きスペース

（実装では、その区間は完全に空きであるか(empty)を持っているが補助的なもの。）

この問題では、区間に対する操作が必要なので、遅延評価をする必要がある。
遅延評価についてわからない人はkyuridenamida先生による解説を読もう
http://d.hatena.ne.jp/kyuridenamida/20121114/1352835261

ソースコード

class HotelSegTree
{
private:
    struct Seg
    {
	bool empty;
	int max_space;
	int left_space;
	int right_space;
	int lazy;
	Seg()
	    : empty(false), max_space(0),
	      left_space(0), right_space(0),
	      lazy(-1)
	{
	}
    };

    vector<Seg> seg;
    int SIZE;

    static const int IN = 1, OUT = 0;
    void update(int a, int b, int ope, int k, int l, int r)
    {
	const int space = r - l;
	const int mid = (l + r) / 2;
	const int lk = 2 * k + 1, rk = 2 * k + 2;

	if (seg[k].lazy != -1)
	{
	    int lazy_ope = seg[k].lazy;
	    seg[k].lazy = -1;
	    update(l, r, lazy_ope, k, l, r);
	}

	if (b <= l || r <= a || space == 0)
	    return;

	if (a <= l && r <= b)
	{
	    seg[k].max_space = seg[k].left_space = seg[k].right_space
		= ope == OUT ? space : 0;
	    seg[k].empty = ope == OUT;

	    if (k < SIZE)
		seg[lk].lazy = seg[rk].lazy = ope;
	}
	else
	{
	    update(a, b, ope, lk, l, mid);
	    update(a, b, ope, rk, mid, r);

	    const int cat_space = seg[lk].right_space + seg[rk].left_space;
	    seg[k].max_space = max(cat_space, max(seg[lk].max_space, seg[rk].max_space));
	    seg[k].empty = seg[k].max_space == space;

	    seg[k].left_space = seg[lk].left_space;
	    if (seg[lk].empty)
		seg[k].left_space += seg[rk].left_space;

	    seg[k].right_space = seg[rk].right_space;
	    if (seg[rk].empty)
		seg[k].right_space += seg[lk].right_space;
	}
    }

    int find(int need_space, int k, int l, int r)
    {
	if (seg[k].left_space >= need_space)
	    return l;

	int mid = (l + r) / 2;
	int lk = 2 * k + 1, rk = 2 * k + 2;
	if (seg[lk].max_space >= need_space)
	    return find(need_space, lk, l, mid);
	else if (seg[lk].right_space + seg[rk].left_space >= need_space)
	    return mid - seg[lk].right_space;
	else
	    return find(need_space, rk, mid, r);
    }

public:
    HotelSegTree(int n)
    {
	SIZE = 1;
	while (SIZE < n)
	    SIZE *= 2;
	seg.resize(2 * SIZE);
    }

    void out(int l, int r)
    {
	update(l, r, OUT, 0, 0, SIZE);
    }

    void in(int l, int r)
    {
	update(l, r, IN, 0, 0, SIZE);
    }

    int find(int need_space)
    {
	if (seg[0].max_space < need_space)
	    return -1;
	else
	    return find(need_space, 0, 0, SIZE);
    }
};
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);

    HotelSegTree segtree(n);
    segtree.out(0, n);
    while (m--)
    {
	int q;
	scanf("%d", &q);
	if (q == 1)
	{
	    int d;
	    scanf("%d", &d);

	    int k = segtree.find(d);
	    if (k == -1)
		puts("0");
	    else
	    {
		printf("%d\n", k + 1);
		segtree.in(k, k + d);
	    }
	}
	else
	{
	    int x, d;
	    scanf("%d%d", &x, &d);
	    --x;

	    segtree.out(x, x + d);
	}
    }
}