【每日一题】contest

题意

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

solution

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

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