我们给了n个玩家，每个玩家有3个值分别分配给A，B和C。

如果存在另一个具有所有三个值A [j]> A [i]，B [j]> B [i]和C [j]> C [i]的玩家j，则玩家i无法获胜。我们被要求找到无法获胜的玩家数量。

我使用蛮力尝试了这个问题，蛮力是对玩家数组的线性搜索。但是它显示TLE。

对于每个玩家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 ^ 2），因为对于每个玩家，我们都遍历整个数组。因此，它给了TLE。

样本测试用例：

Sample Input

3(number of players)
A B C
1 4 2
4 3 2
2 5 3

Sample Output :

1 

Explanation :
Only player1 cannot win as there exists player3 whose all 3 values(A, B and C) are greater than that of player1.

限制条件：

n(number of players) <= 10^5

解决该问题的最佳方法是什么？

解决方案：

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

int get_max(int i, int l, int r, int L) {  // range query of max in range v[B+1: n]
    if(r < L || n <= l)
        return numeric_limits<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));
}
void update(int i, int l, int r, int on, int v) { // point update in tree[on]
    if(r < on || on < l) 
        return;
    else if(l == r) {
        tree[i] = max(tree[i], v);
        return;
    }
    int m = (l + r)/2;
    update(2*i+1, l, m, on, v);
    update(2*i+2, m + 1, r, on, v);
    tree[i] = max(tree[2*i+1], tree[2*i+2]);
}

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, 0);           // reduce the scale of range from [0,10^9] to [0,10^5]
    for(int i = 0; i < n; i++) {
        b[i] = v[i][1];
    }
    for(int i = 0; i < n; i++) {
        cin >> v[i][2];
    }

//     sort on 0th col in reverse order
    sort(v.begin(), v.end(), comp);
    sort(b.begin(), b.end());
    
    int ans = 0;
    for(int i = 0; i < n;) {
        int j = i;
        while(j < n &&  v[j][0] == v[i][0]) {    
            int B = v[j][1];
            int pos = lower_bound(b.begin(), b.end(), B) - b.begin(); // position of B in b[]
            int mx = get_max(0, 0, n - 1, pos + 1);
            if(mx > v[j][2])
                ans += 1;
            j++;
        }
        while(i < j) {
            int B = v[i][1];
            int C = v[i][2];
            int pos = lower_bound(b.begin(), b.end(), B) - b.begin(); // position of B in b[]
            update(0, 0, n - 1, pos, C);
            i++;
        }
    }
    return ans;
}

该解决方案使用段树，从而解决了时间O（n * log（n））和空间O（n）的问题。

方法在@Primusa接受的答案中进行了解释。