最开始用指针写，交G++就MEL，交C++就AC。

（指针一时爽，一直指针一直爽）

后来写了伪指针的版本，又因为离散化出了问题无限WA，真实自闭题目。。。

这是伪指针式的，速度和内存都还是可以

#include <iostream>
#include <algorithm>

using namespace std;
const int MAXN = (int) 1e5 + 5;
int a[MAXN * 20], lson[MAXN * 20], rson[MAXN * 20];
int COUNTER = 0;

inline int newnode(int val) {
    a[++COUNTER] = val;
    lson[COUNTER] = rson[COUNTER] = 0;
    return COUNTER;
}

inline int newnode(int l, int r) {
    a[++COUNTER] = a[l] + a[r];
    lson[COUNTER] = l;
    rson[COUNTER] = r;
    return COUNTER;
}

int build(int tl, int tr) {
    if (tl > tr)return 0;
    if (tl == tr) return newnode(0);
    int tmid = (tl + tr) >> 1;
    return newnode(build(tl, tmid), build(tmid + 1, tr));
}

int add(int root, int pos, int tl = 0, int tr = MAXN) {
    if (tl == tr) return newnode(a[root] + 1);
    int tmid = (tl + tr) >> 1;
    if (tmid >= pos) { return newnode(add(lson[root], pos, tl, tmid), rson[root]); }
    else {
        return newnode(lson[root], add(rson[root], pos, tmid + 1, tr));
    }
}

int entry[MAXN], in[MAXN], inorder[MAXN];

int findKth(int index_l, int index_r, int k, int val_l = 0, int val_r = MAXN) {
    if (val_l == val_r)return val_l;
    int val_mid = (val_l + val_r) >> 1;
    int left = a[lson[index_r]] - a[lson[index_l]];
    if (left >= k) { return findKth(lson[index_l], lson[index_r], k, val_l, val_mid); }
    else {
        return findKth(rson[index_l], rson[index_r], k - left, val_mid + 1, val_r);
    }
}

int main() {
    int t;
    cin >> t;
    COUNTER = 0;
    entry[0] = build(0, MAXN);
    auto stmem = COUNTER;
    while (t--) {
        COUNTER = stmem;
        static int n, m;
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; ++i) {
            scanf("%d", in + i);
            inorder[i] = in[i];
        }
        sort(inorder, inorder + n);
        auto ed = unique(inorder, inorder + n);
        for (int i = 0; i < n; ++i) { entry[i + 1] = add(entry[i], lower_bound(inorder, ed, in[i]) - inorder); }
        for (int i = 0; i < m; ++i) {
            static int l, r, k;
            scanf("%d%d%d", &l, &r, &k);
            cout << inorder[findKth(entry[l - 1], entry[r], k)] << endl;
        }
    }
    return 0;
}

这个是最开始写的指针式的

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
const int MAXN = (int) 1e5 + 5;
const int UP = (int) 1e5 + 5;
int PTR_COUNTER = 0;

struct node {
    node *l, *r;
    int data;

    node() {}
} seg[MAXN * 20];

node *newnode() { return &seg[PTR_COUNTER++]; }

node *build(int l, int r) {
    if (l > r)return nullptr;
    if (l == r) {
        auto root = newnode();
        return root;
    }
    int mid = (l + r) >> 1;
    auto root = newnode();
    root->l = build(l, mid);
    root->r = build(mid + 1, r);
    return root;
}

int query(node *root, int tl, int tr, int l, int r) {
    if (tl > r || tr < l)return 0;
    if (tl >= l && tr <= r)return root->data;
    int tmid = (tl + tr) >> 1;
    return query(root->l, tl, tmid, l, r) + query(root->r, tmid + 1, tr, l, r);
}

node *update(node *root, int tl, int tr, int pos, int add_val) {
    if (tl == tr) {
        auto nrt = newnode();
        nrt->data = root->data + add_val;
        return nrt;
    }
    int tmid = (tl + tr) >> 1;
    auto nrt = newnode();
    if (tmid >= pos) {
        nrt->l = update(root->l, tl, tmid, pos, add_val);
        nrt->r = root->r;
        nrt->data = nrt->l->data + nrt->r->data;
    }
    else {
        nrt->l = root->l;
        nrt->r = update(root->r, tmid + 1, tr, pos, add_val);
        nrt->data = nrt->l->data + nrt->r->data;
    }
    return nrt;
}

node *entry[MAXN];

int findKth(int index_l, int index_r, int val_l, int val_r, int k) {
    if (val_l == val_r) return val_l;
    int val_mid = (val_l + val_r) >> 1;
    int _l = query(entry[index_l], 0, UP, val_l, val_mid), _r = query(entry[index_r], 0, UP, val_l, val_mid);
    int left = _r - _l;
    if (left >= k) { return findKth(index_l, index_r, val_l, val_mid, k); }
    else {
        return findKth(index_l, index_r, val_mid + 1, val_r, k - left);
    }
}

int main() {
    int t;
    scanf("%d", &t);
    auto root = build(0, UP);
    entry[0] = root;
    int rem = PTR_COUNTER;
    while (t--) {
        PTR_COUNTER = rem;
        static int n, m;
        scanf("%d%d", &n, &m);
        int in[MAXN], in_cpy[MAXN];
        for (int i = 0; i < n; ++i) {
            static int num;
            scanf("%d", &num);
            in[i] = num;
            in_cpy[i] = num;
        }
        sort(in, in + n);
        auto ed = unique(in, in + n);
        for (int i = 0; i < n; ++i) { entry[i + 1] = update(entry[i], 0, UP, lower_bound(in, ed, in_cpy[i]) - in, 1); }
        for (int i = 0; i < m; ++i) {
            static int l, r, k;
            scanf("%d%d%d", &l, &r, &k);
            --l;
            printf("%d\n", in[findKth(l, r, 0, UP, k)]);
        }
    }
    return 0;
}