[지속 가능 한 라인 트 리] poj 2104 정적 구간 k 대

#include 
#include 
#include 
using namespace std;
int ls[5000000];
int rs[5000000];
int sum[5000000];
int san[5000000];
int num[5000000];
int T[5000000];
int n,m,tot = 0,rt;

void build(int l,int r,int &x)
{
    x = ++ tot;
    sum[x] = 0;
    if(l == r)
        return ;
    int mid = (l+r)/2;
    build(l,mid,ls[x]);
    build(mid+1,r,rs[x]);
}

void update(int last,int p,int l,int r,int &x)
{
    x = ++ tot;
    ls[x] = ls[last];
    rs[x] = rs[last];
    sum[x] = sum[last] + 1;
    if(l == r)
        return ;
    int mid = (l+r)/2;
    if(p <= mid)
        update(ls[last],p,l,mid,ls[x]);
    else
        update(rs[last],p,mid+1,r,rs[x]);
}

int query(int s,int t,int l,int r,int k)
{
    if(l == r)
        return l;
    int mid = (l+r)/2;
    int cnt = sum[ls[t]] - sum[ls[s]];
    if(k <= cnt)
        return query(ls[s],ls[t],l,mid,k);
    else
        return query(rs[s],rs[t],mid+1,r,k-cnt);
}

int main()
{
    int x,y,z;
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i ++)
    {
        scanf("%d",&num[i]);
        san[i] = num[i];
    }
    tot = 0;
    sort(san+1,san+n+1);
    int cnt = unique(san+1,san+n+1)-san-1;
    build(1,cnt,T[0]);
    for(int i = 1;i <= n;i ++)
        num[i] = lower_bound(san+1,san+cnt+1,num[i]) - san;
    for(int i = 1;i <= n;i ++)
        update(T[i-1],num[i],1,cnt,T[i]);
    for(int i = 1;i <= m;i ++)
    {
        scanf("%d%d%d",&x,&y,&z);
        int id = query(T[x-1],T[y],1,cnt,z);
        printf("%d
",san[id]);
    }
    return 0;
}