【每日一题】Contest

题目描述
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>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define lowbit(x) x&(-x)

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;

const int N = 2e5+5;
const ll mod = 1e9+7;
const int INF = 0x3f3f3f3f;
const double eps =1e-9;
const double PI=acos(-1.0);
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
const int exdir[4][2]={1,1,1,-1,-1,1,-1,-1};

ll qpow(ll x,ll y){
    ll ans=1,t=x;
    while(y>0){
        if(y&1)ans*=t,ans%=mod;
        t*=t,t%=mod;
        y>>=1;
    }
    return ans%mod;
}

struct node{
    int a,b,c;
}a[N];
int tree[N],n;

bool cmp1(node a,node b){
    return a.a<b.a;
}
bool cmp2(node a,node b){
    return a.b<b.b;
}

void add(int x){
    while(x<=n){tree[x]+=1;x+=lowbit(x);}
}
int sum(int x){
    int ans = 0;
    while(x>0){ans+=tree[x];x-=lowbit(x);}
    return ans;
}
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i].a>>a[i].b>>a[i].c;
    ll ans=0;
    sort(a+1,a+n+1,cmp1);
    for(int i=1;i<=n;i++){
        ans+= sum(n)-sum(a[i].b);
        add(a[i].b);
    }
    memset(tree,0,sizeof(tree));
    for(int i=1;i<=n;i++){
        ans +=sum(n)-sum(a[i].c);
        add(a[i].c);
    }
    memset(tree,0,sizeof(tree));
    sort(a+1,a+n+1,cmp2);
    for(int i=1;i<=n;i++){
        ans += sum(n)-sum(a[i].c);
        add(a[i].c);
    }
    cout<<ans/2;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    //int t;cin>>t;
    //while(t--)solve(),cout<<'\n';
    solve();
    return 0;
}