题解：P12031 [USACO25OPEN] Forklift Certified P
沉石鱼惊旋
·
·
题解
做法
一个简单的发现是，我们每个箱子只需要关心『右上角』下方的区域是否包含某个箱子的『左下角』。
但是删除箱子需要支持删掉某个 $x$ 的某个 $y$ 。而删掉之后新的 $y'$ 可能成为这一行的最小值，我们对线段树的叶子结点开 `std::set` 维护一下。
感谢 @[hard_plan](https://www.luogu.com.cn/user/749406) 指出，这里元素坐标都是不一样的（我一开始没看到这个信息，难过），叶子结点只需要记录对应值就可以了。
$M=1$ 考虑类似拓扑排序的做法。但是按枚举一个点然后枚举出边的做法肯定不行。我们考虑尝试删除 $u$ 的时候，找到一个挡住他的 $v$，尝试递归下去删掉 $v$。如果删掉 $v$ 之后没有障碍了就结束了，否则继续找到下一个 $v_2$ 去删掉，直到 $u$ 可以被删除。重复这个过程。显然每个点只会被删除一次。其实就是一个拓扑排序的 DFS 写法。
注意可能会出自环。先把 $u$ 点删掉就可以了。
# 代码
<https://www.luogu.com.cn/record/212388266>
```cpp
#include <bits/stdc++.h>
using namespace std;
#define getchar() p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++
char buf[1000000], *p1 = buf, *p2 = buf;
template <typename T>
void read(T &x)
{
x = 0;
int f = 1;
char c = getchar();
for (; c < '0' || c > '9'; c = getchar())
if (c == '-')
f = -f;
for (; c >= '0' && c <= '9'; c = getchar())
x = x * 10 + c - '0';
x *= f;
}
template <typename T, typename... Args>
void read(T &x, Args &...y)
{
read(x);
read(y...);
}
template <class T>
void write(T x)
{
static int stk[30];
if (x < 0)
putchar('-'), x = -x;
int top = 0;
do
{
stk[top++] = x % 10, x /= 10;
} while (x);
while (top)
putchar(stk[--top] + '0');
}
template <class T>
void write(T x, char lastChar) { write(x), putchar(lastChar); }
const int inf = 1e9;
int N, M;
int n;
struct point
{
int x, y;
};
point a[100020];
point b[100020];
array<int, 2> s[200020];
struct SegTree
{
struct node
{
array<int, 2> mn;
} t[200020 << 2];
#define ls id << 1
#define rs id << 1 | 1
#define Llen (mid - l + 1)
#define Rlen (r - mid)
void push_up(int id) { t[id].mn = min(t[ls].mn, t[rs].mn); }
void build(int id = 1, int l = 1, int r = N)
{
if (l == r)
return t[id].mn = {inf, -1}, void();
int mid = l + r >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
push_up(id);
}
void add(int pos, array<int, 2> v, int k, int id = 1, int l = 1, int r = N)
{
if (r < pos || l > pos)
return;
if (pos <= l && r <= pos)
{
if (k > 0)
s[pos] = v;
else
s[pos] = {0, 0};
t[id].mn = s[pos] == (array<int, 2>){0, 0} ? (array<int, 2>){inf, -1} : s[pos];
return;
}
int mid = l + r >> 1;
add(pos, v, k, ls, l, mid);
add(pos, v, k, rs, mid + 1, r);
push_up(id);
}
array<int, 2> query(int ql, int qr, int id = 1, int l = 1, int r = N)
{
if (r < ql || l > qr)
return {inf, -1};
if (ql <= l && r <= qr)
return t[id].mn;
int mid = l + r >> 1;
return min(query(ql, qr, ls, l, mid), query(ql, qr, rs, mid + 1, r));
}
} T;
namespace M1
{
bool vis[100020];
bool del[100020];
void dfs(int u)
{
if (del[u])
return;
if (!vis[u])
T.add(a[u].x, {a[u].y, u}, -1), vis[u] = 1;
auto [w, v] = T.query(1, b[u].x);
if (w >= b[u].y)
return del[u] = 1, write(u, ' ');
dfs(v);
dfs(u);
}
void solve()
{
read(n);
N = n << 1;
memset(vis, 0, sizeof(bool) * (n + 5));
memset(del, 0, sizeof(bool) * (n + 5));
T.build();
for (int i = 1; i <= n; i++)
read(a[i].x, a[i].y, b[i].x, b[i].y);
for (int i = 1; i <= n; i++)
T.add(a[i].x, {a[i].y, i}, 1);
for (int i = 1; i <= n; i++)
dfs(i);
putchar('\n');
}
};
namespace M2
{
void solve()
{
read(n);
N = n << 1;
T.build();
for (int i = 1; i <= n; i++)
read(a[i].x, a[i].y, b[i].x, b[i].y);
for (int i = 1; i <= n; i++)
T.add(a[i].x, {a[i].y, i}, 1);
for (int i = 1; i <= n; i++)
T.add(a[i].x, {a[i].y, i}, -1), write(T.query(1, b[i].x)[0] >= b[i].y);
putchar('\n');
}
}
int main()
{
int t;
read(t, M);
while (t--)
(M & 1 ? M1::solve() : M2::solve());
return 0;
}
```