对于给定的一段正整数序列，逆序对就是序列中ai>aj且i<j的有序对。
求这段正整数序列中逆序对的数目。
Input
第一行，一个数n，表示序列中有n个数。N<=5*10^5
第二行n个数，表示给定的序列。序列中每个数字不超过10^9
Output
给定序列中逆序对的数目。
Sample Input
6
5 4 2 6 3 1
Sample Output
11
#include<bits/stdc++.h>
using namespace std;
long long a[500005],ans,n;
struct MM
{
long long ii,num;
}b[500005];
struct MMM
{
long long l,r,sum;
}tree[2000005];
bool cmp(MM x,MM y)
{
return x.num<y.num;
}
void build(long long root,long long L,long long R)
{
tree[root].l=L;
tree[root].r=R;
if(tree[root].l==tree[root].r)
return;
long long mid=(L+R)>>1;
build(root<<1,L,mid);
build(root<<1|1,mid+1,R);
return;
}
void updata(long long root,long long v)
{
if(tree[root].l==tree[root].r)
{
tree[root].sum++;
return;
}
long long mid=(tree[root].l+tree[root].r)>>1;
if(v<=mid)
updata(root<<1,v);
else
updata(root<<1|1,v);
tree[root].sum=tree[root<<1].sum+tree[root<<1|1].sum;
return;
}
long long query(long long root,long long x)
{
if(tree[root].l==tree[root].r)
return tree[root].sum;
long long mid=(tree[root].l+tree[root].r)>>1;
if(x<=mid)
return query(root<<1,x)+tree[root<<1|1].sum;
return query(root<<1|1,x);
}
int main()
{
cin>>n;
for(long long i=1;i<=n;i++)//这里离散化开始
{
cin>>a[i];
b[i].num=a[i];
b[i].ii=i;
}
sort(b+1,b+n+1,cmp);
for(long long i=1,j=0;i<=n;i++)
{
if(b[i].num!=b[i-1].num||i==1) j++;
a[b[i].ii]=j; //a[i]=j，输入的第i个数字排序后第j小
}
build(1,1,n);
for(long long i=1;i<=n;i++)
{
ans+=query(1,a[i]+1);
//query查询在线段树中>=a[i]+1数字，出现了多少次
updata(1,a[i]);//在权值线段树中,将a[i]这个数字出现的次数加1
}
cout<<ans<<endl;
return 0;
}
原文：https://www.cnblogs.com/cutemush/p/11788999.html