hdu 2665 Kth number 主席树

时间：2024-08-30 17:36:50

Kth number

Time Limit: 15000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

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
思路：主席树板子题；
#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<iostream>

#include<cstdio>

#include<cmath>

#include<string>

#include<queue>

#include<algorithm>

#include<stack>

#include<cstring>

#include<vector>

#include<list>

#include<set>

#include<map>

using namespace std;

#define ll long long

#define pi (4*atan(1.0))

#define eps 1e-14

#define bug(x)  cout<<"bug"<<x<<endl;

const int N=1e5+,M=1e6+,inf=;

const ll INF=1e18+,mod=;

struct Chairmantree

{

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

    int tot;

    void init()

    {

        tot=;

    }

    void build(int l,int r,int &pos)

    {

        pos=++tot;

        sum[pos]=;

        if(l==r)return;

        int mid=(l+r)>>;

        build(l,mid,ls[pos]);

        build(mid+,r,rs[pos]);

    }

    void update(int p,int c,int pre,int l,int r,int &pos)

    {

        pos=++tot;

        ls[pos]=ls[pre];

        rs[pos]=rs[pre];

        sum[pos]=sum[pre]+c;

        if(l==r)return;

        int mid=(l+r)>>;

        if(p<=mid)

            update(p,c,ls[pre],l,mid,ls[pos]);

        else

            update(p,c,rs[pre],mid+,r,rs[pos]);

    }

    int query(int L,int R,int l,int r,int k)

    {

        if(l==r)return l;

        int mid=(l+r)>>;

        int num=sum[ls[R]]-sum[ls[L]];

        if(k<=num)return query(ls[L],ls[R],l,mid,k);

        else return query(rs[L],rs[R],mid+,r,k-num);

    }

};

Chairmantree tree;

int a[N],b[N];

int getpos(int x,int cnt)

{

    int pos=lower_bound(b+,b+cnt,x)-b;

    return pos;

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        int n,m;

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

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

        {

            scanf("%d",&a[i]);

            b[i]=a[i];

        }

        sort(b+,b++n);

        int num=unique(b+,b++n)-b;

        tree.init();

        tree.build(,num-,tree.rt[]);

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

        {

            int p=getpos(a[i],num);

            tree.update(p,,tree.rt[i-],,num-,tree.rt[i]);

        }

        //for(int i=1;i<num;i++)

        //    printf("%d ",tree.rt[i]);

        //printf("\n");

        while(m--)

        {

            int l,r,k;

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

            printf("%d\n",b[tree.query(tree.rt[l-],tree.rt[r],,num-,k)]);

        }

    }

    return ;

}

相关文章