时间限制：1秒 空间限制：131072K
题目描述
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 <cstdio> #include <iostream> #include <cstring> #include <map> #include <algorithm> using namespace std; typedef long long ll; const int MAXN=200010; int c[MAXN]; int n; int a[MAXN]; int cnt; struct node2 { int x; int y; int z; }peo[200100]; struct node { int id; ll num; }r[MAXN]; int cmp(node x,node y) { if(x.num!=y.num) return x.num<y.num; else return x.id<y.id; } int lowbit(int x) { return x&(-x); } void add(int i,int value) { while(i<=n) { c[i]+=value; i+=lowbit(i); } } int sum(int i) { int sum=0; while(i>=1) { sum+=c[i]; i-=lowbit(i); } return sum; } int main() { int t,i,tmp; ll ans; ans=0; while(scanf("%d",&n)!=EOF){ for(int i=1;i<=n;i++) { scanf("%d%d%d",&peo[i].x,&peo[i].y,&peo[i].z); } memset(c,0,sizeof(c)); memset(r,0,sizeof(r)); for(i=1;i<=n;i++) { r[i].num=peo[i].y; r[i].id=peo[i].x; } sort(r+1,r+n+1,cmp); for(int j=1;j<=n;j++) { add(r[j].id,1); ans+=j-sum(r[j].id); } memset(c,0,sizeof(c)); for(i=1;i<=n;i++) { r[i].num=peo[i].z; r[i].id=peo[i].x; } sort(r+1,r+n+1,cmp); for(int j=1;j<=n;j++) { add(r[j].id,1); ans+=j-sum(r[j].id); } memset(c,0,sizeof(c)); for(i=1;i<=n;i++) { r[i].num=peo[i].z; r[i].id=peo[i].y; } sort(r+1,r+n+1,cmp); for(int j=1;j<=n;j++) { add(r[j].id,1); ans+=j-sum(r[j].id); } printf("%lld ",ans/2); } return 0; }