题目描述
一家旅馆共有N个房间,这N个房间是连成一排的,标号为1-N。
现在有很多旅客以组为单位前来入住,每组旅客的数量可以用Di来表示。
旅店的业务分为两种,入住和退房:
1、旅客入住时,第i组旅客需要根据他们的人数Di,给他们安排Di个连续的房间,并且房间号要尽可能的小。如果房间不够,则无法安排。
2、旅客退房时,第i组旅客的账单将包含两个参数Xi和Di,你需要将房间号Xi到Xi+Di−1之间的房间全部清空。
现在你需要帮助该旅馆处理M单业务。
旅馆最初是空的。
输入数据
第一行输入两个用空格隔开的整数N和M。
接下来M行将描述M单业务:
“1 Di”表示这单业务为入住业务。
“2 Xi Di”表示这单业务为退房业务。
输出数据
每个入住业务输出一个整数,表示要安排的房间序列中的第一个房间的号码。
如果没办法安排,则输出0。
每个输出占一行。
数据范围
1≤Di≤N≤50000,
1≤M<50000
样例
输入样例:
10 6
1 3
1 3
1 3
1 3
2 5 5
1 6
输出样例:
1
4
7
0
5
算法
线段树
C++ 代码
#include <iostream>
using namespace std;
int n, m;
int a, x, d;
struct node
{
int l, r;
int sum, mx, lm, rm;
int lazy;
}tree[200010];
void pushup(node& f, node& l, node& r)
{
f.sum = l.sum + r.sum;
f.lm = l.lm;
if (l.lm == l.sum) //l区间内的房间全部为空时
f.lm = l.sum + r.lm;
f.rm = r.rm;
if (r.rm == r.sum)
f.rm = r.sum + l.rm;
f.mx = max(max(l.mx, r.mx), l.rm + r.lm);
return;
}
void pushdown(node& f, node& l, node& r)
{
if (f.lazy == 1)
{
l.mx = l.lm = l.rm = r.mx = r.lm = r.rm = 0;
}
else if (f.lazy == 2)
{
l.mx = l.lm = l.rm = l.sum;
r.mx = r.lm = r.rm = r.sum;
}
l.lazy = r.lazy = f.lazy;
f.lazy = 0;
return;
}
void build(int now, int start, int end)
{
if (start == end)
{
tree[now].l = tree[now].r = start;
tree[now].sum = tree[now].mx = tree[now].lm = tree[now].rm = 1;
return;
}
tree[now].l = start;
tree[now].r = end;
int mid = (start + end) >> 1;
build(now << 1, start, mid);
build(now << 1 | 1, mid + 1, end);
pushup(tree[now], tree[now << 1], tree[now << 1 | 1]);
return;
}
void update(int now, int l, int r, int lazy)
{
if (tree[now].l >= l && tree[now].r <= r)
{
if (lazy == 1)
{
tree[now].mx = tree[now].lm = tree[now].rm = 0;
}
else if (lazy == 2)
{
tree[now].mx = tree[now].lm = tree[now].rm = tree[now].sum;
}
tree[now].lazy = lazy;
return;
}
if (tree[now].lazy)
pushdown(tree[now], tree[now << 1], tree[now << 1 | 1]);
int mid = (tree[now].l + tree[now].r) >> 1;
if (l <= mid)
update(now << 1, l, r, lazy);
if (r > mid)
update(now << 1 | 1, l, r, lazy);
pushup(tree[now], tree[now << 1], tree[now << 1 | 1]);
return;
}
int query(int now, int len)
{
if (tree[now].mx < len)
return 0;
if (tree[now].lazy)
pushdown(tree[now], tree[now << 1], tree[now << 1 | 1]);
if (tree[now << 1].mx >= len)
return query(now << 1, len);
if (tree[now << 1].rm + tree[now << 1 | 1].lm >= len)
return tree[now << 1].r - tree[now << 1].rm + 1;
if (tree[now << 1 | 1].mx >= len)
return query(now << 1 | 1, len);
return 0;
}
int main()
{
cin >> n >> m;
build(1, 1, n);
while (m--)
{
cin >> a;
if (a == 1)
{
cin >> d;
int res = query(1, d);
cout << res << endl;
if (res)
update(1, res, res + d - 1, 1);
}
else
{
cin >> x >> d;
update(1, x, x + d - 1, 2);
}
}
return 0;
}