HDU - 2665 Kth 번호 (주석 트 리 템 플 릿)

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
질문
문제 풀이 방향: 주석 트 리 템 플 릿 문제, 주석 트 리 의 사상 을 더 이상 소개 하지 않 겠 습 니 다. 문제 가 있 으 면 코드 주석 을 볼 수 있 습 니 다.

#include
#include
#include
#include
using namespace std;
const int maxn=100010;
int n,m,q,p,sz;
int a[maxn],b[maxn];
int lc[maxn<<5],rc[maxn<<5],sum[maxn<<5],rt[maxn<<5];
//    nlog(n)
void build(int &rt,int l,int r)//  
{
    rt=++sz;
    sum[rt]=0;//  
    if(l==r)
        return ;//       
    int mid=(l+r)>>1;
    build(lc[rt],l,mid);
    build(rc[rt],mid+1,r);
}
int update(int o,int l,int r)
{
    int oo=++sz;//  
    lc[oo]=lc[o],rc[oo]=rc[o],sum[oo]=sum[o]+1;//          +1
    if(l==r)
        return oo;
    int mid=(l+r)>>1;
    if(mid>=p)
        lc[oo]=update(lc[oo],l,mid);
    else
        rc[oo]=update(rc[oo],mid+1,r);
    return oo;//        
}
int query(int u,int v,int l,int r,int k)
{
    int mid=(l+r)>>1;
    int x=sum[lc[v]]-sum[lc[u]];//     
    if(l==r)
        return l;
    //kth  ，  <=        ，      ，     ；  ，      ，            
    if(x>=k)
        return query(lc[u],lc[v],l,mid,k);
    else
        return query(rc[u],rc[v],mid+1,r,k-x);
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
            sz=0;
        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);
        q=unique(b+1,b+1+n)-b-1;//   
        build(rt[0],1,q);
        for(int i=1;i<=n;i++){
            p=lower_bound(b+1,b+1+q,a[i])-b;
            rt[i]=update(rt[i-1],1,q);
        }
        while(m--){
            int l,r,k;
            scanf("%d%d%d",&l,&r,&k);
            printf("%d
",b[query(rt[l-1],rt[r],1,q,k)]);
        }
    }
    return 0;
}