【每日一题】补档 ABC309F - Box in Box

题目内容

原题链接

给定 n n n 个箱子，问是否存在一个箱子 x x x 是否可以放到另一个箱子 y y y 里。
需要满足 h x < h y , w x < w y , d x < d y h_x<h_y,w_x<w_y,d_x<d_y hx​<hy​,wx​<wy​,dx​<dy​。
箱子可以随意翻转。

数据范围

1 ≤ n ≤ 2 ⋅ 1 0 5 1\leq n\leq 2\cdot 10^5 1≤n≤2⋅105
1 ≤ h i , w i , d i ≤ 1 0 9 1\leq h_i,w_i,d_i\leq 10^9 1≤hi​,wi​,di​≤109

题解

首先按从小到大对 h , w , d h,w,d h,w,d 进行排序。

这里假设对所有的箱子，排序后都有 h ≤ w ≤ d h\leq w\leq d h≤w≤d

那么我们再按照 h h h 为第一关键字， w w w 为第二关键字， d d d 为第三关键字对箱子进行从小到大的排序。

然后我们从按 h h h 从小到大枚举，每次将所有 h h h 相同的箱子一起枚举。

这样，我们就可以对剩下的 w w w 和 d d d 构建树状数组了。

对于箱子 i i i ，找到 h j < h i h_j<h_i hj​<hi​ 的 j j j ，且 w j < w i w_j<w_i wj​<wi​ 的最小的 d j d_j dj​ 。判断 d j < d i d_j < d_i dj​<di​ 是否成立即可。

然后在判断完后，将所有值为 h i h_i hi​ 的箱子都加入到树状数组中。

如 q u e r y ( p ) query(p) query(p) 其实是在求 w ≤ p w\leq p w≤p 的最小的 d d d 。

这个问题又叫三维偏序。

时间复杂度： O ( n log ⁡ n ) O(n\log n) O(nlogn)

代码

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;

struct Node {
    int a[3];
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<Node> vec(n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 3; ++j) cin >> vec[i].a[j];
        sort(vec[i].a, vec[i].a + 3);
    }

    sort(vec.begin(), vec.end(), [](const Node& A, const Node& B) {
        return A.a[0] < B.a[0];
    });

    vector<int> b;
    for (int i = 0; i < n; ++i) b.push_back(vec[i].a[1]);
    sort(b.begin(), b.end());
    b.erase(unique(b.begin(), b.end()), b.end());

    auto get = [&](int x) {
        return int(lower_bound(b.begin(), b.end(), x) - b.begin() + 1);
    };

    for (int i = 0; i < n; ++i) vec[i].a[1] = get(vec[i].a[1]);

    int m = int(b.size());
    vector<int> tr(m + 1, INF);

    auto update = [&](int p, int x) {
        while (p <= m) {
            tr[p] = min(tr[p], x);
            p += (p & -p);
        }
    };

    auto query = [&](int p) {
        int res = INF;
        while (p >= 1) {
            res = min(res, tr[p]);
            p -= (p & -p);
        }
        return res;
    };

    bool ok = false;
    for (int i = 0; i < n; ++i) {
        int j = i + 1;
        while (j < n && vec[j].a[0] == vec[i].a[0]) j += 1;

        // 找到是否存在这么一个即可
        for (int k = i; k < j; ++k) {
            if (query(vec[k].a[1] - 1) < vec[k].a[2]) {
                ok = true;
                break;
            }
        }
        if (ok) break;

        // 把当前的部分全部添加进去
        for (int k = i; k < j; ++k) {
            update(vec[k].a[1], vec[k].a[2]);
        }

        i = j - 1;
    }

    if (ok) cout << "Yes\n";
    else cout << "No\n";

    return 0;
}