问题回顾 #

我们有n名玩家，每名玩家拥有A、B、C三个属性值。如果存在另一名玩家j，满足A[j] > A[i]、B[j] > B[i]且C[j] > C[i]，那么玩家i无法获胜。需要统计所有无法获胜的玩家数量。

暴力解法的局限性 #

最直接的思路是暴力遍历每个玩家，检查是否存在满足条件的玩家j，代码如下：

int count_players_cannot_win(vector<vector<int>> values) {
    int c = 0;
    int n = values.size();
    for(int i = 0; i < n; i++) {
        for(int j = 0; j!= i && j < n; j++) {
            if(values[i][0] < values[j][0] && values[i][1] < values[j][1] && values[i][2] < values[j][2]) {
                c += 1;
                break;
            }
        }
    }
    return c;
}

但这个解法的时间复杂度是O(n²)，当n≤1e5时，1e10级别的操作次数会直接导致超时（TLE），必须用更高效的方法。

最优解法：线段树优化（O(nlogn)） #

这个问题属于三维偏序问题的简化版，我们可以通过排序+线段树的组合将时间复杂度降到O(nlogn)，核心思路如下：

1. 排序预处理

首先对玩家按A属性降序排序，如果A属性相同，则按B属性升序排序。这样做的好处是：

• 当处理到某个玩家时，已经处理过的所有玩家的A属性都≥当前玩家的A属性。
• 同A属性的玩家按B升序排序，确保同A的玩家不会互相干扰（因为A相同，不可能满足A[j]>A[i]）。

2. B属性的坐标压缩

由于B属性的取值范围可能很大（比如到1e9），直接用B值作为线段树的下标不现实，所以我们需要对B属性做离散化：

• 收集所有玩家的B属性值并排序。
• 对于每个玩家的B值，用lower_bound找到它在排序后数组中的位置，将B的范围压缩到0~n-1，这样线段树的大小就可控了。

3. 线段树的作用

线段树用来维护当前已处理玩家中，B属性大于某个值的所有玩家的最大C属性值。对于每个玩家，我们只需要查询线段树中B[i]对应位置之后的最大C值：

• 如果这个最大值大于当前玩家的C值，说明存在一个已处理的玩家（A≥当前，B>当前，C>当前），也就是存在j满足A[j]>A[i]、B[j]>B[i]、C[j]>C[i]，当前玩家无法获胜。
• 查询完成后，再将当前玩家的C值更新到线段树对应的B位置（保留最大值，因为相同B值的玩家中，最大的C值对后续查询最有意义）。

4. 批量处理同A的玩家

为了避免同A属性的玩家互相影响，我们会批量处理所有A属性相同的玩家：先统一查询这些玩家是否无法获胜，再统一将他们的C值更新到线段树中。这样同A的玩家不会被计入彼此的判断条件。

完整代码实现 #

#include <vector>
#include <algorithm>
#include <climits>
#include <iostream>
using namespace std;

int n;
const int N = 4e5 + 1;
int tree[N];

// 查询[L, n-1]区间内的最大C值
int get_max(int i, int l, int r, int L) {
    if(r < L || n <= l) return INT_MIN;
    else if(L <= l) return tree[i];
    int m = (l + r)/2;
    return max(get_max(2*i+1, l, m, L), get_max(2*i+2, m+1, r, L));
}

// 更新线段树中pos位置的最大值为v
void update(int i, int l, int r, int pos, int v) {
    if(r < pos || pos < l) return;
    else if(l == r) {
        tree[i] = max(tree[i], v);
        return;
    }
    int m = (l + r)/2;
    update(2*i+1, l, m, pos, v);
    update(2*i+2, m + 1, r, pos, v);
    tree[i] = max(tree[2*i+1], tree[2*i+2]);
}

// 排序比较函数：A降序，A相同则B升序
bool comp(vector<int> a, vector<int> b) {
    return a[0] != b[0] ? a[0] > b[0] : a[1] < b[1];
}

int solve(vector<vector<int>> &v) {
    n = v.size();
    vector<int> b(n);
    // 收集所有B属性用于离散化
    for(int i = 0; i < n; i++) {
        b[i] = v[i][1];
    }
    sort(b.begin(), b.end());
    
    // 按A降序、B升序排序玩家
    sort(v.begin(), v.end(), comp);
    
    int ans = 0;
    for(int i = 0; i < n;) {
        int j = i;
        // 批量查询所有A相同的玩家
        while(j < n && v[j][0] == v[i][0]) {
            int B_val = v[j][1];
            // 找到B_val离散化后的位置
            int pos = lower_bound(b.begin(), b.end(), B_val) - b.begin();
            // 查询B大于当前B_val的最大C值
            int max_c = get_max(0, 0, n - 1, pos + 1);
            if(max_c > v[j][2]) {
                ans++;
            }
            j++;
        }
        // 批量更新线段树，加入所有A相同的玩家
        while(i < j) {
            int B_val = v[i][1];
            int C_val = v[i][2];
            int pos = lower_bound(b.begin(), b.end(), B_val) - b.begin();
            update(0, 0, n - 1, pos, C_val);
            i++;
        }
    }
    return ans;
}

样例验证 #

拿题目中的样例输入来看：

3
1 4 2
4 3 2
2 5 3

排序后的玩家顺序是：

1. (4,3,2) → A最大
2. (2,5,3) → A次之
3. (1,4,2) → A最小

处理过程：

• 先处理A=4的玩家：此时线段树为空，查询结果为INT_MIN，不计数；然后将B=3（离散化位置0）的C=2更新到线段树。
• 处理A=2的玩家：查询B>5的位置（离散化后B=5在排序后的b数组中是最后一位，pos+1=3，超出范围，查询结果INT_MIN），不计数；然后将B=5（位置2）的C=3更新到线段树。
• 处理A=1的玩家：查询B>4的位置（pos是1，查询[1,2]区间的最大C，结果是3），3>2，所以计数+1；然后更新线段树。

最终答案是1，和样例输出一致。

内容的提问来源于stack exchange，提问作者tusharRawat