【每日一题】转换为求逆序对 树状数组

链接：https://ac.nowcoder.com/acm/problem/13947
n支队伍一共参加了三场比赛。
一支队伍x认为自己比另一支队伍y强当且仅当x在至少一场比赛中比y的排名高。
求有多少组(x,y)，使得x自己觉得比y强，y自己也觉得比x强。
(x, y), (y, x)算一组。

4
1 3 1
2 2 4
4 1 2
3 4 3
二元组满足条件当且仅当一场比赛x的排名高而另一场y的排名高。

方法1：

只考虑两场不就是求逆序对吗？
三场的话就
按比赛1排序：
即 1 2 4 3 （序号排名 真实值是 1 2 3 4）
3 2 4 1
1 4 3 2 ---逆序对 4,3 4,2（第一场是顺序的，即前面的排名高）
再按比赛2排序求比赛3的逆序
两个相加就是答案

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MYINTMAX 0x3f3f3f3f
#define N 200005
int tree[N];
int gn=0;
int gi=0;
inline int query(int pos){
    int ans=0;
    while(pos>0) {
        ans+=tree[pos];
        pos-=pos&(-pos);
    }
    return ans;
}
inline void update(int pos, int val){
    int ans = 0;
    while(pos<=gn){
        tree[pos]+=val;
        pos+=pos&(-pos);
    }
}

int cmp(const void *p1,const void*p2){
    if( ((int*)p1)[gi]!=((int*)p2)[gi])
        return ((int*)p1)[gi] - ((int*)p2)[gi];
}
int a[N][3];
int b[3][N];
ll solveForRever(int *a){
    ll res=0;
    memset(tree,0,sizeof(int)*(gn+1));
    for(int i=gn-1;i>=0;i--){
        res+=query(a[i]);
        update(a[i],1);
    }
    return res;
}
void copyNum(int level)
{ 
    for(int i=0;i<gn;++i){
        //cout<<a[i][level];
        b[level][i] = a[i][level];
    }
    return;
}
int main(void)
{
    int n;
    cin>>n;
    gn=n;
    for(int i = 0;i<n;++i){
        for(int j=0;j<3;++j){
            cin>>a[i][j];
        }
    }
    qsort(a,n,sizeof(int)*3,cmp);
    /*for(int i = 0;i<n;++i){
        for(int j=0;j<3;++j){
            cout<<a[i][j];
        }
         cout<<endl;
    }*/
    copyNum(1);
    copyNum(2);
    ll ans;
    ans = solveForRever(b[1]);
    ans+=solveForRever(b[2]);
    gi=1;
    qsort(a,n,sizeof(int)*3,cmp);
    copyNum(2);copyNum(0);
    ans+=solveForRever(b[2]);ans+=solveForRever(b[0]);
    gi=2;
    qsort(a,n,sizeof(int)*3,cmp);
    copyNum(1);copyNum(0);
    ans+=solveForRever(b[1]);ans+=solveForRever(b[0]);
    cout<<ans/4;
    return 0;
}

方法二：cbq分治

不符合的情况是一个三维偏序
主要思想就是先按照第一维排序。然后遍历每一个点，此时我们要统计的就是前面的点中比这个点的y坐标要小的点的个数。我们用一个树状数组来维护y坐标这个信息，于是就只要得到getsum(y)就行了。

三维的CDQ分治呢，做法如下：

第一维排序，第二维CDQ分治，第三维树状数组。

第一维比如先按照x坐标排序。在第二维的CDQ分治时，我们对每一个自区间，先按照y排序，计算左边对右边的影响的时候:

左边的x都小于右边

在每一边y也是依次递增的

我们只要扫描右边，把左边y小于等于当前的y坐标的z坐标更新到树状数组，统计目前树状数组z坐标小于自己的就是偏序<的点的个数。

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

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

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