Contest

树状数组+排序

A比B的一场排名高，并且B也有一场的排名比A高
那么对第一场排序后，就保证了后面的排名比前面的排名高，这样只需要统计有多少个数对(a[i],a[j]) 满足 i<j && a[i]>a[j] 这不就是求逆序数对吗。
所以我们对任意两场求逆序数对即可。
以第一场排序后，求相对于第一场而言，第二场的逆序数对(即求出第一场、第二场之间的满足的)，第三场的逆序数对(即求出第一场、第三场之间的满足的)
然后在以第二场排序，求相对于第二场而言，第三场的逆序数对(即求出第二场、第三场之间的满足的)
最后的结果要除以2，为什么？假设存在一组逆序数对，假设A的第一场比B的第一场高，A的第二场比B的第二场低，这已经满足了，考虑第三组的高低情况，因为排名不会一样，所以对于满足的而言，必定是一个队伍比另一个队伍两高一低/一高两低的情况，这样就重复计算了一次。
比如
2
1 2 2
2 1 1
容易得到第一场排序后，第二场的逆序数对有1，第三场的逆序数对有1，
第二场排序后，第三场的逆序数对为0.
但是答案是1，并不是1+1+0=2

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+5;
struct node{int a,b,c;}q[maxn];
int c[maxn];
void add(int x){
    for(;x<maxn;x+=x&(-x)) c[x]++;
}
ll get_sum(int x){
    ll sum=0;
    for(;x;x-=x&(-x)) sum+=c[x];
    return sum;
}
int main(){
    //ios::sync_with_stdio(0);
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d%d%d",&q[i].a,&q[i].b,&q[i].c);
    sort(q+1,q+1+n,[](node a,node b){
       return a.a<b.a; 
    });
    ll sum=0;
    for(int i=1;i<=n;i++) add(q[i].b),sum+=i-get_sum(q[i].b);
    memset(c,0,sizeof c);
    for(int i=1;i<=n;i++) add(q[i].c),sum+=i-get_sum(q[i].c);
    memset(c,0,sizeof c);
    sort(q+1,q+1+n,[](node a,node b){
           return a.b<b.b; 
    });
    for(int i=1;i<=n;i++) add(q[i].c),sum+=i-get_sum(q[i].c);
    printf("%lld",sum/2);
    return 0;
}