题解：P2894 [USACO08FEB] Hotel G
Toorean
·
·
题解
一道不错的线段树入门题。
简略题意：m 个查询：查询 L 最小的 [L,L+x-1] 连续 0 段，若存在则这段变为 1；操作把 [x,x+y-1] 段变为 0。
我们先考虑如何判断是否存在连续的 x 长空段。于是自然地想到线段树维护连续段，当根节点的最大连续段不小于 x 有解。
接下来考虑如何找到答案。为了保证答案尽量小，我们从左至右地依次讨论：
- 若左子树区间最大连续段不小于 x，向左子树递归。
- 若跨过左右子树最大连续段不小于 x，那么答案就已经确定，直接返回即可（具体看代码）。
- 若右子树最大连续段不小于 x，向右子树递归。
如此的，我们便可唯一确定最小答案。
对于修改操作，我们只需维护三个值：
这样，便可维护整个序列。
```cpp
struct SegmenTree {
struct node {
int l, r;
int lmax, rmax, smax;
int lazy;
int siz () { return r - l + 1; }
} t[MAXN << 2];
#define ls (x << 1)
#define rs (x << 1 | 1)
void upd (int x, int k) { t[x].lazy = k, t[x].lmax = t[x].rmax = t[x].smax = t[x].siz () * (k ^ 1); }
void pushup (int x) { t[x].lmax = (t[ls].lmax == t[ls].siz () ? t[ls].lmax + t[rs].lmax : t[ls].lmax), t[x].rmax = (t[rs].rmax == t[rs].siz () ? t[rs].rmax + t[ls].rmax : t[rs].rmax); t[x].smax = max ({t[ls].smax, t[rs].smax, t[ls].rmax + t[rs].lmax}); }
void pushdown (int x) { if (t[x].lazy != -1) upd (ls, t[x].lazy), upd (rs, t[x].lazy); t[x].lazy = -1; }
void build (int x, int l, int r) {
t[x].l = l, t[x].r = r;
t[x].lmax = t[x].rmax = t[x].smax = 0;
t[x].lazy = -1;
if (l == r) return t[x].rmax = t[x].lmax = t[x].smax = 1, void ();
int mid = l + r >> 1;
build (ls, l, mid); build (rs, mid + 1, r);
pushup (x);
}
int query (int x, int l, int r, int len) {
int mid = l + r >> 1;
pushdown (x);
if (t[ls].smax >= len) return query (ls, l, mid, len);
else if (t[ls].rmax + t[rs].lmax >= len) return mid - t[ls].rmax + 1; // 左子树右端点最大连续段起点即为答案
else if (t[rs].smax >= len) return query (rs, mid + 1, r, len);
else return 0;
}
void modify (int x, int l, int r, int k) {
if (t[x].l > r || l > t[x].r) return;
if (t[x].l >= l && t[x].r <= r) return upd (x, k);
pushdown (x);
modify (ls, l, r, k); modify (rs, l, r, k);
pushup (x);
}
} t;
```
结语：这题与 [P4513](https://www.luogu.com.cn/problem/P4513) 其实很像，所采用的思想都一致。这题的关键在于想到这个 Trick 是否能进一步思考下去，进而写出正确的 query 函数。