题目描述 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> using namespace std; #define N 100010 int n; struct node{ int l,r; long long v; }tr[40010<<4]; void build(int k,int l,int r){ tr[k].l=l;tr[k].r=r; if(tr[k].l==tr[k].r)return; int mid=(l+r)>>1; build(k<<1,l,mid);build(k<<1|1,mid+1,r); } long long query(int k,int l,int r){ if(tr[k].l>=l&&tr[k].r<=r)return tr[k].v; int mid=(tr[k].l+tr[k].r)>>1; long long res=0; if(l<=mid)res+=query(k<<1,l,r); if(r>mid)res+=query(k<<1|1,l,r); return res; } void Insert(int k,int l){ if(tr[k].l==l&&tr[k].r==tr[k].l){ tr[k].v++; return; } int mid=(tr[k].l+tr[k].r)>>1; if(l<=mid)Insert(k<<1,l); if(l>mid) Insert(k<<1|1,l); tr[k].v=tr[k<<1].v+tr[k<<1|1].v; } int main(){ scanf("%d",&n); build(1,1,N); int x; long long ans=0; for(int i=1;i<=n;i++){ scanf("%d",&x); ans+=query(1,x+1,N); Insert(1,x); } cout<<ans; return 0; }