专栏文章

题解：P12031 [USACO25OPEN] Forklift Certified P

CCommandSR作弊者
P12031题解参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@min4mlwv
此快照首次捕获于
2025/12/01 20:29
3 个月前
此快照最后确认于
2025/12/01 20:29
3 个月前
查看原文

Solution

仅使用线段树和树状数组，没有使用 set 的做法。

第一问

首先有一个 O(n2)O(n^2) 做法，如果 uu 被 vv 阻挡就建边 v→uv\rightarrow u，相当于 vv 一定要在 uu 之前删掉，然后直接输出拓扑序。
这个劣在建了大量多余的边，比如说有 u→vu\rightarrow v 和 v→wv\rightarrow w 那么再建 u→wu\rightarrow w 的边就没用。
那么有用的边构成一颗生成树，是 O(n)O(n) 级别的。
发现是一颗树后，我们反过来建边，那么删掉一个点需要先删掉它的儿子，我们一边 DFS 一边删点。
那么需要快速知道一个点的儿子有哪些，考虑用数据结构维护。对于一个点左下角 (x,y)(x,y) 我们在线段树 xx 的位置单点改成 yy，因为坐标各不相同所以直接单点改即可。
设当前点右上角坐标 (x2,y2)(x_2,y_2) 那么查询是否有儿子没删掉相当于在 [1,x2][1,x_2] 查一个最小的 y′y'，如果 y′>y2y' > y_2 那么相当于儿子全都被删光了，可以删 uu。否则先递归儿子，然后再递归一遍自己，查看有没有另外的儿子没删。因为边的规模是 O(n)O(n) 的所以复杂度是 O(nlog⁡n)O(n\log n) 级别。
删除一个点就是对应 xx 坐标改成 ∞\infin。

第二问

比第一问简单很多，倒着扫，按照上面的线段树维护方式一边更新一边查有没有点阻挡自己即可。可以使用树状数组代替。

Code

CPP
#include <bits/stdc++.h>
#define int long long
#define F(i, a, b) for (int i = (a); i <= (b); ++i)
#define D(i, a, b) for (int i = (a); i >= (b); --i)
#define FIO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define NO_MLE cerr<<fabs(&Med-&Mbe)/1048576.0<<"MB\n";
using namespace std;
const int inf = 1e12, N = 1e5 + 5;
int T, M, n;
struct V {
	int x, y, xx, yy, id;
} a[N];
void ckmin(int &x, int y) {
	if (y < x) x = y;
}
namespace Solver1 {
#define lc(x) (x<<1)
#define rc(x) (x<<1|1)
	int mn[N<<3], mp[N<<1];
	bool vis[N];
	void Build(int rt, int l, int r) {
		mn[rt] = inf;
		if (l == r) return;
		int mid = (l + r) >> 1;
		Build(lc(rt), l, mid), Build(rc(rt), mid + 1, r);
		mn[rt] = min(mn[lc(rt)], mn[rc(rt)]);
	}
	void Modify(int rt, int l, int r, int p, int x) {
		if (l == r) {
			mn[rt] = x;
			return;
		}
		int mid = (l + r) >> 1;
		(p <= mid ? Modify(lc(rt), l, mid, p, x) : Modify(rc(rt), mid + 1, r, p, x));
		mn[rt] = min(mn[lc(rt)], mn[rc(rt)]);
	}
	int Query(int rt, int l, int r, int L, int R) {
		if (l >= L && r <= R) return mn[rt];
		int mid = (l + r) >> 1, res = inf;
		if (L <= mid) ckmin(res, Query(lc(rt), l, mid, L, R));
		if (R > mid) ckmin(res, Query(rc(rt), mid + 1, r, L, R));
		return res;
	}
	void DFS(int u) {
		if (vis[u]) Modify(1,1,n<<1,a[u].x,inf), vis[u] = 0;
		int res = Query(1,1,n<<1,1,a[u].xx);
		if (res == inf || res > a[u].yy) {
			cout << u << ' '; return;
		}
		DFS(mp[res]), DFS(u);
	}
	void GOGO() {
		Build(1, 1, n<<1);
		F(i, 1, n) vis[i] = 1, mp[a[i].y] = i;
		F(i, 1, n) Modify(1,1,n<<1,a[i].x,a[i].y);
		F(i, 1, n) if (vis[i]) DFS(i);
		cout << '\n';
	}
}
namespace Solver2 {
	int tr[N<<1];
	bool ans[N];
	void upd(int p, int x) {
		for (; p <= 2*n; p += (p & -p)) ckmin(tr[p], x);
	}
	int qry(int p) {
		int res = inf;
		for (; p; p -= (p & -p)) ckmin(res, tr[p]);
		return res;
	}
	void GOGO() {
		F(i, 0, 2*n) tr[i] = inf;
		D(i, n, 1) {
			if (qry(a[i].xx) > a[i].yy) ans[i] = 1;
			else ans[i] = 0;
			upd(a[i].x, a[i].y);
		}
		F(i, 1, n) cout << ans[i]; cout << '\n';
	}
}
void mian() {
	cin >> n;
	F(i, 1, n) {
		cin >> a[i].x >> a[i].y >> a[i].xx >> a[i].yy;
		a[i].id = i;
	}
	if (M == 1) Solver1::GOGO();
	else Solver2::GOGO();
} 
signed main() {
	FIO cin >> T >> M; F(_, 1, T) mian();
	return 0;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...