前两天做树状数组和线段树专题时碰到过
当时的做法如下
思路：从前往后读，读一个数x，让a[x]+=1，然后让ans+=∑（i=x+1…n)a[i],这个地方用线段树或者树状数组优化降低时间复杂度为lgn
再优化方法：离散化
时间复杂度o(nlgn)
学习了分治法后，发现分治法的时间复杂度也是o(nlgn)
当然这里也能用离散化优化
分治法代码
#include
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn=1000000;
ll n,A[maxn],L[maxn],R[maxn],i,j,k,ans;
void merge(ll A[],ll p,ll q,ll r)
{
ll n1,n2;
n1=q-p+1;
n2=r-q;
for(i=1;
i<=n1;
i++)
L[i]=A[p+i-1];
for(j=1;
j<=n2;
j++)
R[j]=A[q+j];
L[n1+1]=inf;
R[n2+1]=inf;
i=1;
j=1;
for(k=p;
k<=r;
k++)
{
if(L[i]<=R[j])
{
A[k]=L[i];
i=i+1;
}
else
{
A[k]=R[j];
j=j+1;
ans+=n1-i+1;
}
}
}
void mergesort(ll A[],ll p,ll r)
{
if(p 【算法导论学习笔记——2.3.1分治法——习题2-4逆序对数】思路解析：
在分治的同时，加入判断
对于L数组和R数组，应该是L数组排在R数组前，
所以如果R数组的首元素比L数组的首元素小，
那么R数组首元素比L[i]到L[n]小，
即产生n1-i+1个逆序对
(n1为L数组长度，i为当前L数组首元素下标，n1-i+1即为L[i]到L[n]的长度）
推荐阅读
- 集合的全排列（Java实现）
- 拓展欧几里得算法详解
- 算法导论程序15-计数排序（Python）
- 算法导论 — 8.3 基数排序
- 算法导论程序16--基数排序（Python）
- 算法导论 基数排序
- RSA模重复平方算法小示例
- 【算法导论之四】计数排序
- 算法导论计数排序实现