【每日一题】contest 题解

Description

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

Solution

容斥思想, 不考虑任何限制，总共有 种组合
我们要求题目给的限制方案不好求，逆向思维求不符合的情况
显然不符合的情况是一个三维偏序
三维偏序问题可以用 cdq 分治去解决，这里就不赘述了
得到三维偏序的方案为
那么答案就是

#include<iostream>
#include<algorithm>

using namespace std;
struct node {
    int x, y, z;
    bool operator < (const node &s) {
        return x < s.x;
    }
}a[200005], b[200005];
long long p;
long long t[200005];
int lowbit(int x) {
    return x & (-x);
}

void add(int x, int y) {
    while(x < 200005) {
        t[x] += y;
        x += lowbit(x);
    }
}

long long sum(int x) {
    long long ans = 0;
    while(x) {
        ans += t[x];
        x -= lowbit(x);
    } 
    return ans;
}

void cdq(int l, int r) {
    if(l == r) return ;
    int mid = l + r >> 1;
    cdq(l, mid); cdq(mid + 1, r);
    int L = l, R = mid + 1, tot = l;
    while (L <= mid && R <= r) {
        if (a[L].y <= a[R].y) add(a[L].z, 1), b[tot++] = a[L++];
        else p -= sum(a[R].z), b[tot++] = a[R++];
    }
    while (L <= mid) {
        add(a[L].z, 1);
        b[tot++] = a[L++];
    }
    while (R <= r) {
      p -= sum(a[R].z);
        b[tot++] = a[R++];
    }
    for(int i = l; i <= mid; i++) add(a[i].z, -1);
    for(int i = l; i <= r; i++) a[i] = b[i];
}
int main() {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i].x >> a[i].y >> a[i].z;
    }
    p = 1LL * n * (n - 1) / 2;
    sort(a + 1, a + 1 + n);
    cdq(1, n);
    cout << p << "\n"; 
    return 0;
}