一个静态主席树的模板

//#pragma comment(linker, "/STACK:1024000000,1024000000")
//#pragma GCC optimize(2)
#include <bits/stdc++.h>

using namespace std;
typedef double dou;
typedef long long ll;
typedef pair<int, int> pii;
typedef map<int, int> mii;

#define pai acos(-1.0)
#define M 4000005
#define inf 0x3f3f3f3f
#define mod 1000000007
#define IN inline
#define W(a) while(a)
#define lowbit(a) a&(-a)
#define left k<<1
#define right k<<1|1
#define lson L, mid, left
#define rson mid + 1, R, right
#define ms(a,b) memset(a,b,sizeof(a))
#define Abs(a) (a ^ (a >> 31)) - (a >> 31)
#define random(a,b) (rand()%(b+1-a)+a)
#define false_stdio ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

int n, m, cnt, Q;
int T[M], Ls[M], Rs[M], sum[M];
int init[M], num[M];

int Built(int L, int R) {
    int rt = ++cnt;
    if (L < R) {
        int mid = (L + R) >> 1;
        Ls[rt] = Built(L, mid);
        Rs[rt] = Built(mid + 1, R);
    }
    return rt;
}

int updata(int L, int R, int pre, int id) {
    int rt = ++cnt;
    Ls[rt] = Ls[pre], Rs[rt] = Rs[pre], sum[rt] = sum[pre] + 1;
    if (L < R) {
        int mid = (L + R) >> 1;
        if (id <= mid)Ls[rt] = updata(L, mid, Ls[pre], id);
        else Rs[rt] = updata(mid + 1, R, Rs[pre], id);
    }
    return rt;
}

int query(int u, int v, int L, int R, int k) {
    if (L == R)return L;
    int x = sum[Ls[v]] - sum[Ls[u]];
    int mid = (L + R) >> 1;
    if (x >= k)return query(Ls[u], Ls[v], L, mid, k);
    else return query(Rs[u], Rs[v], mid + 1, R, k - x);
}

int main() {
    false_stdio;

    cin >> n >> Q;
    for (int i = 1; i <= n; i++) {
        cin >> num[i];
        init[i] = num[i];
    }
    sort(init + 1, init + n + 1);
    m = unique(init + 1, init + n + 1) - init - 1;

    T[0] = Built(1, m);
    for (int i = 1; i <= n; i++) {
        int id = lower_bound(init + 1, init + m + 1, num[i]) - init;
        T[i] = updata(1, m, T[i - 1], id);
    }
    int l, r, k;
    for (int i = 1; i <= Q; i++) {
        cin >> l >> r >> k;
        cout << init[query(T[l - 1], T[r], 1, m, k)] << endl;
    }

    return 0;
}