poj 2104 K - th Number 정적 구간 K 대 지속 가능 데이터 구조

정적 구간 K 가 크다.
우선 K 대 방법 을 모 을 겁 니 다.값 에 따라 나 무 를 만 들 고 [i, j] 는 [i, p] [p + 1, j] 라인 트 리 의 평균 점 으로 나 뉜 다.만약 sum (i, p) > = k 가 크 면 k 가 왼쪽 구간 에 있다 는 것 을 설명 하고 그 다음 에 왼쪽 구간 에서 k 가 크 면 오른쪽 구간 에서 k - sum (i, p) 이 크다.
지속 가능 한 데이터 구조 가 서로 감소 하 는 성질 을 이용 하여 매번 아래 표 시 된 left 에서 right 까지 값 은 [i, p] 의 개수 에 있 습 니 다.

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <cstring>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <assert.h>
#include <queue>
#define REP(i,n) for(int i=0;i<n;i++)
#define TR(i,x) for(typeof(x.begin()) i=x.begin();i!=x.end();i++)
#define ALLL(x) x.begin(),x.end()
#define SORT(x) sort(ALLL(x))
#define CLEAR(x) memset(x,0,sizeof(x))
#define FILLL(x,c) memset(x,c,sizeof(x))
using namespace std;
const double eps = 1e-9;
#define LL long long 
#define pb push_back
const int maxn = 100100;
int n ,m ;
map<int ,int >mp;
map<int ,int >::iterator it;
int idx[maxn];
int num[maxn];

struct Node{
     Node *l,*r;
     int sum;
}nodes[maxn *25];
Node *root[maxn];
struct Seg{
	 Node *null;
	 int C;
	 void init(){
	 	 C = 0 ;
	 	 null = &nodes[C++];
	     null->l = null->r = null;
	     null->sum = 0;
	     root[0] = null;
	 }
	 Node * update(int pos,int left ,int right ,Node *root,int val){
	 	  Node *rt = &nodes[C++];
	 	  rt->l = root->l;
	 	  rt->r = root->r;
	 	  rt->sum = root->sum;
	 	  if(left == right){
	 	  	  rt->sum += val;
	 	  	  return rt;
	 	  }
	 	  int mid = (left + right)/2;
	 	  if(pos<= mid){
	 	  	  rt->l = update(pos,left,mid,root->l,val);
	 	  }
	 	  if(pos>mid){
	 	  	  rt->r = update(pos,mid+1,right,root->r,val);
	 	  }
	 	  rt->sum = rt->l->sum + rt->r->sum;
	 	  return rt;
	 }
	 int query(int left ,int right,int k,Node * rroot ,Node * lroot){
	 	     if(left ==right){
	 	     	return left;
	 	     }
	 	     int mid = (left +right )/2;
	 	     int s = rroot->l->sum - lroot->l->sum;
	 	    // cout << s << " "<<k<<"  "<<left << "  "<<right<<endl; 
	 	     if(s>=k){
	 	     	 return query(left,mid,k,rroot->l,lroot->l); 
	 	     }else{
	 	     	 return query(mid+1,right,k-s,rroot->r,lroot->r);
	 	     }
	 }
}T;
int main(){
    while(~scanf("%d%d",&n,&m)){
    	  mp.clear();
    	  for(int i=1;i<=n;i++){
    	       scanf("%d",&num[i]);
    	       mp[num[i]] =1; 
    	  }
    	  int tot = 0;
    	  for(it=mp.begin();it!= mp.end();it++){
    	  	   tot++ ;
    	  	   it->second = tot;
    	  	   idx[tot] = it->first;
    	  }
    	  T.init();
          for(int i =1;i<=n;i++){
               root[i] = T.update(mp[num[i]],1,n,root[i-1],1);	   
          }  	  
          for(int i =1;i<=m;i++){
          	  int a,b,k;
          	  scanf("%d%d%d",&a,&b,&k);
          	  int ans = T.query(1,n,k,root[b],root[a-1]);
          	  printf("%d
",idx[ans]);
          }
    }      
    return 0;
}