洛谷 P5463 小鱼比可爱（加强版）（树状数组）

传送门

---

解题思路

逆序对升级版。
考虑每个逆序对对答案的贡献为多少。
假设这个逆序对的坐标为(i,j)，则显然有i(n-j+1)个区间包含这个逆序对，所以对答案的贡献就是i(n-j+1)。
和以前一样用树状数组求逆序对，需要改动的地方是新加的节点不再是+1，而是+i。
估计ans最大可能在n^4左右，会炸long long，所以写个高精乘低精即可。

AC代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1e6+5;
long long d[maxn],ans[50]={1};
int n,m,a[maxn],c[maxn];
inline int lowbit(int x){
	return x&(-x);
}
void add(int x,long long v){
	for(int i=x;i<=m;i+=lowbit(i)){
		d[i]+=v;
	}
}
long long query(int x){
	long long res=0;
	for(int i=x;i>=1;i-=lowbit(i)){
		res+=d[i];
	}
	return res;
}
void jia(long long x){
	ans[1]+=x;
	for(int i=1;i<ans[0];i++){
		ans[i+1]+=ans[i]/10;
		ans[i]%=10;
	}
	while(ans[ans[0]]>10){
		ans[ans[0]+1]+=ans[ans[0]]/10;
		ans[ans[0]]%=10;
		ans[0]++;
	}
}
void print(){
	for(int i=ans[0];i>=1;i--) cout<<ans[i];
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		c[i]=a[i];
	}
	sort(c+1,c+n+1);
	m=unique(c+1,c+n+1)-c-1;
	for(int i=1;i<=n;i++){
		a[i]=lower_bound(c+1,c+m+1,a[i])-c;
		jia(1ll*(n-i+1)*(query(m)-query(a[i])));
		add(a[i],i);
	}
	print();
	return 0;
}