珂朵莉的数列

题目描述
珂朵莉给了你一个序列，有n×(n+1)/2个子区间，求出她们各自的逆序对个数，然后加起来输出
输入描述:
第一行一个数 n 表示这个序列 a 的长度

之后一行 n 个数，第i个数表示ai

输出描述:
输出一行一个数表示答案

示例1
输入

10
1 10 8 5 6 2 3 9 4 7
输出

270

示例2
输入

20
6 0 4 5 8 8 0 6 6 1 0 4 6 6 0 0 7 2 0 5
输出

3481

备注:
对于100%的数据，n <=
1000000 ,0 <= 序列中每个数 <= 1000000000

比较经典的从贡献值分析问题，我们分析每一对逆序对产生的贡献值，如果当前的逆序对为 [l,r]，那么存在于多少个子区间当中呢？l * ( n - r + 1) 个子区间当中，排列组合一下即可。

那么我们可以用树状数组去维护逆序对，每次插入数字时，位置为当前数字离散化之后的位置，权值为当前数字前面有个数字。

然后每次统计答案时直接，比当前数字大的总权值和即可。（可以自己思考一下）。

然后这道题会爆long long，所以我们需要用两个数字存答案（即把数字当成1e18进制的数字即可）。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
#define lowbit(x) (x&(-x))
using namespace std;
const int N=1e6+10,p=1e18;
int res1,res2,n,d[N],a[N],cnt;
vector<int> v;
inline int get(int x){
	return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}
inline void add(int x,int v){
	for(int i=x;i<=n;i+=lowbit(i))	d[i]+=v;
}
inline int ask(int x){
	int res=0; for(int i=x;i;i-=lowbit(i))	res+=d[i];	return res;
}
signed main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)	scanf("%lld",&a[i]),v.push_back(a[i]);
	sort(v.begin(),v.end());	v.erase(unique(v.begin(),v.end()),v.end());
	for(int i=1;i<=n;i++){
		add(get(a[i]),i);	res1+=(n-i+1)*(ask(v.size())-ask(get(a[i])));
		if(res1>p){
			res2+=res1/p;	res1%=p;
		}
	}
	if(res2)	printf("%lld%018lld\n",res2,res1);
	else	printf("%lld\n",res1);
	return 0;
}