歸并排序和樹(shù)狀數(shù)組都可以用nlogn的算法做到求出逆序?qū)?但這里著重講樹(shù)狀數(shù)組的原理與求法.
樹(shù)狀數(shù)組最常用的方面就是用來(lái)求逆序?qū)? 普通方法需要n^2的復(fù)雜度, 而樹(shù)狀數(shù)組只需要用nlogn的復(fù)雜度, 所以是很好的優(yōu)化, 關(guān)鍵在于內(nèi)部函數(shù)lowbit的應(yīng)用.
這是樹(shù)狀數(shù)組的結(jié)構(gòu)圖 : lowbit函數(shù)就是進(jìn)行哪些實(shí)現(xiàn)之間的轉(zhuǎn)化的, 因?yàn)檫@些數(shù)之間在二進(jìn)制中存在著某種聯(lián)系, 而lowbit函數(shù)便可把這些聯(lián)系體現(xiàn)出來(lái).!!!
總之記住樹(shù)狀數(shù)組實(shí)現(xiàn)的是nlogn的算法, 和他具體實(shí)現(xiàn)的是什么功能就行了.
當(dāng)數(shù)據(jù)的范圍較小時(shí)，比如maxn=100000，那么我們可以開(kāi)一個(gè)數(shù)組c[maxn],來(lái)記錄前面數(shù)據(jù)的出現(xiàn)情況，初始化為0；當(dāng)數(shù)據(jù)a出現(xiàn)時(shí)，就令c[a]=1。這樣的話(huà)，欲求某個(gè)數(shù)a的逆序數(shù)，只需要算出在當(dāng)前狀態(tài)下c[a+1,maxn]中有多少個(gè)1，因?yàn)檫@些位置的數(shù)在a之前出現(xiàn)且比a大。但是若每添加一個(gè)數(shù)據(jù)a時(shí)，就得從a+1到 maxn搜一遍，復(fù)雜度太高了。樹(shù)狀數(shù)組卻能很好的解決這個(gè)問(wèn)題，可以把數(shù)一個(gè)個(gè)插入到樹(shù)狀數(shù)組中， 每插入一個(gè)數(shù)， 統(tǒng)計(jì)比他小的數(shù)的個(gè)數(shù)，對(duì)應(yīng)的逆序?yàn)?i - getsum( c[i] )，其中 i 為當(dāng)前已經(jīng)插入的數(shù)的個(gè)數(shù)， getsum( c[i] ）為比 c[i] 小的數(shù)的個(gè)數(shù)，i- getsum( c[i] ) 即比c[i] 大的個(gè)數(shù)， 即逆序的個(gè)數(shù)。最后需要把所有逆序數(shù)求和，就是在插入的過(guò)程中邊插入邊求和.
舉個(gè)例子：有5個(gè)數(shù)，分別為5 3 4 2 1，當(dāng)讀入數(shù)據(jù)a=5時(shí)，c為：0，0，0，0，1；d為：0，0，0，0，1；當(dāng)讀入數(shù)據(jù)a=3時(shí)，c為：0，0，1，0，1；d為：0，0 ， 1，1，1；當(dāng)讀入數(shù)據(jù)a=4時(shí)，c為：0，0，1，1，1；d為：0，0，1，2，1；
此思想的關(guān)鍵在于，讀入數(shù)據(jù)的最大值為maxn，由于maxn較小，所以可以用數(shù)組來(lái)記錄狀態(tài)。當(dāng)maxn較大時(shí)，直接開(kāi)數(shù)組顯然是不行了，這是的解決辦法就是離散化。所謂離散化，就是將連續(xù)問(wèn)題的解用一組離散要素來(lái)表征而近似求解的方法，這個(gè)定義太抽象了，還是舉個(gè)例子吧。
假如現(xiàn)在有一些數(shù)：1234 98756 123456 99999 56782,由于1234是第一小的數(shù)，所以num[1]=1;依此，有num[5]=2,num[2]=3,num[4]=4,num[3]=5;這樣轉(zhuǎn)化后并不影響原來(lái)數(shù)據(jù)的相對(duì)大小關(guān)系，何樂(lè)而不為呢?。?！
還有一點(diǎn)值得注意，當(dāng)有數(shù)據(jù)0出現(xiàn)時(shí)，由于0&0=0，無(wú)法更新，此時(shí)我們可以采取加一個(gè)數(shù)的方法將所有的數(shù)據(jù)都變成大于0的.
具體看代碼 : 樹(shù)狀數(shù)組+去重離散化
#include<cstdio>
#include<algorithm>
#include<cstring>
#define CLR(x) memset(x,0,sizeof(x))
#define ll long long int
#define PI acos(-1.0)
#define db double
#define mod 1000000007
using namespace std;
const int maxn=1e5+5;
const db eps=1e-6;
const int inf=1e9;
const ll INF=1e15;
int c[maxn]; //樹(shù)狀數(shù)組
int lisan[maxn]; //用來(lái)離散的存離散后的結(jié)果數(shù)組
int s[maxn]; //用來(lái)存原始狀態(tài)
int n,k;
//樹(shù)狀數(shù)組
int lowbit(int x) //返回值最大1e5.
{
return x&(-x);
}
void update(int i,int ans)
{
while(i <= n){
c[i] += ans;
i += lowbit(i);
}
}
int sum(int i)
{
int s = 0;
while(i > 0){
s += c[i];
i -= lowbit(i);
}
return s;
}
//結(jié)束
int main()
{
while(~scanf("%d%d",&n,&k)){
CLR(c);
for(int i=0;i<n;i++){
scanf("%d",&s[i]);
lisan[i] = s[i];
}
sort(lisan,lisan+n);
int len=unique(lisan,lisan+n)-lisan;
ll res = 0;
for(int i=0;i<n;i++){
ll l=lower_bound(lisan,lisan+len,s[i])-lisan+1;
update(l,1);
res += i+1 - sum(l);
}
if(res < k) printf("0\n");
else
printf("%lld\n",res-k);
}
}
說(shuō)一說(shuō)離散那部分.
/* 首先看題就知道肯定是需要進(jìn)行離散化的, 還有一個(gè)問(wèn)題就是可能有重?cái)?shù), 對(duì)于sort這種不穩(wěn)定排序, 不考慮
*重?cái)?shù), 是對(duì)結(jié)果又影響的, 所以需要進(jìn)行去重離散化, 一般的離散化也可以做到, 就是知道判到不重了, 就離散
* 化, 但是稍微有點(diǎn)麻煩, 所以這里就用到了, unique 和 lower_bound 函數(shù), unique是使該數(shù)組中相同的部分去
* 掉, 而lower_bound是返回第一個(gè)大于或等于x的位置, 返回的都是地址.
*/
for(int i=0;i<n;i++){
scanf("%d",&s[i]);
lisan[i] = s[i];
}
sort(lisan,lisan+n); //首先排序
int len=unique(lisan,lisan+n)-lisan; //求出離散數(shù)組的長(zhǎng)度并去重.
ll res = 0;
for(int i=0;i<n;i++){
int l=lower_bound(lisan,lisan+len,s[i])-lisan+1; //實(shí)際上是返回的s[i] 在lisan數(shù)組中下標(biāo)位置(從1開(kāi)始) 然后
//給原先那個(gè)數(shù)組所有相同的數(shù)都統(tǒng)一賦成一個(gè)值. 這樣就可以到達(dá)去重的目的. l 既是離散化后的結(jié)果
update(l,1);
res += i+1 - sum(l);
}
所以實(shí)際上不管離不離散化都可以用這種方法.
