题解：P12031 [USACO25OPEN] Forklift Certified P

· · 题解

Solution

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

第一问

首先有一个 O(n^2) 做法，如果 u 被 v 阻挡就建边 v\rightarrow u，相当于 v 一定要在 u 之前删掉，然后直接输出拓扑序。

这个劣在建了大量多余的边，比如说有 u\rightarrow v 和 v\rightarrow w 那么再建 u\rightarrow w 的边就没用。

那么有用的边构成一颗生成树，是 O(n) 级别的。

发现是一颗树后，我们反过来建边，那么删掉一个点需要先删掉它的儿子，我们一边 DFS 一边删点。

那么需要快速知道一个点的儿子有哪些，考虑用数据结构维护。对于一个点左下角 (x,y) 我们在线段树 x 的位置单点改成 y，因为坐标各不相同所以直接单点改即可。

设当前点右上角坐标 (x_2,y_2) 那么查询是否有儿子没删掉相当于在 [1,x_2] 查一个最小的 y'，如果 y' > y_2 那么相当于儿子全都被删光了，可以删 u。否则先递归儿子，然后再递归一遍自己，查看有没有另外的儿子没删。因为边的规模是 O(n) 的所以复杂度是 O(n\log n) 级别。

删除一个点就是对应 x 坐标改成 \infin。

第二问

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

Code

#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;
}