hdu 2665 Kth number 主席树

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

Source

HDU男生专场公开赛——赶在女生之前先过节（From WHU）

思路：主席树板子题；

#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+10,M=1e6+10,inf=2147483647;
const ll INF=1e18+10,mod=2147493647;
struct Chairmantree
{
    int rt[N*20],ls[N*20],rs[N*20],sum[N*20];
    int tot;
    void init()
    {
        tot=0;
    }
    void build(int l,int r,int &pos)
    {
        pos=++tot;
        sum[pos]=0;
        if(l==r)return;
        int mid=(l+r)>>1;
        build(l,mid,ls[pos]);
        build(mid+1,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)>>1;
        if(p<=mid)
            update(p,c,ls[pre],l,mid,ls[pos]);
        else
            update(p,c,rs[pre],mid+1,r,rs[pos]);
    }
    int query(int L,int R,int l,int r,int k)
    {
        if(l==r)return l;
        int mid=(l+r)>>1;
        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+1,r,k-num);
    }
};
Chairmantree tree;
int a[N],b[N];
int getpos(int x,int cnt)
{
    int pos=lower_bound(b+1,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=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            b[i]=a[i];
        }
        sort(b+1,b+1+n);
        int num=unique(b+1,b+1+n)-b;
        tree.init();
        tree.build(1,num-1,tree.rt[0]);
        for(int i=1;i<=n;i++)
        {
            int p=getpos(a[i],num);
            tree.update(p,1,tree.rt[i-1],1,num-1,tree.rt[i]);
        }
        //for(int i=1;i<num;i++)
        //    printf("%d ",tree.rt[i]);
        //printf("
");
        while(m--)
        {
            int l,r,k;
            scanf("%d%d%d",&l,&r,&k);
            printf("%d
",b[tree.query(tree.rt[l-1],tree.rt[r],1,num-1,k)]);
        }
    }
    return 0;
}