首页 > 代码库 > Day2:T4求逆序对(树状数组+归并排序)
Day2:T4求逆序对(树状数组+归并排序)
T4: 求逆序对
A[I]为前缀和
推导 (A[J]-A[I])/(J-I)>=M
A[j]-A[I]>=M(J-I)
A[J]-M*J>=A[I]-M*I
设B[]=A[]-M*();
B[J]>=B[I]
也就是求逆序对;
求逆序对的方法主要有两种:
归并排序;
树状数组;
这里两种方法都学习一下:
1.之前对于树状数组的印象就只有单点修改和区间求和
一直觉得lowbit是一个神奇的东西(至今没有搞懂原理)
上网搜了一下用树状数组求逆序对的方法,发现有一个大神写的很棒....看得很明白(感谢~~)
顺便学了一下离散化,也就是文中的:
for
(i=1;i<=n;i++)
{
scanf
(
"%d"
,&in[i].v);
in[i].order=i;
}
sort(in+1,in+n+1,cmp);
for
(i=1;i<=n;i++) aa[in[i].order]=i;
有点像指针操作。(自己对离散化的初步感受是这样的)
然后就是根据树状数组的原理求逆序对了
其实一直不是很清楚树状数组的原理,翻了翻书才有一点点的领悟吧
1).首先是update中的c数组的理解,上面链接的那个资料中解释的过程会误以为c是统计某个数的个数的
仔细看白书会发现其实并不是这样,c数组是用来维护某一区间的区间和的
getsum的操作也就是把沿途中的长条所表示的区间和加起来,这样可以节省时间(注意理解图)
2).具体的,标程中的c是用来记录在某个区间里有多少个数比i小
3).理解lowbit的过程,同样需要仔细回看白书的解释
无论是i=t-n;i+=lowbit(i)或是i-=lowbit(i)都是一个找父亲的过程
4).其实说白了lowbit到底有什么用呢,其实也就是节省了时间,做到快速简便而已吧
嗯...这样的话,对于树状数组的原理算是搞懂了QAQ感觉这种东西很容易忘记怎么办?
给以后的自己一个忠告呗~先看白书,好好理解图,再看自己的感悟,最后看链接资料;
2.另一种方法就是很传统的用:归并排序求逆序对
这种算法求逆序对也很容易理解,简单的说也无非就是基于快排思想+统计个数
主要的程序:p版的...不要在意这些细节...
procedure mergesort(l,r:longint);var mid,i,j,k:longint;begin if l=r then exit; mid:=(l+r) div 2; mergesort(l,mid); mergesort(mid+1,r); i:=l;j:=mid+1;k:=l; while (i<=mid) and (j<=r) do if v[i]<v[j] then begin push(k,i); ans:=ans+r-j+1;//在l..mid 和 mid+1 ..r中j处于[mid+1,r]中且这段是升序的,那么如果v[j]>v[i]那么v[j..r]都会大于//v[i]这和求逆序对有异曲同工之妙 end else push(k,j); while i<=mid do push(k,i); while j<=r do push(k,j); for i:=l to r do v[i]:=temp[i];end;
根据推导建立等式,之后输出ans即可
很好理解就不多说了...
晚安民那
Day2:T4求逆序对(树状数组+归并排序)