C++(clang++ 11.0.1) 解法, 执行用时: 123ms, 内存消耗: 9868K, 提交时间: 2022-07-29 14:08:35

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5;
#define pii pair<ll,ll>
ll a[4][N+5];
ll n,all,tree[N+5];
pii p[N+5];
void update(ll x)
{
	for(;x<=n;x+=x&-x) tree[x]++;
}
ll get_num(int x)
{
	ll ans=0;
	for(;x;x-=x&-x) ans+=tree[x];
	return ans;
}
int main()
{
	scanf("%lld",&n);
	for(ll i=1;i<=n;i++)
	scanf("%lld%lld%lld",&a[1][i],&a[2][i],&a[3][i]);
	for(ll i=1;i<3;i++)
	for(ll j=i+1;j<=3;j++)
	{
		memset(tree,0,sizeof(tree));
		for(ll k=1;k<=n;k++)
		p[k].first=a[i][k],p[k].second=a[j][k];
		sort(p+1,p+n+1);
		for(ll k=1;k<=n;k++)
		{
			update(p[k].second);
			all+=k-get_num(p[k].second);
		}
	}
	printf("%lld\n",all/2);
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 133ms, 内存消耗: 9060K, 提交时间: 2019-07-19 14:46:23

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
typedef long long ll;
ll ans=0;
int n;
int a[maxn],b[maxn],c[maxn];
ll tr[maxn];
int A[maxn],B[maxn];
void updata(int x,int val)
{
	while(x<=n)
	{
		tr[x]+=val;
		x+=x&-x;
	}
}
ll query(int x)
{
	ll rec=0;
	while(x)
	{
		rec+=tr[x];
		x-=x&-x;
	}
	return rec;
}
ll mer(int x[],int y[])
{
	for(int i=1;i<=n;i++)
		A[x[i]]=y[i];
	memset(tr,0,sizeof(tr));
	ll rec=0;
	for(int i=1;i<=n;i++)
	{
		rec+=(i-1-query(A[i]));
		updata(A[i],1);
	}
	return rec;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d%d%d",&a[i],&b[i],&c[i]);
	ans+=mer(a,b)+mer(b,c)+mer(a,c);
	printf("%lld\n",ans/2);
}

pypy3 解法, 执行用时: 1401ms, 内存消耗: 81524K, 提交时间: 2021-06-08 18:55:57

def fen_update(tree, i, delta):
	while i < len(tree): tree[i] += delta; i |= i + 1
def fen_get(tree, i):
	sum = 0
	while i > 0: sum += tree[i - 1]; i &= i - 1
	return sum

n = int(input())
a = [[0] * 3 for _ in range(n)]
s = [[0] * 3 for _ in range(n)]
for i in range(n):
	x, y, z = map(int, input().split())
	a[i][0] = x - 1; a[i][1] = y - 1; a[i][2] = z - 1
	s[x - 1][0] = i; s[y - 1][1] = i; s[z - 1][2] = i
ans = 0
for k in range(3):
	t, j = [0] * n, (k + 1) % 3
	for i in range(n - 1, -1, -1):
		ans += fen_get(t, a[s[i][k]][j])
		fen_update(t, a[s[i][k]][j], 1)

print(ans // 2)