contest

题意：
有n支队伍参加n3场比赛，一支队伍x认为自己比另一支队伍y强当且仅当x在至少一场比赛中比y的排名高，也就是互相赢过对方，这样算一组（x,y），试问存在多少组？

分析：
我们首先想到的思路是将第一场比赛进行排序，保证i自认为比i+1强，然后寻找后面比赛存在多少组j比j+1强，这样暴力下来复杂度要O（n^2），常熟还很大，显然会TLE,那么我们想一想怎么优化这种暴力。
我们先从总情况上考虑，符合队伍的x，y三场比赛后可能两种情况：rankx>ranky2次或者是rankx<ranky2次，那么我们统计这些情况出现的次数cnt，因为满足情况的（x,y）两种情况都会统计一次，存在重复，所以最终答案应为cnt/2。
而统计上述情况，我们可以由2场比赛进行考虑，设第一场比赛用a表示，第二场比赛用b表示，我们首先按a进行正序排序，那么问题就变成求b组j>i且bi>bj出现数量，也就是求b组的逆序对。
对于逆序对问题，方法有归并排序，树状数组和线段树。
线段树写bug修不过来，所以参考了一下大佬的树状数组作法（树状数组真的比线段树好看一万倍）
具体实现：
每次构建一个值的范围是1~n的BIT，按照j = 0，1，2，3···，n-1的顺序进行如下操作。
1、BIT t[j] 位置加上 1
2、res += j - query(t[i])
对于目标数组b，区间[bi+1,n]之和，即为>bi值的个数，最后遍历统计即可，记得除2。
最后提醒一下，如果通过率45%，记得开longlong!

代码：

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
using namespace std;
typedef long long ll;
int i,j,n,k,tt,m;
ll cnt,ans;
int ran[3][200003],t[200003];
struct Hi{
    int x,y;
}a[200003];
int cmp(Hi A,Hi B){
    if(A.x==B.x)    return A.y<B.y;
    return A.x<B.x;
}
void add(int x, int v) {
    for(int i = x; i <= n; i += i & -i) t[i] += v;
}
int get(int x) {
    int res = 0;
    for(int i = x; i; i -= i & -i) res += t[i];
    return res;
}
using namespace std;
int main()
{
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        for(j=0;j<3;j++){
            scanf("%d",&ran[j][i]);
        }
    }
    for(int i=0;i<2;i++){
        for(int j=i+1;j<3;j++){
            for(k=1;k<=n;k++){
                a[k].x=ran[i][k];
                a[k].y=ran[j][k];
            }    
            sort(a+1,a+1+n,cmp);//先排序第一组
            memset(t,0,sizeof(t));
            for(int k=1;k<=n;k++){//求逆序对数
                ans+=get(n)-get(a[k].y);//得到之前有多少个比你大的数（逆序对）
                add(a[k].y,1);//下标等效与数值,该位置加上1
            }
        }
    }
    printf("%lld\n",ans/2);//答案有重复要除2
}