Kth number

Time Limit: 15000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 12984 Accepted Submission(s): 3962

Problem Description

Give you a sequence and ask you the kth big number of a inteval.

Input

The first line is the number of the test cases.
For each test case, the first line contain two integer n and m (n, m <= 100000), indicates the number of integers in the sequence and the number of the quaere.
The second line contains n integers, describe the sequence.
Each of following m lines contains three integers s, t, k.
[s, t] indicates the interval and k indicates the kth big number in interval [s, t]

Output

For each test case, output m lines. Each line contains the kth big number.

Sample Input

10 1

1 4 2 3 5 6 7 8 9 0

1 3 2

Sample Output

http://blog.sina.com.cn/s/blog_4a0c4e5d0101c3ev.html ：详解

http://blog.csdn.net/acdreamers/article/details/8656644 ：代码

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=;

int T[N],num[N],san[N];

int ls[N*],rs[N*],sum[N*];

int tot,n,m;

void Update(int last,int p,int l,int r,int &rt){

    rt=++tot;

    ls[rt]=ls[last];

    rs[rt]=rs[last];

    sum[rt]=sum[last]+;

    if(l==r) return;

    int m=(l+r)>>;

    if(p<=m) Update(ls[last],p,l,m,ls[rt]);

    else Update(rs[last],p,m+,r,rs[rt]);

}

int Query(int ss,int tt,int l,int r,int k){

    if(l==r) return l;

    int m=(l+r)>>;

    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+,r,k-cnt);

}

void work(){

    int l,r,k;

    for(int i=;i<=n;++i) {

        scanf("%d",num+i);

        san[i]=num[i];

    }

    tot=;

    sort(san+,san+n+);

    int cnt=unique(san+,san+n+)-san-;for(int i=;i<=n;++i)

    num[i]=lower_bound(san+,san+cnt+,num[i])-san;

    for(int i=;i<=n;++i) Update(T[i-],num[i],,cnt,T[i]);

    while(m--) {

        scanf("%d%d%d",&l,&r,&k);

        int id=Query(T[l-],T[r],,cnt,k);

        printf("%d\n",san[id]);

    }

}

int main(){

    int T;

    for(scanf("%d",&T);T--;){

        scanf("%d%d",&n,&m);

        work();

    }

}

巴特西

hdu2665可持久化线段树，求区间第K大

Kth number

最新文章

热门文章