Forklift Certified P

Mier_Samuelle · 2026-08-09 11:15:04 · 题解

首先 M=2 就是一个裸的三维偏序，可以 CDQ 分治，也可以维护一棵线段树，存一段 x 坐标区间内的最小 y 坐标，倒序将每个矩形的左下角插入线段树，查询一段前缀 min 即可。可做到 O(n \log n)。

考虑 M=1，朴素的想法是 O(n^2) 建图跑拓扑排序。先考虑优化建图，发现不太可做。那么就不建图了，直接 dfs。对于每个矩形，找到所有阻挡它的矩形，递归将它们删除，最后再把自己删除。这样每个矩形就只会被删一次。查找这一步可用上文提到的线段树，额外维护一下最小值对应的矩形编号，即可做到 O(\log n)，于是总复杂度 O(n \log n)。

:::success[Code]{open}

#include <bits/stdc++.h>
#define lc (u << 1)
#define rc ((u << 1) | 1)
#define mid ((l + r) >> 1)
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int xl[MAXN], yl[MAXN], xr[MAXN], yr[MAXN], n;
bool ans[MAXN], vis[MAXN];
vector <int> ord;
struct Segment_tree{
    int mn[MAXN * 8], idx[MAXN * 8];
    void pushup(int u){
        mn[u] = min(mn[lc], mn[rc]);
        idx[u] = (mn[lc] < mn[rc] ? idx[lc] : idx[rc]);
        return;
    }
    void build(int u, int l, int r){
        mn[u] = idx[u] = INF;
        if (l == r){
            return;
        }
        build(lc, l, mid);
        build(rc, mid + 1, r);
        return;
    }
    void modify(int u, int l, int r, int pos, int val, int id){
        if (l == r){
            mn[u] = val;
            idx[u] = id;
            return;
        }
        if (pos <= mid){
            modify(lc, l, mid, pos, val, id);
        }
        else{
            modify(rc, mid + 1, r, pos, val, id);
        }
        pushup(u);
        return;
    }
    pii query(int u, int l, int r, int ql, int qr){
        if (ql <= l && r <= qr){
            return {mn[u], idx[u]};
        }
        pii res = {INF, 0};
        if (ql <= mid){
            res = min(res, query(lc, l, mid, ql, qr));
        }
        if (qr > mid){
            res = min(res, query(rc, mid + 1, r, ql, qr));
        }
        return res;
    }
}tr;
void remove(int u){
    while (true){
        tr.modify(1, 1, 2 * n, xl[u], INF, INF);
        pii res = tr.query(1, 1, 2 * n, 1, xr[u]);
        int mn = res.fi, idx = res.se;
//      cout << u << " " << mn << " " << idx << "\n";
        tr.modify(1, 1, 2 * n, xl[u], yl[u], u);
        if (mn > yr[u]){
            break;
        }
        remove(idx);
    }
    tr.modify(1, 1, 2 * n, xl[u], INF, INF);
    ord.push_back(u);
    vis[u] = true;
    return;
}
void solve1(){
    cin >> n;
    tr.build(1, 1, 2 * n);
    for (int i = 1; i <= n; i++){
        cin >> xl[i] >> yl[i] >> xr[i] >> yr[i];
        tr.modify(1, 1, 2 * n, xl[i], yl[i], i);
    }
    for (int i = 1; i <= n; i++){
        vis[i] = false;
    }
    ord.clear();
    for (int i = 1; i <= n; i++){
        if (!vis[i]){
            remove(i);
        }
    }
    for (int x : ord){
        cout << x << " ";
    }
    cout << "\n";
    return;
}
void solve2(){
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> xl[i] >> yl[i] >> xr[i] >> yr[i];
    }
    tr.build(1, 1, 2 * n);
    for (int i = n; i >= 1; i--){
        int mn = tr.query(1, 1, 2 * n, 1, xr[i]).fi;
        ans[i] = (mn > yr[i]);
        tr.modify(1, 1, 2 * n, xl[i], yl[i], i);
    }
    for (int i = 1; i <= n; i++){
        cout << ans[i];
    }
    cout << "\n";
    return;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t, m;
    cin >> t >> m;
    while (t--){
        if (m == 1){
            solve1();
        }
        else{
            solve2();
        }
    }
    return 0;
}

:::