[原创]POJ 2104 K-th Number [主席树入门]【数据结构】

2017-03-10 21:51:50 Tabris_ 阅读数：487

博客爬取于2020-06-14 22:41:22
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/61209605

题目链接:http://poj.org/problem?id=2104
————————————————————————————————————————————————
K-th Number
Time Limit: 20000MS Memory Limit: 65536K
Total Submissions: 53824 Accepted: 18506
Case Time Limit: 2000MS
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 109 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大的数值

解题思路:
算法不用想妥妥的主席树啊

之前一直没有学习主席树,就是理解不了主席树,
今天找到了一个很好的
博客1
博客2

算是明白了什么是主席树,

主席树为了保存历史版本的状态 ,于是在每次更新的时候都在开出一条链来代表新建出来的节点,

这样就不用每次在建一颗树了

其实主席树是一种函数式线段树

寻找 $[l,r]$ 区间的值其实也就成了找第 $R$ 个版本-第 $l-1$ 个版本就是我们要查询的值了

附本题代码
——————————————————————————————————————————————————

# pragma comment(linker, "/STACK:1024000000,1024000000")
//#include<bits/stdc++.h>
# include <stdio.h>
# include <algorithm>
using namespace std;

typedef long long int LL;

const int    INF = (~(1<<31));
const int    N   = 100000+7;
const double eps = 1e-7;

inline int read(){
    int x=0,f=1;char ch = getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while('0'<=ch&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*f;
}
/****************************************************/

int rt[N*20],ls[N*20],rs[N*20],sum[N*20],tot;
int n,q,ql,qr,x,a[N],b[N],sz;
void build(int &rt,int l,int r){
    rt=++tot;
    sum[rt]=0;
    if(l==r) return ;
    int m = (r+l)>>1;
    build(ls[rt],l,m);
    build(rs[rt],m+1,r);
}
void update(int &rt,int l,int r,int last,int pos){
    rt = ++tot;
    ls[rt]=ls[last];
    rs[rt]=rs[last];
    sum[rt]=sum[last]+1;
    if(l==r) return ;
    int m = (r+l)>>1;
    if(pos<=m) update(ls[rt],l,m,ls[last],pos);
    else       update(rs[rt],m+1,r,rs[last],pos);
}
int query(int ss,int tt,int l,int r,int k){
    if(l==r)return l;
    int m = (l+r)>>1;
    int cnt=sum[ls[tt]]-sum[ls[ss]];
    if(k<=cnt)return query(ls[ss],ls[tt],l,m,k);
    else  return query(rs[ss],rs[tt],m+1,r,k-cnt);
}

void qq(){
    scanf("%d%d%d",&ql,&qr,&x);
    printf("%d\n",b[query(rt[ql-1],rt[qr],1,sz,x)]);
}

int main(){
    while(~scanf("%d%d",&n,&q)){

        for(int i=1;i<=n;i++) scanf("%d",a+i),b[i]=a[i];
        sort(b+1,b+n+1);
        sz=unique(b+1,b+n+1)-(b+1);

        tot = 0;
        build(rt[0],1,sz);

        for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+sz+1,a[i])-b;
        for(int i=1;i<=n;i++)update(rt[i],1,sz,rt[i-1],a[i]);
        while(q--)qq();
    }
    return 0;
}