Hotel

Time Limit: 3000MS		Memory Limit: 65536K
Total Submissions: 22646		Accepted: 9911

Description

The cows are journeying north to Thunder Bay in Canada to gain cultural enrichment and enjoy a vacation on the sunny shores of Lake Superior. Bessie, ever the competent travel agent, has named the Bullmoose Hotel on famed Cumberland Street as their vacation residence. This immense hotel has N (1 ≤ N ≤ 50,000) rooms all located on the same side of an extremely long hallway (all the better to see the lake, of course).

The cows and other visitors arrive in groups of size Di (1 ≤ Di ≤ N) and approach the front desk to check in. Each group i requests a set of Di contiguous rooms from Canmuu, the moose staffing the counter. He assigns them some set of consecutive room numbers r..r+Di-1 if they are available or, if no contiguous set of rooms is available, politely suggests alternate lodging. Canmuu always chooses the value of r to be the smallest possible.

Visitors also depart the hotel from groups of contiguous rooms. Checkout i has the parameters Xi and Di which specify the vacating of rooms Xi ..Xi +Di-1 (1 ≤ Xi ≤ N-Di+1). Some (or all) of those rooms might be empty before the checkout.

Your job is to assist Canmuu by processing M (1 ≤ M < 50,000) checkin/checkout requests. The hotel is initially unoccupied.

Input

* Line 1: Two space-separated integers: N and M
* Lines 2..M+1: Line i+1 contains request expressed as one of two possible formats: (a) Two space separated integers representing a check-in request: 1 and Di (b) Three space-separated integers representing a check-out: 2, Xi, and Di

Output

* Lines 1.....: For each check-in request, output a single line with a single integer r, the first room in the contiguous sequence of rooms to be occupied. If the request cannot be satisfied, output 0.

Sample Input

10 6
1 3
1 3
1 3
1 3
2 5 5
1 6

Sample Output

1
4
7
0
5

题目大意 ： 一家旅馆有N个房间， M次询问， 操作1需要找到一个包含U那么长的连续区间，该区间内的房间都没人住， 如果前面没有，则往后找，如果可以找到，输出他最左边的下标， 否则输出0，操作2表示U 到 U + V区间的顾客都走了

思路 ： 线段树的区间合并操作， 主要维护三个值： 第一个是该区间内连续前缀、 连续后缀， 最大区间长度。每次查找时优先查找连续前缀， 如果前缀满足则输出该区间的左边界， 如果不满足则查找左区间的后缀 + 右区间的前缀， 满足则输出左区间的右边界 - 左边界后缀的长度 + 1， 否则查找右区间前缀，以此类推。

Accepted code

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;

#define sc scanf
#define ls rt << 1
#define rs ls | 1
#define Min(x, y) x = min(x, y)
#define Max(x, y) x = max(x, y)
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define MEM(x, b) memset(x, b, sizeof(x))
#define lowbit(x) ((x) & (-x))
#define P2(x) ((x) * (x))

typedef long long ll;
const int MOD = 1e9 + 7;
const int MAXN = 1e6 + 10;
const int INF = 0x3f3f3f3f;
inline ll fpow(ll a, ll b){ ll r = 1, t = a; while (b){ if (b & 1)r = (r*t) % MOD; b >>= 1; t = (t*t) % MOD; }return r; }

struct node
{
	int l, r;
	int lx, rx, ax, lzy; // lzy为1表示人满了，为0表示没人，为-1表示有人住但是不满
}t[MAXN * 4];
int n, m, flag;
void build(int rt, int l, int r) {
	t[rt].l = l, t[rt].r = r; // 初始状态下每个房间都没人
	t[rt].lx = t[rt].rx = t[rt].ax = r - l + 1;
	if (l == r) return;
	int mid = (l + r) >> 1;
	build(ls, l, mid);
	build(rs, mid + 1, r);
}
void Pushdown(int rt) {
	t[ls].lzy = t[rs].lzy = t[rt].lzy;
	if (t[rt].lzy == 0) {
		t[ls].lx = t[ls].rx = t[ls].ax = t[ls].r - t[ls].l + 1;
		t[rs].lx = t[rs].rx = t[rs].ax = t[rs].r - t[rs].l + 1;
	}
	else if (t[rt].lzy == 1) {
		t[ls].lx = t[ls].rx = t[ls].ax = 0;
		t[rs].lx = t[rs].rx = t[rs].ax = 0;
	}
	t[rt].lzy = -1;
}
int Query(int rt, int x) {
	if (t[rt].lx == x && t[rt].r - t[rt].l + 1 == x)
		return t[rt].l; // 前缀满足，则返回左边界
	if (t[rt].ax >= x) {
		if (t[rt].lzy != -1) Pushdown(rt);
		if (t[ls].ax >= x) return Query(ls, x); // 左边满足往左跑
		if (t[ls].rx + t[rs].lx >= x) return t[ls].r - t[ls].rx + 1; // 中间满足
		if (t[rs].ax >= x) return Query(rs, x); // 右边满足往右跑
	}
	return 0;
}
void Update(int rt, int l, int r) {
	if (t[rt].l == l && t[rt].r == r) { // 区间更新 or 单点更新
		if (flag) t[rt].lx = t[rt].rx = t[rt].ax = 0; // flag表示两个更新状态
		else t[rt].lx = t[rt].rx = t[rt].ax = r - l + 1; 
		t[rt].lzy = flag;
		return;
	}
	int mid = (t[rt].l + t[rt].r) >> 1;
	if (t[rt].lzy != -1) Pushdown(rt);
	if (mid >= r) Update(ls, l, r);
	else if (mid < l) Update(rs, l, r);
	else {
		Update(ls, l, mid);
		Update(rs, mid + 1, r);
	}
	if (t[ls].lzy == 0)  // 更新每个值
		t[rt].lx = t[ls].ax + t[rs].lx;
	else
		t[rt].lx = t[ls].lx; 
	if (t[rs].lzy == 0)
		t[rt].rx = t[rs].ax + t[ls].rx;
	else
		t[rt].rx = t[rs].rx;
	t[rt].ax = max(t[ls].ax, t[rs].ax); 
	t[rt].ax = max(t[rt].ax, max(t[ls].lx, max(t[rs].rx, t[ls].rx + t[rs].lx)));
	if (t[rt].ax == t[rt].r - t[rt].l + 1) t[rt].lzy = 0;
	else if (t[rt].ax == 0) t[rt].lzy = 1;
	else t[rt].lzy = -1;
}

int main()
{
	cin >> n >> m;
	build(1, 1, n);
	while (m--) {
		int op, ui, vi;
		sc("%d", &op);
		if (op == 1) {
			sc("%d", &ui);
			int ans = Query(1, ui);
			cout << ans << endl;
			if (ans) {
				flag = 1;
				Update(1, ans, ans + ui - 1);
			}
		}
		else {
			sc("%d %d", &ui, &vi);
			flag = 0;
			Update(1, ui, ui + vi - 1);
		}
	}
	return 0;
}