其实不用离散化的，因为主席树的空间为：O(nlog(L))(L为维护的区间长度)，L最大2^63次也能在30MB以内

如果忘了，那就再看一遍吧
https://www.bilibili.com/video/BV1mg4y1d7he/?spm_id_from=333.1387.search.video_card.click&vd_source=406c9c8949c7ee3523a9638f9d224a73
Y总版本

//太好了，炜神只用了1.14514秒就完成了这题，我又双叒叕可以copyyyyyy了
#pragma GCC optimize(3)

#include<bits/stdc++.h>

#define fi first
#define se second
#define lc p << 1
#define rc p << 1 | 1
#define lowbit(x) x & -x
#define inv(x) qmi(x, P - 2)

using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef pair<db, db> pdd;
const int N = 2e5 + 10, M = 2 * N;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f;
const double PI = 3.141592653589793;
const int dx[] = {-1, 0, 1, 1, 1, 0, -1, -1};
const int dy[] = {1, 1, 1, 0, -1, -1, -1, 0};//奇数位置是上下左右
const int P = 998244353;

int T = 1;
ll primes[N], p_vis[N], p_cnt = 1;
ll fact[N];

struct node{
    int l, r;
    int cnt;//这里的cnt维护的是：区间内数的出现次数之和
}SegTree[N * 4 * 20];

int root[N], idx;

void normalMath_init(){
    fact[0] = 1;
    for(int i = 1; i < N; i ++) fact[i] = fact[i - 1] * i % P;

    p_vis[0] = p_vis[1] = -1;
    for(int i = 2; i < N; i ++){
        if(!p_vis[i]) primes[p_cnt ++] = i;
        for(int j = 1; primes[j] * i < N; j ++){
            p_vis[i * primes[j]] = 1;
            if(i % primes[j] == 0) break;
        }
    }
}

ll qmi(ll a, ll b){
    ll res = 1;
    while(b){
        if(b & 1) res = res * a % P;
        b >>= 1;
        a = a * a % P;
    }
    return res;
}

ll C(ll b, ll a){
    return fact[b] * inv(fact[a]) % P * inv(fact[b - a]) % P;
}

ll gcd(ll a, ll b){
    return b ? gcd(b, a % b) : a; 
} 

void solve(){
    ll n, q;
    cin >> n >> q;

    vector<ll> a(n + 10), b;//b是离散化后的数组
    for(int i = 1; i <= n; i ++) cin >> a[i], b.push_back(a[i]);
    sort(b.begin(), b.end());
    b.erase(unique(b.begin(), b.end()), b.end());
    int m = b.size() - 1;

    function<void(int &)> pushup = [&](int &p) -> void{
        int l = SegTree[p].l, r = SegTree[p].r;
        SegTree[p].cnt = SegTree[l].cnt + SegTree[r].cnt;
    };
    //动态建树（也就是指针建树，l和r存的是子树的节点编号）
    function<int(int, int)> build = [&](int l, int r) -> int{
        int p = ++ idx;  
        int mid = l + r >> 1;
        if(l == r) return p;
        SegTree[p].l = build(l, mid), SegTree[p].r = build(mid + 1, r);
        return p;
    };
    //插入操作
    function<int(int, int, int, int)> ist = [&](int p, int l, int r, int x) -> int{
        int q = ++ idx;//新插入一个点
        SegTree[q] = SegTree[p];//复制上个版本的点
        if(l == r){
            SegTree[q].cnt ++;
            return q;
        }
        int mid = l + r >> 1;
        if(x <= mid) SegTree[q].l = ist(SegTree[p].l, l, mid, x);//递归左边
        else SegTree[q].r = ist(SegTree[p].r, mid + 1, r, x);//递归右边
        pushup(q);//更新父亲
        return q;
    };

    function<int(int, int, int, int, int)> qurry = [&](int q, int p, int l, int r, int k) -> int{
        if(l == r) return l;
        //查询左边区间内，
        int cnt = SegTree[SegTree[q].l].cnt - SegTree[SegTree[p].l].cnt;
        int mid = l + r >> 1;
        //如果左边出现的数字之和 >= k，答案一定在左边
        //否则，答案就是右边 k - cnt 小的数字
        if(cnt >= k) return qurry(SegTree[q].l, SegTree[p].l, l, mid, k);
        else return qurry(SegTree[q].r, SegTree[p].r, mid + 1, r, k - cnt);
    };

    function<ll(ll)> hs = [&](ll x) -> ll{
        return lower_bound(b.begin(), b.end(), x) - b.begin();  
    };

    root[0] = build(0, m);
    for(int i = 1; i <= n; i ++){
        root[i] = ist(root[i - 1], 0, m, hs(a[i]));
    }
    while(q --){
        int l, r, k;
        cin >> l >> r >> k;
        cout << b[qurry(root[r], root[l - 1], 0, m, k)] << '\n';
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    normalMath_init();
    //cin >> T;
    while(T --){
        solve();
    }
    return 0;
}   

蒟蒻版本

//太好了，炜神只用了1.14514秒就完成了这题，我又双叒叕可以copyyyyyy了
#pragma GCC optimize(3)

#include<bits/stdc++.h>

#define fi first
#define se second
#define lc p << 1
#define rc p << 1 | 1
#define lowbit(x) x & -x
#define inv(x) qmi(x, P - 2)

using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef pair<db, db> pdd;
const int N = 1e5 + 10, M = 2 * N;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f;
const double PI = 3.141592653589793;
const int dx[] = {-1, 0, 1, 1, 1, 0, -1, -1};
const int dy[] = {1, 1, 1, 0, -1, -1, -1, 0};//奇数位置是上下左右
const int P = 998244353;

int T = 1;
ll primes[N], p_vis[N], p_cnt = 1;
ll fact[N];

struct SegTree{
    int ls, rs, cnt;
}tr[N * 40];
int root[N], idx;

void build(int &p, int l, ll r){
    p = ++ idx;
    if(l == r) return;
    int mid = l + r >> 1;
    build(tr[p].ls, l, mid), build(tr[p].rs, mid + 1, r);
}

void ist(int &q, int p, ll l, ll r, ll x){
    q = ++ idx, tr[q] = tr[p], tr[q].cnt ++;
    if(l == r) return;
    int mid = l + r >> 1;
    if(x <= mid) ist(tr[q].ls, tr[p].ls, l, mid, x);
    else ist(tr[q].rs, tr[p].rs, mid + 1, r, x);
}

int qurry(int q, int p, ll l, ll r, int k){
    if(l == r) return l;
    int mid = l + r >> 1, s = tr[tr[q].ls].cnt - tr[tr[p].ls].cnt;
    if(s >= k) return qurry(tr[q].ls, tr[p].ls, l, mid, k);
    else return qurry(tr[q].rs, tr[p].rs, mid + 1, r, k - s);
}

void normalMath_init(){
    fact[0] = 1;
    for(int i = 1; i < N; i ++) fact[i] = fact[i - 1] * i % P;

    p_vis[0] = p_vis[1] = -1;
    for(int i = 2; i < N; i ++){
        if(!p_vis[i]) primes[p_cnt ++] = i;
        for(int j = 1; primes[j] * i < N; j ++){
            p_vis[i * primes[j]] = 1;
            if(i % primes[j] == 0) break;
        }
    }
}

ll qmi(ll a, ll b){
    ll res = 1;
    while(b){
        if(b & 1) res = res * a % P;
        b >>= 1;
        a = a * a % P;
    }
    return res;
}

ll C(ll b, ll a){
    return fact[b] * inv(fact[a]) % P * inv(fact[b - a]) % P;
}

ll gcd(ll a, ll b){
    return b ? gcd(b, a % b) : a; 
} 

void solve(){
    ll n, q;
    cin >> n >> q;
    vector<ll> a(n + 10);
    //因为存在负数，所以我们让所有数加个偏移量即可，最后减去偏移量
    for(int i = 1; i <= n; i ++) cin >> a[i], a[i] += inf;
    for(int i = 1; i <= n; i ++) ist(root[i], root[i - 1], 1, 2ll * inf, a[i]);

    while(q --){
        int l, r, k;
        cin >> l >> r >> k;
        cout << qurry(root[r], root[l - 1], 1, 2 * inf, k) - inf << '\n';
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    normalMath_init();
    //cin >> T;
    while(T --){
        solve();
    }
    return 0;
}