poj 2104 & hdu 2665 kth number [주석 트 리 입문 문제 + 설명]

또 하루 걸 린 지식 포인트.전 자 는 주로 구간 내 개 수 와 관련 된 문 제 를 처리 하 는데 예 를 들 어 구간 k 가 작고 구간 내 에 숫자 개 수 를 반복 하지 않 는 등 이 선분 수 는 할 수 없다. 주석 나 무 를 수정 할 때 나무 모양 의 배열 을 사용 해 야 한다 고 하면 나무 세트 나무 가 되 지 않 을 까?omg   
손 대 신의 교과서 몇 개 와 인터넷 에 많은 설명 을 하고 나의 이 해 를 말 해 보 세 요.
1. 주석 트 리 의 ls, rs 는 선분 트 리 의 좌우 점 과 다 릅 니 다. 전 자 는 엄격 한 의미 의 좌우 점 이 아니 라 좌우 뿌리 의 번호 입 니 다!
2. cnct 에 저 장 된 것 은 이 숫자 가 나타 난 횟수 라 는 점 은 의심 할 여지 가 없다.
3. 특정한 값 이 수정 되 었 을 때 이 점 은 루트 노드 라 는 길 (갈 라 지지 않 은) 까지 복사 한 다음 에 연결 점 의 번호 에 대응 하 는 변 화 는 관련 되 지 않 는 것 은 변 하지 않 는 다.인터넷 에서 수 동 쓰레기 를 회수 하면 메모리 비용 이 줄어든다 고 말 하 는 이유 다.
게다가 이 입문 문 제 는 구간 내 k 가 작 아야 한다.
먼저 배열 을 분 산 했 습 니 다.그리고 rt 배열 의 역할: 특정한 노드, 특정한 버 전 번 호 를 저장 하 는 대응 관계

/***********
poj2104
2016.1.24
24472K	1594MS	C++	1995B
***********/
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100001;
struct Node
{
    int ls,rs,cnt;
}tr[maxn*20];
int cur,rt[maxn];
void init()
{
    cur=0;
}
inline void push_up(int o)
{
    tr[o].cnt=tr[tr[o].ls].cnt+tr[tr[o].rs].cnt;
}
int build(int l,int r)
{
    int k=cur++;
    if(l==r)
    {
        tr[k].cnt=0;
        return k;
    }
    int mid=(l+r)>>1;
    tr[k].ls=build(l,mid);
    tr[k].rs=build(mid+1,r);
    push_up(k);
    return k;
}
int update(int o,int l,int r,int pos,int val)
{
    int k=cur++;
    tr[k]=tr[o];
    if(l==pos&&r==pos)
    {
        tr[k].cnt+=val;
        return k;
    }
    int mid=(l+r)>>1;
    if(pos<=mid) tr[k].ls=update(tr[o].ls,l,mid,pos,val);
    else tr[k].rs=update(tr[o].rs,mid+1,r,pos,val);
    push_up(k);
    return k;
}
int query(int l,int r,int o,int v,int kth)
{
    if(l==r) return l;
    int mid=(l+r)>>1;
    int res=tr[tr[v].ls].cnt-tr[tr[o].ls].cnt;
    if(kth<=res) return query(l,mid,tr[o].ls,tr[v].ls,kth);
    else return query(mid+1,r,tr[o].rs,tr[v].rs,kth-res);
}
int b[maxn],sortb[maxn];
bool cmp(int x,int y)
{
    return x>y;
}
int main()
{
    //freopen("cin.txt","r",stdin);
    int n,m,T;
    //scanf("%d",&T);
    while(~scanf("%d%d",&n,&m))
    {
        init();
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&b[i]);
            sortb[i]=b[i];
        }
        sort(sortb+1,sortb+1+n);
        int cnt=1;
        for(int i=2;i<=n;i++)
            if(sortb[i]!=sortb[cnt]) sortb[++cnt]=sortb[i];
        rt[0]=build(1,cnt);
        for(int i=1;i<=n;i++)
        {
            int p=lower_bound(sortb+1,sortb+1+cnt,b[i])-sortb;
            rt[i]=update(rt[i-1],1,cnt,p,1);
        }
        for(int i=0;i<m;i++)
        {
            int a,b,k;
            scanf("%d%d%d",&a,&b,&k);
            int idx=query(1,cnt,rt[a-1],rt[b],k);
            printf("%d
",sortb[idx]);
        }
    }
    return 0;
}

/***********
hdu2665
2016.1.24
826MS 25872K 2106 B G++
***********/
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100001;
struct Node
{
    int ls,rs,cnt;
}tr[maxn*20];
int cur,rt[maxn];
void init()
{
    cur=0;
}
inline void push_up(int o)
{
    tr[o].cnt=tr[tr[o].ls].cnt+tr[tr[o].rs].cnt;
}
int build(int l,int r)
{
    int k=cur++;
    if(l==r)
    {
        tr[k].cnt=0;
        return k;
    }
    int mid=(l+r)>>1;
    tr[k].ls=build(l,mid);
    tr[k].rs=build(mid+1,r);
    push_up(k);
    return k;
}
int update(int o,int l,int r,int pos,int val)
{
    int k=cur++;
    tr[k]=tr[o];
    if(l==pos&&r==pos)
    {
        tr[k].cnt+=val;
        return k;
    }
    int mid=(l+r)>>1;
    if(pos<=mid) tr[k].ls=update(tr[o].ls,l,mid,pos,val);
    else tr[k].rs=update(tr[o].rs,mid+1,r,pos,val);
    push_up(k);
    return k;
}
int query(int l,int r,int o,int v,int kth)
{
    if(l==r) return l;
    int mid=(l+r)>>1;
    int res=tr[tr[v].ls].cnt-tr[tr[o].ls].cnt;
    if(kth<=res) return query(l,mid,tr[o].ls,tr[v].ls,kth);
    else return query(mid+1,r,tr[o].rs,tr[v].rs,kth-res);
}
int b[maxn],sortb[maxn];
bool cmp(int x,int y)
{
    return x>y;
}
int main()
{
    //freopen("cin.txt","r",stdin);
    int n,m,T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        init();
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&b[i]);
            sortb[i]=b[i];
        }
        sort(sortb+1,sortb+1+n);
        int cnt=1;
        for(int i=2;i<=n;i++)
            if(sortb[i]!=sortb[cnt]) sortb[++cnt]=sortb[i];
        rt[0]=build(1,cnt);
        for(int i=1;i<=n;i++)
        {
            int p=lower_bound(sortb+1,sortb+1+cnt,b[i])-sortb;
            rt[i]=update(rt[i-1],1,cnt,p,1);
        }
        for(int i=0;i<m;i++)
        {
            int a,b,k;
            scanf("%d%d%d",&a,&b,&k);
            int idx=query(1,cnt,rt[a-1],rt[b],k);
            printf("%d
",sortb[idx]);
        }
    }
    return 0;
}