每日一题：Contest （树状数组）

题意

$n$ 支队伍一共参加了三场比赛。
一支队伍 $x$ 认为自己比另一支队伍 $y$ 强当且仅当 $x$ 在至少一场比赛中比 $y$ 的排名高。
求有多少组 $(x,y)$，使得 $x$ 自己觉得比 $y$ 强，$y$ 自己也觉得比 $x$ 强，$(x, y)$, $(y, x)$算一组。

solution

若 $x$ 和 $y$ 都互相认为更强，那么必定存在两场，一场 $x$ 强于 $y$，一场 $y$ 强于 $x$，那么就是对于任意两场求逆序数，最后的答案需要除以2，因为如果两队互认为更强，必定存在 $x$ 有两场更强，或者 $y$ 有两场更强，那么计算逆序数时就多计算了一次。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 2e5 + 5;
ll n, res, t[N];

struct Node {
  ll a, b, c;
} q[N];

bool cmpa(Node x, Node y) { return x.a < y.a; }
bool cmpb(Node x, Node y) { return x.b < y.b; }

void add(ll x) {
  while (x <= n) {
    t[x]++;
    x += x & -x;
  }
}

ll query(ll x) {
  ll sum = 0;
  while (x) {
    sum += t[x];
    x -= x & -x;
  }
  return sum;
}

int main() {
  cin >> n;
  for (ll i = 1; i <= n; i++) cin >> q[i].a >> q[i].b >> q[i].c;
  sort(q + 1, q + n + 1, cmpa);
  for (ll i = 1; i <= n; i++) {
    add(q[i].b);
    res += i - query(q[i].b);
  }
  memset(t, 0, sizeof(t));
  for (ll i = 1; i <= n; i++) {
    add(q[i].c);
    res += i - query(q[i].c);
  }
  sort(q + 1, q + n + 1, cmpb);
  memset(t, 0, sizeof(t));
  for (ll i = 1; i <= n; i++) {
    add(q[i].c);
    res += i - query(q[i].c);
  }
  cout << res / 2 << '\n';
  return 0;
}