给定一个序列a1,a2,a3,a4...,an ，如果存在i<j 并且 ai > aj那么我们称之为逆序对，求逆序对的数目
输入
第一行为n,表示序列长度，接下来的n行，第i+1行表示序列中的第i个数。
N<=10^5。Ai<=10^5
输出
所有逆序对总数
样例
输入复制
4
3
2
3
2
输出复制
3
#include<bits/stdc++.h>
using namespace std;
int n,m,a[300001];
long long ans;
vector<int>v;
int main()
{
scanf("%d",&n);
for(long long i=1;i<=n;i++)
scanf("%d",&a[i]);
for(long long i=1;i<=n;i++)
{
int now=upper_bound(v.begin(),v.end(),a[i])-v.begin();
// cout<<i<<" "<<now<<endl;
ans=ans+i-now-1,v.insert(v.begin()+now,a[i]);
}
printf("%lld",ans);
return 0;
}
原文：https://www.cnblogs.com/cutemush/p/14116021.html