【CodeForce】 46D Parking Lot （線段樹 區間合并）

題目大意：有一條長度為L的街道,有N個操作,操作有兩種,（1）"1 a"，表示有一輛長度為a的車開進來想找停車位,停車位必須滿足與它前面的車距離至少為b,與後面的車距離至少為f.如果能找到這樣的停車位,輸出這輛車的起始位置(且這個位置最小),否則輸出-1。（2）"2 a"，表示第a個事件裡進來停車的那輛車開出去了

思路：需要分4種情況

1、沒有前面和沒有後面，也就是正好這個車的長度等于停車場的長度

2、隻有後面，這個情況是指車正好放在0的位置。

3、隻有前面，這個情況是指車放在最後面的地方

4、都有的情況。

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAX 100010
#define ls rt<<1
#define rs ls|1
#define m (l+r)>>1
int sum[MAX << 2];
int lsum[MAX << 2];
int rsum[MAX << 2];
int col[MAX << 2];
struct
{
	int s, e;
}car[MAX];

void uprt(int len, int rt)
{
	lsum[rt] = lsum[ls];
	rsum[rt] = rsum[rs];
	if (lsum[rt] == len - (len >> 1))
		lsum[rt] += lsum[rs];
	if (rsum[rt] == (len >> 1))
		rsum[rt] += rsum[ls];
	sum[rt] = max(rsum[ls] + lsum[rs], max(sum[ls], sum[rs]));
}

void ups(int len, int rt)
{
	if (col[rt] != -1)
	{
		if (col[rt] == 0)
		{
			lsum[ls] = rsum[ls] = sum[ls] = 0;
			lsum[rs] = rsum[rs] = sum[rs] = 0;
		}
		else
		{
			lsum[rs] = rsum[rs] = sum[rs] = (len >> 1);
			lsum[ls] = rsum[ls] = sum[ls] = len - (len >> 1);
		}
		col[ls] = col[rs] = col[rt];
		col[rt] = -1;
	}
}

void updata(int L, int R, int c, int l, int r, int rt)
{
	int len = r - l + 1;
	if (L <= l&&r <= R)
	{
		col[rt] = c;
		if (c == 0)
			lsum[rt] = rsum[rt] = sum[rt] = 0;
		else
			lsum[rt] = rsum[rt] = sum[rt] = len;
		return;
	}
	ups(len, rt);
	int mid = m;
	if (L <= mid)
		updata(L, R, c, l, mid, ls);
	if (mid < R)
		updata(L, R, c, mid + 1, r, rs);
	uprt(len, rt);
}

int query(int len, int l, int r, int rt)
{
	if (l == r)
		return l;
	int mid=m;
	ups(r - l + 1, rt);
	if (sum[ls] >= len)
		return query(len, l, mid, ls);
	if (rsum[ls] + lsum[rs] >= len)
		return mid - rsum[ls] + 1;
	return query(len, mid + 1, r, rs);
}

void build(int l, int r, int rt)
{
	if (l == r)
	{
		lsum[rt] = rsum[rt] = sum[rt] = 1;
		return;
	}
	int mid = m;
	build(l, mid, ls);
	build(mid + 1, r, rs);
	uprt(r - l + 1, rt);
}
int main()
{
	int n, b, f;
	scanf("%d%d%d", &n, &b, &f);
	memset(col, -1, sizeof(col));
	n--;
	build(0, n, 1);
	int t;
	cin >> t;
	int x, y;
	int pos;
	int pos2;
	bool posx=0;
	int k = b + f;
	int cnt = 0;
	while (t--)
	{
		cnt++;
		scanf("%d%d", &x, &y);
		if (x == 1)
		{
			pos = -1;
			if (y == n + 1 && y == sum[1])
			{
				car[cnt].s = 0;
				car[cnt].e = n;
				updata(0, n, 0, 0, n, 1);
				puts("0");
				continue;
			}
			if (lsum[1] >= y + f)
			{
				pos = 0;
				updata(0, y - 1, 0, 0, n, 1);
				car[cnt].s = 0;
				car[cnt].e = y - 1;
			}
			else
			if (sum[1] >= y + k)
			{
				pos = query(y + k, 0, n, 1);
				pos += b;
				updata(pos, pos + y - 1, 0, 0, n, 1);
				car[cnt].s = pos;
				car[cnt].e = pos + y - 1;
			}
			else
			if (rsum[1] >= y + b)
			{
				pos = n - rsum[1] + b+1;
					updata(pos, pos + y - 1, 0, 0, n, 1);
					car[cnt].s = pos;
					car[cnt].e = pos + y - 1;
			}
			printf("%d\n", pos);
		}
		else
		{
			updata(car[y].s, car[y].e, 1, 0, n, 1);
			if (car[y].s == 0)
				posx = 0;
		}
	}
}