题目描述
一家旅馆共有 N 个房间,这 N 个房间是连成一排的,标号为 1∼N。
现在有很多旅客以组为单位前来入住,每组旅客的数量可以用 Di 来表示。
旅店的业务分为两种,入住和退房:
旅客入住时,第 i 组旅客需要根据他们的人数 Di,给他们安排 Di 个连续的房间,并且房间号要尽可能的小。如果房间不够,则无法安排。
旅客退房时,第 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
线段树 + 延迟更新
多写写题解加深理解下。
设序列1-n,起初都为0,当被占用则为1。分析题意得出有2种操作
- 找出序列1-n中第一个长度为len的连续0子串,返回该子串左端点,并将该子串全部置为1。
- 给定[l,r],使该区间的值全部置为0。
可以看出具有区间查询、区间修改的特点,所以考虑使用线段树。
使用线段树最应该考虑的问题是:我们需要维护的信息是什么?如何构造合适的变量去维护?
可以看出对于任意区间[l,r],我们需要快速获取其最长连续0子串的长度,由经验得:使用ld以l为起点最长0子串长度,rd以r为终点最长0子串长度两个变量,就能够从ls和rs的信息中更新出d最长连续9子串的长度。至此我们就可以完成build函数和pushup函数了。
如何完成操作1,即如何查询答案?首先记住我们的目标是找出长度为len的连续0子串,并返回其左端点编号。在我们的query函数中,对于任意树节点所表示的区间[pi,pr]:
- 若该区间p.d < len,则在该区间找不到答案,否则答案就在该区间内
- 若p.d == len && p.d == pr - pi + 1,表示该区间刚好合适,pi就是答案
- 若p.ls.d >= len,答案就在左子区间里,否则答案要么是完全在右子区间里或者左区间的.rd和右区间的.ld组成
- 若p.ls.rd + p.rs.ld >= len,则答案为 p.ls.r - p.ls.rd + 1。
- 递归右子区间。
考虑延迟更新?由于我们的操作要么是将一段序列全部变为1,要么全部0。当操作区间[l,r]覆盖了某个树节点区间[pi,pr],则不需要继续深入子节点进行更新数据,直接将该区间的信息更新即可,并加以标记。
时间复杂度
$O(mlogn)$
C++ 代码
#include <iostream>
#include <cmath>
using namespace std;
const int N = 50010;
struct Seg
{
int l, r;
int d, ld, rd;
int lazy;
} tr[N * 4];
int n, m;
void pushup(Seg &a, Seg &b, Seg &c)
{
a.d = max(max(b.d, c.d), b.rd + c.ld);
a.ld = (b.r - b.l + 1) == b.d ? b.d + c.ld : b.ld;
a.rd = (c.r - c.l + 1) == c.d ? c.d + b.rd : c.rd;
}
void pushup(int u)
{
pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
void change(int u, int x)
{
tr[u].d = tr[u].ld = tr[u].rd = x;
}
void pushdown(int u)
{
if (!tr[u].lazy) return;
if (tr[u].lazy == 1)
{
change(u << 1, 0);
change(u << 1 | 1, 0);
}
else
{
change(u << 1, tr[u << 1].r - tr[u << 1].l + 1);
change(u << 1 | 1, tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1);
}
tr[u << 1].lazy = tr[u << 1 | 1].lazy = tr[u].lazy;
tr[u].lazy = 0;
}
void build(int u, int l, int r)
{
if (l == r) tr[u] = {l, l, 1, 1, 1, 0};
else
{
tr[u].l = l, tr[u].r = r;
int mid = (l + r) >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
int query(int u, int len)
{
if (tr[u].d < len) return 0;
if (tr[u].d == len && tr[u].d == (tr[u].r - tr[u].l + 1)) return tr[u].l;
pushdown(u);
if (tr[u << 1].d >= len) return query(u << 1, len); //在左半区
if (tr[u << 1].rd + tr[u << 1 | 1].ld >= len) return tr[u << 1].r - tr[u << 1].rd + 1;
return query(u << 1 | 1, len);
}
void modify(int u, int l, int r, int k)
{
if (l <= tr[u].l && tr[u].r <= r)
{
if (k == 1)
{
//开房
change(u, 0);
}
else
{
//退房
change(u, tr[u].r - tr[u].l + 1);
}
tr[u].lazy = k;
}
else
{
pushdown(u);
int mid = (tr[u].l + tr[u].r) >> 1;
if (l <= mid) modify(u << 1, l, r, k);
if (r > mid) modify(u << 1 | 1, l, r, k);
pushup(u);
}
}
int main()
{
cin >> n >> m;
build(1, 1, n);
for (int i = 1; i <= m; i ++)
{
int op;
cin >> op;
if (op == 1)
{
int c;
cin >> c;
int left = query(1, c);
cout << left << endl;
if (left)
{
modify(1, left, left + c - 1, 1);
}
}
else
{
int l, r;
cin >> l >> r;
modify(1, l, l + r - 1, -1);
}
}
}
牛