//i<j,a[i]>a[j].以第一场的排名进行排序,这样排序后i,j就表示第一场排名,a[i],a[j]就表示第二场排名 #include <bits/stdc++.h> using namespace std; const int maxn=2e5+7; typedef long long ll; struct node { int x,y; node(){} node(int x,int y):x(x),y(y){} bool operator<(const node o)const{ return x<o.x; } }s[maxn]; int n; int a[maxn],b[maxn],c[maxn]; ll C[maxn]; void add(int i,int val) { while(i<maxn) { C[i]+=val; i+=(i&(-1)); } } ll sum(int i) { ll ans=0; while(i) { ans+=C[i]; i-=(i&(-i)); } return ans; } ll solve() { memset(C,0,sizeof(C)); ll ans=0; for(int i=n-1;i>=0;i--) { add(s[i].y,1); ans+=sum(s[i].y-1); } return ans; } int main() { scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%d%d%d",&a[i],&b[i],&c[i]); } ll ans=0; //a,b for(int i=0;i<n;i++) { s[i]=node(a[i],b[i]); } sort(s,s+n); ans+=solve(); //a,c for(int i=0;i<n;i++) { s[i]=node(a[i],c[i]); } sort(s,s+n); ans+=solve(); //b,c for(int i=0;i<n;i++) { s[i]=node(b[i],c[i]); } sort(s,s+n); ans+=solve(); printf("%lld\n",ans/2); }
全部评论
(0) 回帖