题目链接：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
题解
我们知道这里是求三次逆序对，先把第一场比赛的排名作序号，跟第二场比赛排名求逆序对的数量，再把第一场和第三场一起求，然后把第二场和第三场一起求这样会产生一些重复的，我们知道，如果两只队伍被计入逆序对，那么必有一只队伍排名高一场，则另一只队伍排名必高两场，比如x1<y1,x2>y2,x3>y3,那么就会有两组逆序对，所以要除以二（这一点仔细理解琢磨一下）
详情看代码：
#include<bits/stdc++.h> #include<cstdio> #define ll long long const int MMAX=2e5+5; int a[MMAX],b[MMAX],c[MMAX]; int te[MMAX],n; ll ans=0; void sor(int l1,int r1,int l2,int r2) { int temp[MMAX]; int i=l1,j=l2,re=0; while(i<=r1&&j<=r2) { if(te[i]<te[j]) temp[++re]=te[i++]; else{ ans=ans+r1-i+1; temp[++re]=te[j++]; } } while(i<=r1) temp[++re]=te[i++]; while(j<=r2) temp[++re]=te[j++]; for(int i=1;i<=re;i++) te[i+l1-1]=temp[i]; } void get_sort(int l,int r) { int mid=(l+r)/2; if(mid!=l) get_sort(l,mid); if(r!=mid+1) get_sort(mid+1,r); sor(l,mid,mid+1,r); } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d%d%d",&a[i],&b[i],&c[i]); for(int i=1;i<=n;i++) te[a[i]]=b[i]; ///求（1,2）的逆序对 get_sort(1,n); for(int i=1;i<=n;i++) te[a[i]]=c[i]; ///求（1,3）的逆序对 get_sort(1,n); for(int i=1;i<=n;i++) te[b[i]]=c[i]; ///求（2,3）的逆序对 get_sort(1,n); printf("%lld\n",ans/2); return 0; }
原文：https://www.cnblogs.com/lhhhhh/p/13861146.html