题目描述 Description
给定一个序列a1,a2,…,an，如果存在i<j并且ai>aj，那么我们称之为逆序对，求逆序对的数目
数据范围：N<=105。Ai<=105。时间限制为1s。
输入描述 Input Description
第一行为n,表示序列长度，接下来的n行，第i+1行表示序列中的第i个数。
输出描述 Output Description
所有逆序对总数.
样例输入 Sample Input
4
3
2
3
2
样例输出 Sample Output
3
/*
权值线段树模板
首先我们更改线段树叶子节点处存储的内容，将其更改为权值，并且记录对于一个权值x的个数。
那么我们首先构建一棵空树，
对于每次插入的数字x，我们查找x+1到max区间的数字存在的个数，并将这个个数加入答案，
然后插入这个数字。最后输出答案就可以了。。
*/
#include<iostream>
#include<cstdio>
#include<cstring> #define N 200007 using namespace std;
int n,x;
long long ans;
struct tree
{
int l,r;
long long sum;
}tr[N<<]; void push_up(int now)
{
tr[now].sum=tr[now<<].sum+tr[now<<|].sum;
} void build(int now,int l,int r)
{
tr[now].l=l;tr[now].r=r;
if(l==r) return;
int mid=(tr[now].l+tr[now].r)>>;
build(now<<,l,mid);build(now<<|,mid+,r);
} void insert(int now,int k)
{
if(tr[now].l==k && tr[now].l==tr[now].r)
{
tr[now].sum++;
return;
}
int mid=(tr[now].l+tr[now].r)>>;
if(x>mid) insert(now<<|,k);
if(x<=mid) insert(now<<,k);
push_up(now);
} long long gets(int now,int l,int r)
{
if(tr[now].l>r||tr[now].r<l) return ;
if(tr[now].l==l&&tr[now].r==r)
return tr[now].sum;
int mid=(tr[now].l+tr[now].r)>>;
if(l>mid) return gets(now<<|,l,r);
else if(r<=mid) return gets(now<<,l,r);
else return gets(now<<,l,mid)+gets(now<<|,mid+,r);
} int main()
{
scanf("%d",&n);
build(,,N);ans=;
for(int i=;i<=n;i++)
{
scanf("%d",&x);
ans+=gets(,x+,N);
insert(,x);
}
printf("%lld\n",ans);
return ;
}