poj 2104 K - th Number (주석 트 리 템 플 릿)
4021 단어 데이터 구조의 주석 트 리
// by spli
#include
#include
#include
#include
using namespace std;
const int N=200010;
int n,m;
struct node{
int id,v;
}a[N];
int mp[N];
int r[N];
struct seg{
int ls,rs;
int siz;
}t[N*40];int tot;
bool cmp(node x,node y){
return x.vvoid update(int &pos,int L,int R,int v){
t[++tot]=t[pos];pos=tot;
t[pos].siz++;
if(L==R) return;
int mid=(L+R)>>1;
if(v<=mid) update(t[pos].ls,L,mid,v);
else update(t[pos].rs,mid+1,R,v);
}
int query(int ll,int rr,int L,int R,int k){
if(L==R) return L;
int s=t[t[rr].ls].siz-t[t[ll].ls].siz;
int mid=(L+R)>>1;
if(k<=s) return query(t[ll].ls,t[rr].ls,L,mid,k);
else return query(t[ll].rs,t[rr].rs,mid+1,R,k-s);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) scanf("%d",&a[i].v),a[i].id=i;
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;++i) mp[a[i].id]=i;// , lower_bound
for(int i=1;i<=n;++i) r[i]=r[i-1],update(r[i],1,n,mp[i]);
int x,y,k;
while(m--){
scanf("%d%d%d",&x,&y,&k);
printf("%d
",a[query(r[x-1],r[y],1,n,k)].v);
}
return 0;
}