【每日一题】补档 ABC309F - Box in Box | 三维偏序 | 树状数组 | 中等

题目内容

原题链接

给定 $n$ 个箱子，问是否存在一个箱子 $x$ 是否可以放到另一个箱子 $y$ 里。
需要满足 $h_x<h_y,w_x<w_y,d_x<d_y$。
箱子可以随意翻转。

数据范围

$1\le n\le 2\cdot 10^5$
$1\le h_i,w_i,d_i\le 10^9$

题解

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

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

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

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

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

对于箱子 $i$ ，找到 $h_j<h_i$ 的 $j$ ，且 $w_j<w_i$ 的最小的 $d_j$ 。判断 $d_j<d_i$ 是否成立即可。

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

如 $query(p)$ 其实是在求 $w\le p$ 的最小的 $d$ 。

这个问题又叫三维偏序。

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

代码

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