题目描述
有一间旅馆，旅馆内有n间排成一排的房间，一开始全为空。现在有m个要求：
1 d表示询问旅馆内是否有连续d间空房间，有的话则输出最小的一个r，满足从r开始连续d间房间均为空，同时会有人入住这d间房。若无法被满足，则输出0.
2 l r表示把[l,l + r]内的房间全部设为空。
思路
我们可以用线段树记录下每一个区间的数个值:
1.t.l 记录每一个区间的左区间从左端开始的连续空房间数量
2.t.r 记录每一个区间的右区间从右端开始的连续空房间数量
3.t.tot 记录每一个区间的最大连续空房间的数量
首先我们来考虑查找:
对于一个询问x,我们要找到最靠左的连续x个空房间
那么根据题意，我们显然要找尽可能靠左的，所以我们可以先判断左区间的tot，如果tot>=x那么我们显然是可以往左区间找的
如果无法往左区间找的话，我们也不可以直接往右区间找，因为一个连续的区间可能在线段树里面被分成了两份
这时我们就要判断一下左区间的r和右区间的l相加>=x 如果满足的话，那么我们要找的最左端就在分开的位置(mid) - 左区间的r + 1;
最后我们再判断是否在右区间中
以上的步骤中，显然如果t[1].tot
然后我们在来考虑两种更改
一种是将我们上面说的区间的点全部付为有人住
我们可以设我们找到的最左的点为 left, 那么我们其实就是将区间[left, left + x - 1] 改为有人住
我们可以直接将这个区间里的全部状态(l, r, tot)改为0
另外一种是将一段区间全部改为没有人住
对于这一个区间，我们可以将其的全部状态(l, r, tot)改为当前区间的长度 r-l+1,因为我们进行更改的区间显然是全部为空房间的，所以这一个付值很显然是没有问题的
对于下传每个区间的状态我们可用用lazy来完成，对于lazy的方式这里就不讲了，不打lazy的话可能也不会有问题
然后我们在来考虑向上传递状态
显然在一般的情况下，当前区间的l == 左区间的l 右区间类似
然后我们考虑如果左右区间中有整个区间都为空房间的情况，这时我们当前的区间(设为t[p])就可以有
1.当左区间全为空房间t[p].l+=t[p<<1|1].l
对于有区间类似
最后我们考虑每一个区间(设为t[p])的tot，t[p].tot=max(max(t[p<<1].tot, t[p<<1|1].tot), t[p<<1].r+t[p<<1|1].l)
简单来说就是左右区间的tot和两个区间合并后中间的部分所构成的连续空房间进行比较，取最大值即可
#include
#define maxn 1500001
#define max(x, y) (x) > (y) ? (x) : (y)
#define min(x, y) (x) < (y) ? (x) : (y)
struct tree
{
int tot, l, r, cover;
}t[maxn];
int ll = 0;
int make(int p, int l, int r)
{
t[p].cover = -1;
t[p].tot = t[p].l = t[p].r = r - l + 1;
if (l == r)
{
return 0;
}
int m = (l + r) >> 1;
make(p << 1, l, m);
make(p << 1 | 1, m + 1, r);
}
int pushdown(int p, int k)
{
if (t[p].cover != -1)
{
t[p << 1].cover = t[p << 1 | 1].cover = t[p].cover;
if (t[p].cover == 0)
{
t[p << 1].l = t[p << 1].r = t[p << 1].tot = k - (k >> 1);
t[p << 1 | 1].l = t[p << 1 | 1].r = t[p << 1 | 1].tot = (k >> 1);
}
else
{
t[p << 1].l = t[p << 1].r = t[p << 1].tot = t[p << 1 | 1].l = t[p << 1 | 1].r = t[p << 1 | 1].tot = 0;
}
t[p].cover = -1;
}
return 0;
}
int find(int p, int l, int r, int x)
{
if (l == r)
return 1;
pushdown(p, r - l + 1);
int m = (l + r) >> 1;
if (t[p << 1].tot >= x) return find(p << 1, l, m, x);
else if(t[p << 1].r + t[p << 1 | 1].l >= x) return m - t[p << 1].r + 1;
else return find(p << 1 | 1, m + 1, r, x);
}
int pushup(int p, int k)
{
t[p].l = t[p << 1].l;
t[p].r = t[p << 1 | 1].r;
if (t[p].l == k - (k >> 1))
t[p].l += t[p << 1 | 1].l;
if (t[p].r == (k >> 1))
t[p].r += t[p << 1].r;
t[p].tot = max(t[p << 1].r + t[p << 1 | 1].l, max(t[p << 1].tot, t[p << 1 | 1].tot));
return 0;
}
int change(int p, int l, int r, int x, int y, int c)
{
if (x == l && r == y)
{
if (c == 1)
t[p].tot = t[p].l = t[p].r = 0;
else t[p].tot = t[p].l = t[p].r = r - l + 1;
t[p].cover = c;
return 0;
}
pushdown(p, r - l + 1);
int m = (l + r) >> 1;
if (y <= m) change(p << 1, l, m, x, y, c);
else if (x > m) change(p << 1 | 1, m + 1, r, x, y, c);
else
{
change(p << 1, l, m, x, m, c);
change(p << 1 | 1, m + 1, r, m + 1, y, c);
}
pushup(p, r - l + 1);
}
int main()
{
int n, m;
scanf("%d%d", &n, &m);
make(1, 1, n);
for (int i = 1; i <= m; i++)
{
int x;
scanf("%d", &x);
if (x == 1)
{
int y;
scanf("%d", &y);
if (t[1].tot < y) printf("0\n");
else
{
int l = find(1, 1, n, y);
printf("%d\n", l);
change(1, 1, n, l, y + l - 1, 1);
}
}
else
{
int y, z;
scanf("%d%d", &y, &z);
change(1, 1, n, y, y + z - 1, 0);
}
}
return 0;
}
]]>
Comments NOTHING