求有多少玩家不能赢得比赛？

Question

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

如果存在另一个玩家 j 的所有 3 个值 A[j] > A[i]，则玩家 i 无法获胜， B[j] > B[i] 和 C[j] > C[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

What would be optimal way to solve this problem?

解法：

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

This solution uses segment tree, and thus solves the problem in time O(n*log(n)) and space O(n).

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

Answer 1

首先假设我们的输入以元组列表的形式出现T = [(A[0], B[0], C[0]), (A[1], B[1], C[1]) ... (A[N - 1], B[N - 1], C[N - 1])]

我们可以做的第一个观察是我们可以对 T[0] 进行排序（以相反的顺序）。然后对于每个元组(a, b, c)，为了确定它是否不能获胜，我们询问我们是否已经看到一个元组(d, e, f)使得e > b && f > c。我们不需要检查第一个元素，因为我们得到了 d > a* 因为 T 是反向排序的。

好的，现在我们如何检查第二个条件？

我们可以这样重构它：在我们已经用 e > b 看到的所有元组 (d, e, f) 中，f 的最大值是多少？如果最大值大于c，那么我们就知道这个元组不能获胜。

为了处理这部分，我们可以使用具有最大更新和最大范围查询的线段树。当我们遇到一个元组(d, e, f)，我们可以设置tree[e] = max(tree[e], f)。 tree[i] 代表第三个元素，i 代表第二个元素。

为了回答诸如“f 的最大值是多少，使得 e > b”这样的查询，我们做 max(tree[b+1...])，以获得可能范围内的最大第三个元素第二个元素。

由于我们只进行后缀查询，您可以使用修改后的芬威克树，但用线段树更容易解释。

这将为我们提供一个 O(NlogN) 解决方案，用于排序 T 并使用我们的线段树对每个元组进行 O(logN) 处理。

*注意：这实际上应该是 d >= a。然而，当我们假装一切都是独一无二的时，更容易解释算法。为容纳第一个元素的重复值而需要进行的唯一修改是在具有相同值的元组桶中处理查询和更新。这意味着我们将对具有相同第一个元素的所有元组执行我们的检查，然后我们才更新 tree[e] = max(tree[e], f) 对我们执行检查的所有这些元组。这确保当另一个元组正在查询树时，没有具有相同第一个值的元组已经更新了树。

求有多少玩家不能赢得比赛？

Find the number of players cannot win the game?

algorithm

math

data-structures

fenwick-tree