#include <bits/stdc++.h>
using namespace std ;
#define N 200010
int n , m , rt[N] , len , ins[N] , a[N] , newpos ;
struct node {
int ls , rs , sum ;
};
node t[N << 5] ;
inline int alls (const int &x) {
return lower_bound (ins + 1 , ins + 1 + len , x) - ins ;
}
inline void pushup (int u) {
t[u].sum = t[t[u].ls].sum + t[t[u].rs].sum ;
}
#define MID(l , r) (l + r) >> 1 ;
int build (int l , int r) {
int u = ++newpos ;
if (l == r) {
t[u].sum = 0 ;
return u ;
}
int mid = MID (l , r) ;
t[u].ls = build (l , mid) ;
t[u].rs = build (mid + 1 , r) ;
pushup (u) ;
return u ;
}
int update (int k , int l ,int r , int root , int val) {
int u = ++ newpos ;
t[u] = t[root] ;
int mid = MID (l , r) ;
if (l == k && r == k) {
t[u].sum += val ;
return u ;
}
// int mid = MID (l , r) ;
if (k <= mid) t[u].ls = update (k , l , mid , t[u].ls , val) ;
else t[u].rs = update (k , mid + 1 , r , t[u].rs , val) ;
pushup (u) ;
return u ;
}
int getans (int u , int v , int l , int r , int k) {
if (l == r) return l ;
int mid = MID (l , r) ;
int x = t[t[v].ls].sum - t[t[u].ls].sum ;
if (k <= x) return getans (t[u].ls , t[v].ls , l , mid , k) ;
else return getans (t[u].rs , t[v].rs , mid + 1 , r , k - x) ;
}
int main () {
cin >> n >> m ;
for (int i = 1 ; i <= n ; i++) cin >> a[i] ;
memcpy (ins , a , sizeof ins) ;
sort (ins + 1 , ins + n + 1) ;
len = unique (ins + 1 , ins + 1 + n) - ins - 1 ;
rt[0] = build (1 , len) ;
// cout << rt[0] << endl ;
for (int i = 1 ; i <= n ; i ++) {
rt[i] = update (alls(a[i]) , 1 , len , rt[i - 1] , 1) ;
}
// for (int i = 1 ; i <= n ; i ++) cout << rt[i] << endl ;
while (m--) {
int l , r , k ;
cin >> l >> r >> k ;
cout << ins[getans (rt[l - 1] , rt[r] , 1 , len , k) ] << endl ;
}
return 0 ;
}
作为我最喜欢的数据结构 , 之前本想写个分享 , 但是mrk带佬写的 太强了
第k小数。。。