title: 题目
火山经营着一个停车场，假设的停车场有$N$车位（编号$1-N$）都在一条线上，最初所有车位都没停车。经常有人来定车位，他要定连续的$k(1 ≤ k ≤ N)$个车位。火山要确定是否能够满足客人的要求，如果能，他要将这$k$个连续的车位安排在编号最小的地方停下。若不能，则客人不停在火山的停车场。在某一时间，有些车会被车主开走了。火山的停车场很大，火山想让学弟学妹写个程序帮助他。
第1行输入$N$ 和 $M$。$N$是车位个数，M是停车和开走车操作的总次数
接下来M行，先输入操作类型（1或2）
若是1，表示有人来停车，再输入$k$
若是2，再输入$l$, $r$,表示区间$[l, l + r)$的车被开走了。
$N (1 ≤ N ≤ 50,000)$ $M (1 ≤ M < 50,000)$
当输入为1时，若火山的停车场有连续的k个车位，那么输出第一辆车停的最小的编号，否则输出0。
title: input
10 6
1 3
1 3
1 3
1 3
2 5 5
1 6
title: output
1
4
7
0
5
title: 思路
线段树记录每个区间的最大连续未停车长度, 叶子节点就是1/0. 父节点则判断左子树的连续区间是否和右子树的连续区间连接, 如果连接则为相加后长度, 若不连接则取最大长度。
用st,ed记录当前区间的最大停车长度会导致区间内两个相同长度的区间只能用其中一个, 对后续的区间合并有很大影响。
正解是储存 `lsum` 从左端点向右的停车长度, `rsum`从右端点向左的停车长度, 至于中间的区间两端都不占则会由 `msum`取代（max_sum), 这个`msum`也可以是`lsum / rsum` 只要他们的长度大于中间长度（因为可以完全代替且还方便合并,中间的区间是永远无法用来合并的）。
**建树**：
默认全空, 则直接将 `lsum = rsum = msum = len(区间长度)`
**更新**：
因为是区间更新, 使用**lazy**懒更新来优化时间。（有向上更新pushup和向下更新pushdown）
设当前节点为 `father`, 左子树为 `lson`, 右子树为 `rson`。
- **pushup**：
father的lsum, 直接等于 lson的lsum
father的rsum, 直接等于 rson的rsum
father的msum, 直接等于 lson和rson的 msum 最大值
接下来考虑是否合并区间
若lson的lsum跟它的区间长度相等, 也就是说全部都可以停车, 则`father的lsum = lson.lsum + rson.lsum`
若rson的rsum跟它的区间长度相等, 也就是说全部都可以停车, 则`father的rsum = ron.rsum + lson.rsum`
至于msum, 则在`(lson.msum, rson.msum, lson.rsum + rson.lsum)`
最后一项是中间拼接的结果。
- **pushdown**：
如果`lazy != -1`说明需要下放标记
如果是更新0(可以停)就 `lsum = rsum = msum = len`(左/右子树分别为 `len - len/2` / `len/2`)
如果是更新1(不可以停)就 `lsum = rsum = msum = 0`
**查询**：
若根节点的msum都小于k则直接输出0
若大于等于k则 优先往左边找, 左子树也大于等于k则继续找子节点。
直到找到一个节点它的左子树和右子树都小于k, 说明该区间就是要找的区间, 返回`mid - 左子树的rsum + 1` 即是区间最左边的点位置。
代码量很大, 但理清思路就很好写了, 注意规范码风这样不容易出现小错误。
title:代码
~~~ c ++
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5e4 + 10, M = N << 2;
struct Node
{
int l, r;
int lsum, rsum, msum;
void set(int val)
{
lsum = rsum = msum = val;
}
} t[M];
int lazy[M];
void pushup(int u, int len)
{
Node &l = t[u << 1], &r = t[u << 1 | 1]; // 用引用简化代码
t[u].lsum = l.lsum, t[u].rsum = r.rsum; // 不考虑合并区间
if (l.lsum == len - (len >> 1)) // 合并区间
t[u].lsum += r.lsum;
if (r.rsum == (len >> 1))
t[u].rsum += l.rsum;
t[u].msum = max(max(l.msum, r.msum), l.rsum + r.lsum);
}
void pushdown(int u, int len)
{
if (lazy[u] != -1)
{
Node &l = t[u << 1], &r = t[u << 1 | 1];
lazy[u << 1] = lazy[u << 1 | 1] = lazy[u]; // 标记下放
if (lazy[u])
l.set(0), r.set(0);
else
l.set(len - (len >> 1)), r.set(len >> 1);
lazy[u] = -1;
}
}
void build(int l, int r, int u = 1)
{
int len = r - l + 1;
// t[u] = {l, r, len, len, len}; // POJ不支持的特性
t[u].l = l, t[u].r = r, t[u].lsum = t[u].rsum = t[u].msum = len;
if (l == r)
return;
int mid = l + r >> 1;
build(l, mid, u << 1), build(mid + 1, r, u << 1 | 1);
}
void modify(int L, int R, int val, int u = 1)
{
if (t[u].l >= L && t[u].r <= R)
{
if (val)
t[u].set(0);
else
t[u].set(t[u].r - t[u].l + 1);
lazy[u] = val;
return;
}
pushdown(u, t[u].r - t[u].l + 1);
int mid = t[u].l + t[u].r >> 1;
if (mid >= L)
modify(L, R, val, u << 1);
if (R > mid)
modify(L, R, val, u << 1 | 1);
pushup(u, t[u].r - t[u].l + 1);
}
int query(int len, int u = 1)
{
if (t[u].l == t[u].r)
return t[u].l;
pushdown(u, t[u].r - t[u].l + 1);
int mid = t[u].l + t[u].r >> 1;
if (t[u << 1].msum >= len)
return query(len, u << 1);
else if (t[u << 1].rsum + t[u << 1 | 1].lsum >= len) // 要找的最小区间
return mid - t[u << 1].rsum + 1;
else
return query(len, u << 1 | 1);
}
int main()
{
cin.tie(0)->sync_with_stdio(false);
int n, m;
cin >> n >> m;
build(1, n);
memset(lazy, -1, sizeof lazy);
while (m--)
{
int op;
cin >> op;
if (op == 1)
{
cin >> op;
if (t[1].msum < op)
cout << 0 << "\n";
else
{
int res = query(op);
cout << res << "\n";
modify(res, res + op - 1, 1);
}
}
else
{
int l, r;
cin >> l >> r;
modify(l, l + r - 1, 0);
}
}
/*
for (int i = 1; i <= n + 2; i++)
cout << t[i].lsum << " " << t[i].rsum << " " << t[i].msum << endl;
*/
return 0;
}
~~~