树状数组求逆序数

解题思路 : 每场比赛的名次唯一的,当两个人依次比较每一场的名次时只可能有两种情况出现 “两大一小”或者“两小一大”， 所以求出的（a,b） (b,c) (a,c) 的逆序数总和是答案的两倍

#include <iostream>
#include <cstring>

using namespace std;

#define int long long

const int N = 2e5 + 10;

int a[N],b[N],c[N],tr[N],n;

void add(int pos , int x)
{
    for(int i = pos ; i <= n ; i += i & -i ) tr[i] += x;
}

int sum(int pos)
{
    int res = 0;
    for(int i = pos ; i ; i -= i & -i ) res += tr[i];
    
    return res;
}


int solve(int a[] , int b[])
{
    memset(tr , 0 , sizeof tr);
    int t[N];
    int res = 0;
    for(int i = 1 ; i <= n ; i ++ ) t[a[i]] = b[i];  //让a[i] 成为b[i]的下标
    
    for(int i = 1 ; i <= n ; i ++ ) // 顺序遍历下标 即实现第一维a单调递增
    {
        res += sum(n) - sum(t[i]); // 找到当前数组数组里面 t[i] + 1 ~ n 有多少个数， 即t[i]前面有几个大于t[i]的数
        add(t[i] , 1); // 将新的b插入树状数组中
    }
    
    return res;
}

signed main()
{
    cin >> n;
    for(int i = 1 ; i <= n ; i ++)
        cin >> a[i] >> b[i] >> c[i];
    
    int res = solve(a,b) + solve(a,c) + solve(b,c); 
    cout << res / 2;
}