Contest

一开始想的是排序三次 每次求两次逆序对 感觉有点复杂了 看了别人的做法 确实更优
将三次比赛的排名分别记为x, y, z 那么我可以将x作为下标 y作为值 去求这样一个数组的逆序对 这就相当于我的x按顺序排好了 那么我只要y是逆序的 那么就是我的x比你小 y比你大
注意 这样就只需要求三次 因为a[x] = y和a[y] = x 是等价的

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 10;
int a[N], b[N], c[N], tmp[N];
int n;

ll merge_sort(int a[], int l, int r) {
  if (l >= r) return 0;
  int mid = (l + r) >> 1;
  ll cnt = merge_sort(a, l, mid) + merge_sort(a, mid + 1, r);
  int k = 0, i = l, j = mid + 1;
  while (i <= mid && j <= r) {
    if (a[i] <= a[j]) tmp[k ++] = a[i ++];
    else {
      tmp[k ++] = a[j ++];
      cnt += mid - i + 1;
    }
  }
  while (i <= mid) tmp[k ++] = a[i ++];
  while (j <= r) tmp[k ++] = a[j ++];
  for (i = l, j = 0;i <= r; ++ i, ++ j) a[i] = tmp[j];
  return cnt;
}

int main () {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n;
  for (int i = 1;i <= n; ++ i) {
    int x, y, z;cin >> x >> y >> z;
    a[x] = y;
    b[y] = z;
    c[z] = x;
  }  
  ll res1 = merge_sort(a, 1, n);
  ll res2 = merge_sort(b, 1, n);
  ll res3 = merge_sort(c, 1, n);
  /*
  如果我的x z比你的大 y比你小 那么我会计算两次 这就重复了
  故除以2
  详细说一下 其实就是要么不存在逆序关系 要么就存在两对逆序关系
  这是因为排名不能重复
  如果全部比你小或者全部比你大 这就没有逆序关系
  如果一项比你大或者两项比你大 这就是两对逆序关系
  但是题目中给了(x, y)和(y, x)视作一对
  那么这相当于我重复计数了 则最终答案要/=2
  */
  cout << (res1 + res2 + res3) / 2 << '\n';
}