Contest

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

思路：当x自己觉得比y强，y自己也觉得比x强，只有这二种情况，第一种是x二场比y弱，一场比y强，第二种是x二场比y强，一场比y弱。无论哪一种都会产生二组逆序对，所以我们对第一场降序排序，对第二和第三场求逆序对(既已遍历中比当前值小的数目，可以树状数组维护，遍历一个，对值位置加一)，再对第二场排序，对第三场对逆序对（同理）。最终对答案除二即可。

代码：

#include<bits/stdc++.h>
#define ll long long
#define inf 1024523

using namespace std;

inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

int n, b[500005], c[500005];
struct w
{
    int x, y, z;
} w[200005];

bool cmp(struct w a,struct w b)
{
    return a.x>b.x;
}

bool cmp1(struct w a,struct w b)
{
    return a.y>b.y;
}

ll z=0;

void add(int x,int k)
{
    while(x<=n)
    {
        b[x]+=k;
        x+=(x&(-x));
    }
}

ll sum(int x)
{
    ll s=0;
    while(x>0)
    {
        s=s+b[x];
        x-=(x&(-x));
    }
    return s;
}

void add1(int x,int k)
{
    while(x<=n)
    {
        c[x]+=k;
        x+=(x&(-x));
    }
}

ll sum1(int x)
{
    ll s=0;
    while(x>0)
    {
        s=s+c[x];
        x-=(x&(-x));
    }
    return s;
}

int main()
{
    scanf("%d",&n);
    for(int i=0; i<n; i++)
    {
        scanf("%d%d%d",&w[i].x,&w[i].y,&w[i].z);
    }
    sort(w,w+n,cmp);
    memset(b,0,sizeof(b));
    memset(c,0,sizeof(c));
    for(int i=0; i<n; i++)
    {
        z+=sum(w[i].y);
        add(w[i].y,1);
        z+=sum1(w[i].z);
        add1(w[i].z,1);
    }
    memset(c,0,sizeof(c));
    sort(w,w+n,cmp1);
    for(int i=0; i<n; i++)
    {
        z+=sum1(w[i].z);
        add1(w[i].z,1);
    }
    cout << z/2 << endl;
    return 0;
}