记录编号	582511	评测结果	AAAAAAAAAA
题目名称	三元数对	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.014 s
提交时间	2023-09-16 21:08:07	内存使用	2.75 MiB

#include <bits/stdc++.h> 
using namespace std;
typedef long long ll;
const int N = 3e4+10;
int n,top;//top为离散化后数据 
ll c[N],r[N];
ll ans;
struct made{
	int id;
	ll d,x;
}a[N];
bool cmp1(made x,made y){
	return x.x < y.x;
}
bool cmp2(made x,made y){
	return x.id < y.id;
}//先离散化再返回 
void add(int x,ll z){
	while(x <= n+1){
		c[x] += z;
		x += x&-x;
	}
	return;
}
int ask(int x){
	ll ss = 0;
	while(x > 0){
		ss += c[x];
		x -= x&-x;
	}
	return ss;
}
int main(){
	freopen("three.in","r",stdin);
	freopen("three.out","w",stdout);
	scanf("%d",&n);
	for(int i = 1;i <= n;i++){
		scanf("%lld",&a[i].x);
		a[i].id = i;
	}
	sort(a+1,a+1+n,cmp1);
	for(int i = 1;i <= n;i++){
		if(a[i].x != a[i-1].x)top++;
		a[i].d = top;
	}//离散化 
	sort(a+1,a+1+n,cmp2);
	for(int i = n;i >= 1;i--){
		r[i] = ask(n-a[i].d);
		add(n-a[i].d+1,1);
	}
	memset(c,0,sizeof(c));
	for(int i = 1;i <= n;i++){
		ans += r[i] * ask(a[i].d-1);
		add(a[i].d,1);
	}//树状数组求两边逆序对 
	printf("%lld\n",ans);
	
	return 0;
	
}