首页 > 代码库 > HDU 2665.Kth number 区间第K小

HDU 2665.Kth number 区间第K小

Kth number

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


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
1
10
1 1 4 2 3 5 6 7 8 9 0
1 3 2
 

 

Sample Output
2
 

 

Source
HDU男生专场公开赛——赶在女生之前先过节(From WHU)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2665
题意:求区间第K小(区间升序第k个数)
思路:归并树。二分答案x。判断不超过x的数在区间内多少个。假设x是区间第k小,那么在区间内不超过x的数不少于k个。
代码:
技术分享
#include<iostream>#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>#include<map>#include<queue>#include<stack>#include<vector>#include<set>using namespace std;#define PI acos(-1.0)typedef long long ll;typedef pair<int,int> P;const int maxn=1e5+100,maxm=1e5+100,inf=0x3f3f3f3f,mod=1e9+7;const ll INF=1e13+7;inline int get_int(){    int num=0;    char ch;    while((ch=getchar())!= &&ch!=\n)        num=num*10+(ch-0);    return num;}/****************************/struct edge{    int from,to;    int cost;};edge es[maxm];struct node{    int num;    int k;};node sign[maxn];int a[maxn];int cmp(node x,node y){    return x.num<y.num;}vector<node>tree[maxn<<2];void build(int l,int r,int pos){    if(l==r) return;    int mid=(l+r)/2;    for(int i=0; i<tree[pos].size(); i++)    {        int k=tree[pos][i].k;        if(l<=k&&k<=mid) tree[pos<<1].push_back(tree[pos][i]);        else tree[pos<<1|1].push_back(tree[pos][i]);    }    build(l,mid,pos<<1);    build(mid+1,r,pos<<1|1);}int query(int L,int R,int w,int l,int r,int pos){    if(L<=l&&r<=R)    {        int s=0,e=tree[pos].size()-1;        int cou=-1;        while(s<=e)        {            int md=(s+e)/2;            if(tree[pos][md].num<=w) s=md+1,cou=md;            else e=md-1;        }        return cou+1;    }    int mid=(l+r)/2;    int ans=0;    if(L<=mid) ans+=query(L,R,w,l,mid,pos<<1);    if(R>mid) ans+=query(L,R,w,mid+1,r,pos<<1|1);    return ans;}int main(){    int T;    scanf("%d",&T);    while(T--)    {        int n,q;        scanf("%d%d",&n,&q);        for(int i=0; i<=4*n; i++) tree[i].clear();        for(int i=0; i<n; i++)        {            scanf("%d",&a[i]);            sign[i].num=a[i],sign[i].k=i+1;        }        sort(sign,sign+n,cmp);        for(int i=0; i<n; i++) tree[1].push_back(sign[i]);        build(1,n,1);        while(q--)        {            int l,r,k;            scanf("%d%d%d",&l,&r,&k);            int L=0,R=n-1;            int ans=n-1;            while(L<=R)            {                int mid=(L+R)/2;                int w=sign[mid].num;                if((query(l,r,w,1,n,1))>=k) R=mid-1,ans=mid;                else L=mid+1;            }            printf("%d\n",sign[ans].num);        }    }    return 0;}
区间第K小

 

HDU 2665.Kth number 区间第K小