【每日一题】【6月1日】Contest

题意：

支队伍一共参加了三场比赛。
一支队伍 认为自己比另一支队伍 强当且仅当 在至少一场比赛中比 的排名高。

求有多少组，使得 自己觉得比 强， 自己也觉得比 强。

算一组。

解法：

题目应该是有个没有显式声明的条件：一场比赛种不存在两支队伍排名相同。
如果加上这个条件，也能做，处理一下这种情况即可。

第一点：考虑符合要求的队伍 和 三场比赛的排名。
显然只有两种情况： 出现两次， 出现一次；或者 出现两次， 出现一次；
那么我们从中任取两场比赛，对满足 和 各出现一次的做统计，结果数即为 。那么最终答案就是 。

因为同一对满足条件的 ，两种情况都是重复统计一次。

第二点：考虑两场比赛，如何统计 和 各出现一次。
记第一场比赛排名为 ，第二场比赛排名为 。
我们先按 排序。
那么即求 。即 数组的逆序对数。
常见求逆序对的方法有归并排序，或树状数组。
代码实现用树状数组。
树状数组维护区间。
区间中每个点 ，对应值为 的个数。
对于 ，区间 之和，即为 的值的个数。
顺序遍历 ，区间 之和计入答案，再更新树状数组，将 对应的值加一。

Code：

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
using pii = pair<int, int>;
using ll = long long;
#define x first
#define y second
pii p[N];
int rnk[3][N], n, d[N];
void init() {
    memset(d, 0, sizeof d);
}
void add(int x, int v) {
    for(int i = x; i <= n; i += i & -i) d[i] += v;
}
int get(int x) {
    int res = 0;
    for(int i = x; i; i -= i & -i) res += d[i];
    return res;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++) for(int j = 0; j < 3; j++) cin >> rnk[j][i];
    ll ans = 0;
    for(int i = 0; i < 2; i++) {
        for(int j = i + 1; j < 3; j++) {
            for(int k = 1; k <= n; k++) p[k].x = rnk[i][k];
            for(int k = 1; k <= n; k++) p[k].y = rnk[j][k];
            sort(p + 1, p + n + 1);
            init();
            for(int k = 1; k <= n; k++) {
                ans += get(n) - get(p[k].y);
                add(p[k].y, 1);
            }
        }
    }
    cout << ans / 2 << endl;
}