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

Question

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

如果存在另一个玩家 j 并且所有 3 个值都是 A[j] > A[i], B[j] > B[i，则玩家 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 是第二个元素。

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

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

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

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