题目描述

难度分:$1619$

输入$n(2 \leq n \leq 2 \times 10^5)$和$n$个盒子的长、宽、高，每行输入三个数，范围$[1,10^9]$。

你可以随意旋转盒子，也可以保持不变。

问：是否存在一个盒子可以被另一个盒子装下，也就是一个盒子的长宽高都分别严格小于另一个盒子的长宽高。

输出Yes或No。

输入样例$1$

3
19 8 22
10 24 12
15 25 11

输出样例$1$

Yes

输入样例$2$

3
19 8 22
10 25 12
15 24 11

输出样例$2$

No

输入样例$3$

2
1 1 2
1 2 2

输出样例$3$

No

算法

树状数组+有序map

这个题有个二维版本，但是要求的是最多的嵌套层数，将前两个维度进行双关键字排序（第一维升序，第二维降序）后可以通过求$LIS$在$O(nlog_2n)$的时间复杂度下求解。但是本题多了一维，并且可以随意旋转盒子，难度就高很多了。首先可以明确的是，最优解如果存在，肯定有一种是每个能嵌套的盒子，其长宽高是按照升序排列好的（可以反证法证明一下，把最优解变成这个样子一定不会让结果变差）。

可以先构建一个有序映射$boxes$“长 $\rightarrow$ （宽，高）的二元组数组”，有序映射按照“长”升序，而每个长对应的二元组数组按照“宽”降序排列，这样就和二维版本一致了，因为宽降序，所以在求长和宽都严格递增（后面的长大于前面的长，且后面的宽也大于前面的宽）的序列时可以保证在长不同的情况下，也不会选到相同的宽。

如果是要求$LIS$，肯定是没办法在$O(nlog_2n)$的时间复杂度下解决的，好在题目只要求判断是否存在长度为$2$的$LIS$，就好办很多了。以宽为索引开一个最小值树状数组（线段树也可以，但是树状数组常数小很多），树状数组的值为$box$的高。在遍历$boxes$时，已经保证了长的递增，而对于当前的箱子$(x,y,z)$，可以在树状数组小于$y$的范围内进行查询，以此保证第二维的递增，最后查询出的是高的最小值，只要这个值严格小于$z$，那就找到了一对三元组满足长宽高严格递增。

最后，考虑到箱子的每一维都$\leq 10^9$，因此还要记得对宽进行离散化才能构建出树状数组。

复杂度分析

时间复杂度

预处理出$boxes$就相当于遍历了一遍箱子序列，因为三个元素（长、宽、高）的排序可以看成是常数，因此是$O(n)$的。离散化的就相当于遍历了一遍$map$，同样是$O(n)$的，但是离散化完成之后需要对$boxes$每个$value$的二元组数组按照宽降序排列，时间复杂度是$O(nlog_2n)$。最后遍历$boxes$求答案，在遍历的过程中涉及到有限几次对树状数组的查询和更新操作，都是$O(log_2n)$的，因此算法整体的时间复杂度为$O(nlog_2n)$。

空间复杂度

空间上的痛点主要就是树状数组，有序映射，以及离散化时使用的有序表，都是$O(n)$级别的消耗，因此额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;
typedef pair<int, int> PII;

const int INF = 0x3f3f3f3f;

struct BIT {
    int n;
    vector<int> v;
    BIT(int n): n(n), v(n, INF) {}

    void update(int x, int y) {
        x++;
        for(; x <= n; x += lowbit(x)) {
            v[x - 1] = min(v[x - 1], y);
        }
    }

    int query(int x) {
        x = min(x, n - 1);
        int y = INF;
        x++;
        for(; x; x -= lowbit(x)) {
            y = min(y, v[x - 1]);
        }
        return y;
    }

    int lowbit(int x) {
        return x&-x;
    }
};

int main() {
    int n;
    scanf("%d", &n);
    map<int, vector<PII>> boxes;
    map<int, int> mp;
    for(int i = 0; i < n; i++) {
        int h, w, d;
        scanf("%d%d%d", &h, &w, &d);
        vector<int> box = {h, w, d};
        sort(box.begin(), box.end());
        boxes[box[0]].push_back({box[1], box[2]});
        mp[box[1]] = 0;
    }
    int m = 0;
    for(auto it = mp.begin(); it != mp.end(); it++) {
        it->second = ++m;
    }
    for(auto&[k, v]: boxes) {
        for(int i = 0; i < v.size(); i++) {
            v[i].first = mp[v[i].first];
        }
        sort(v.begin(), v.end());
        reverse(v.begin(), v.end());
    }
    bool flag = false;
    BIT bit(n);
    for(auto&[k, v]: boxes) {
        for(auto&tup: v) {
            int x = tup.first, y = tup.second;
            if(bit.query(x - 1) < y) {
                flag = true;
                break;
            }
            bit.update(x, y);
        }
        if(flag) break;
    }
    if(flag) puts("Yes");
    else puts("No");
    return 0;
}