HDU 2665 Kth number(區間第K大) (離散化 主席樹)

HDU 2665 Kth number(區間第K大)   (離散化 主席樹)

題意就是給定一個無序數列,然後給定一堆詢問,求區間[ s , t ]內的第k大的數。

查了很多資料,方法很多,看了半天只看懂了主席樹怎麼做,其餘的做法以後補充。

主席樹(函式式線段樹):

首先是離散化,將所有數按升序對映到正整數。

用線段樹統計這些正整數的出現次數(Sum陣列),這樣就可以快速找到第k大的數。

開始時,是一顆空樹,所有的Sum都為0.

用T[n]表示用數列前n個數按上述方法建立的線段樹的根(以後用根來指代整棵樹)。

然後要求[S,T]區間的按值建立的線段樹,就只需要把兩顆線段樹T[R]和T[S-1]相減(因為葉節點表示的是數出現的次數,滿足區間減法)。

永久化資料結構思想:

永久化資料結構思想就是在修改的時候,不修改原來資料結構,而是新建節點,並且最大限度的複用原來的資料結構。

由於T[n]和T[n-1]之間結構一樣並且,只有一個葉節點的值不同,所以最多有log2 (n) 個節點不同,於是相同的節點可以複用。

就是T[n]只需要多用改變的節點的空間,其餘的直接使用前一棵樹的節點,這樣做的好處是儲存了每個時間的線段樹狀態,也就是儲存了整個操作歷史。

由於沒有破壞原來的資料結構,可以訪問任意時刻的線段樹(從根開始遞迴)。要做到這點,就沒辦法再用原來線段樹的堆式儲存了,而是增加了左右子樹的指標。

也可以仿照SBT的寫法直接用陣列表示節點,用L[]和R[]表示左右子樹的下標。

建樹與查詢:

求T[n]的時候就是在T[n-1]中遞迴,然後把所有經過的節點(也就是修改過的節點)都用新節點存起來。

最後在遞迴訪問線段樹的時候,同步訪問R 和 S-1兩顆線段樹,用Sum[R]-Sum[S-1]來表示[L,R]區間的Sum值

就可以找到第K大的數了。

還有,既然一開始是一顆空樹,就不需要建立一整棵顆空樹了,直接用0表示空樹,省去了開始的一棵樹的空間,

這樣的話需要的空間就是n*log2n

所以主席樹的初始化變得跟SBT一樣簡潔:

L[0]=R[0]=Sum[0]=T[0]=TP=0;

程式碼:

主席樹程式碼:(811MS  27552KB)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
#define maxn 100007
#define maxnn  1860007
using namespace std; 
//主席樹 
int L[maxnn],R[maxnn],Sum[maxnn],T[maxn],TP;//左右子樹,總和,樹根,指標 
void Add(int &rt,int l,int r,int x){//建立新樹
TP;L[TP]=L[rt];R[TP]=R[rt];Sum[TP]=Sum[rt] 1;rt=TP;//複製&新建
if(l==r) return;
int m=(l r)>>1;
if(x <= m) Add(L[rt],l,m,x);
else       Add(R[rt],m 1,r,x);
}
int Search(int TL,int TR,int l,int r,int k){//區間查詢第k大
if(l==r) return l;//返回第k大的下標
int m=(l r)>>1;
if(Sum[L[TR]]-Sum[L[TL]]>=k) return Search(L[TL],L[TR],l,m,k);
else return Search(R[TL],R[TR],m 1,r,k-Sum[L[TR]] Sum[L[TL]]);
}
//常規
int n,m;
int value[maxn];
//離散化 
struct A{
int x,id;
bool operator<(const A&B)const{return x<B.x;}
}ID[maxn];
map<int,int> MP;
int Rank[maxn];
int main(void)
{
int Test;scanf("%d",&Test);
while(Test-->0){
//讀取輸入 離散化 
scanf("%d%d",&n,&m);
for(int i=1;i<=n;  i) {
scanf("%d",&value[i]);
ID[i].x=value[i];
ID[i].id=i;
}
sort(ID 1,ID n 1);MP.clear();
for(int i=1;i<=n;  i){
Rank[i]=ID[i].x;
MP[ID[i].x]=i;
}
//初始化主席樹 
L[0]=R[0]=Sum[0]=T[0]=TP=0;
//建主席樹 
for(int i=1;i<=n;  i) Add(T[i]=T[i-1],1,n,MP[value[i]]);
//開始計算 
for(int i=0;i<m;  i){
int s,t,k;scanf("%d%d%d",&s,&t,&k);
printf("%d\n",Rank[Search(T[s-1],T[t],1,n,k)]); 
}
}
return 0;
}