poj 2104 K-th Number - 經典劃分樹

poj 2104 K-th Number - 經典劃分樹

Description

You are working for Macrohard company in data structures department. After failing your previous task about key insertion you were asked to write a new data structure that would be able to return quickly k-th order statistics in the array segment.
That is, given an array a[1...n] of different integer numbers, your program must answer a series of questions Q(i, j, k) in the form: What would be the k-th number in a[i...j] segment, if this segment was sorted?
For example, consider the array a = (1, 5, 2, 6, 3, 7, 4). Let the question be Q(2, 5, 3). The segment a[2...5] is (5, 2, 6, 3). If we sort this segment, we get (2, 3, 5, 6), the third number is 5, and therefore the answer to the question is 5.

Input

The first line of the input file contains n --- the size of the array, and m --- the number of questions to answer (1 <= n <= 100 000, 1 <= m <= 5 000).
The second line contains n different integer numbers not exceeding 10⁹ by their absolute values --- the array for which the answers should be given.
The following m lines contain question descriptions, each description consists of three numbers: i, j, and k (1 <= i <= j <= n, 1 <= k <= j - i + 1) and represents the question Q(i, j, k).

Output

For each question output the answer to it --- the k-th number in sorted a[i...j] segment.

Sample Input

7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3

Sample Output

5
6
3

Hint

This problem has huge input,so please use c-style input(scanf,printf),or you may got time limit exceed.

 

題目意思：給一個數組，問一個區間內第K大的數。

解題思路：劃分樹。劃分樹是基於快速排序的，首先將原始數組a[]進行排序sorted[]，然後取中位數m，將未排序數組中小於m放在m左邊，大於m的放在m右邊，並記下原始數列中每個數左邊有多少數小於m，用數組to_left[depth][]表示，這就是建樹過程。重點在於查詢過程，設[L,R]為要查詢的區間，[l,r]為當前區間，s 表示[L,R]有多少數放到左子樹，ss表示[l,L-1]有多少數被放倒左子樹，如果s大於等於K，也就是說第K大的數肯定在左子樹裡，下一步就查詢左子樹，但這之前先要更新L,R，新的newl=l+ss, newr=newl+s-1。如果s小於k，也就是說第k大的數在右子樹裡，下一步查詢右子樹，也要先更新L,R，dd表示[l,L-1]中有多少數被放到右子樹，d表示[L,R]有多少數被放到右子樹，那麼newl = m+1+dd，newr=m+d+dd, 這樣查詢逐漸縮小查詢區間，直到最後L==R 返回最後結果就行。

給出一個大牛的圖片例子，

代碼：

 

#include 
#include 
#include 
using namespace std;
#define maxn 100000+100

int val[30][maxn];
int to_left[30][maxn];
int sorted[maxn];
int n;

void build(int l,int r,int d,int rt){
    if(l==r) return;
    int m = (l+r)>>1;
    int lsame = m-l+1;
    for(int i=l;i<=r;i++){
        if(val[d][i]sorted[m]){
            val[d+1][rpos++] = val[d][i];
        }else{
            if(same>1;
    if(s>=k){
        int newl = l+ss;
        int newr = newl + s-1;
        return query(newl,newr,k,l,m,d+1,rt<<1);
    }else{
        int bb = (L-1)-l+1-ss;
        int b = R-L+1 -s;
        int newl = m+1+bb;
        int newr = m+bb+b;  // 4 5 1 3 2 (2,5,4)
        return query(newl,newr,k-s,m+1,r,d+1,rt<<1|1);
    }
}

int main(){
    int m;
    scanf(%d %d,&n,&m);
    for(int i=1;i<=n;i++){
        scanf(%d,&val[0][i]);
        sorted[i]=val[0][i];
    }
    sort(sorted+1,sorted+n+1);
    build(1,n,0,1);
   // print();
    while(m--){
        int i,j,k;
        scanf(%d %d %d,&i,&j,&k);
        printf(%d
,query(i,j,k,1,n,0,1));
    }
    return 0;
}