本文共 1281 字，大约阅读时间需要 4 分钟。
树状数组 离散化
树状数组可以通过查询操作来查找比某数小的数，我们可以利用这一性质来实现逆序对。
怎么采用离散化 建立一个结构体包含val和id， val就是输入的数，id表示输入的顺序。然后按照val从小到大排序，如果val相等，那么就按照id排序。 val：9 -1 18 5 id： 1 2 3 4 排好序之后就变成了val ： -1 5 9 18
id： 2 4 1 3
2 4 1 3 的逆序数 也是3
#include#include #include #include #include #include #include #define inf 0x3f3f3f#define lowbit(x) x&-xusing namespace std;const int N=1e5+5;typedef long long ll;int n;struct node{ int x,id;}q[N];int c[N*5];void add(int i){ while(i<=n) { c[i]++; i+=lowbit(i); }}long long sum(int i){ long long res=0; while(i>0) { res+=c[i]; i-=lowbit(i); } return res;}bool cmp(node x,node y){ return x.x
归并排序
分冶归并排序原理是将整个序列分为两段进行排序，我们可以利用这个性质，后段插入的其序号必定比前段剩余的高，所以其可以组成逆序对
#include#include #include #include #include #include #include #define inf 0x3f3f3fusing namespace std;const int N=1e6+5;typedef long long ll;int a[N],tmp[N];long long cnt=0;void solve(int l,int r){ if(l>=r) return; int mid=(l+r)>>1; solve(l,mid); solve(mid+1,r); int pl=l,pr=mid+1,p=0; while(pl<=mid&&pr<=r) { if(a[pl]<=a[pr]) tmp[p++]=a[pl++]; else tmp[p++]=a[pr++],cnt+=mid-pl+1; } while(pl<=mid) tmp[p++]=a[pl++]; while(pr<=r) tmp[p++]=a[pr++]; for(int i=0;i
转载地址：http://dculz.baihongyu.com/