https://ac.nowcoder.com/acm/problem/13947（牛客网）

Contest：
链接：https://ac.nowcoder.com/acm/problem/13947
来源：牛客网

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

输入描述:
第一行一个整数n，表示队伍数； 接下来n行，每行三个整数a[i], b[i], c[i]，分别表示i在第一场、第二场和第三场比赛中的名次；n 最大不超过200000
输出描述:
输出一个整数表示满足条件的(x,y)数；64bit请用lld

题解：
题目应该是有个没有显式声明的条件：一场比赛种不存在两支队伍排名相同。
如果加上这个条件，也能做，处理一下这种情况即可。

第一点：考虑符合要求的队伍 和 三场比赛的排名。
显然只有两种情况： 出现两次， 出现一次；或者 出现两次， 出现一次；
那么我们从中任取两场比赛，对满足 和 各出现一次的做统计，结果数即为 。那么最终答案就是 。

因为同一对满足条件的 ，两种情况都是重复统计一次。

第二点：考虑两场比赛，如何统计 和 各出现一次。
记第一场比赛排名为 ，第二场比赛排名为 。
我们先按 排序。
那么即求 。即 数组的逆序对数。
常见求逆序对的方法有归并排序，或树状数组。
代码实现用树状数组。
树状数组维护区间。
区间中每个点 ，对应值为 的个数。
对于 ，区间 之和，即为 的值的个数。
顺序遍历 ，区间 之和计入答案，再更新树状数组，将 对应的值加一。

#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int maxn=2e5+10;
const LL mod=1e9+7;
const double pi=acos(-1.0);
inline LL read()
{
	LL X=0; bool flag=1; char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
	while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
	if(flag) return X;
	return ~(X-1);
}
LL n;
LL c[maxn];
LL a[maxn][3];
pair<LL,LL>  p[maxn];
void add(LL x,LL d)
{
    while(x<=n){
        c[x]+=d;
        x+=(x&(-x));
    }
}
LL query(LL x)
{
    LL ans=0;
    while(x>0){
        ans+=c[x];
        x-=(x&(-x));
    }
    return ans;
}
int main()
{
    scanf("%lld",&n);
    for(LL i=1;i<=n;i++){
        scanf("%lld%lld%lld",&a[i][0],&a[i][1],&a[i][2]);
    }
    LL res=0;
    for(LL i=0;i<3;i++){
        for(LL j=i+1;j<3;j++){
            for(LL k=1;k<=n;k++){
                p[k].first=a[k][i];p[k].second=a[k][j];
            }
            sort(p+1,p+1+n);
            memset(c,0,sizeof(c));
            /*for(LL k=1;k<=n;k++){
                printf("%lld %lld\n",p[k].first,p[k].second);
            }
            printf("----\n");*/
            for(LL k=1;k<=n;k++){
                res+=(query(n)-query(p[k].second));
                add(p[k].second,1);
            }
        }
    }
    printf("%lld\n",res/2);
    return 0;
}