自己想出來(lái)的，感覺(jué)要容易想到，使用可持久化線(xiàn)段樹(shù)，時(shí)間上要比y的慢一倍。大體思想就是，我們從小到大依次加入一個(gè)數(shù)，每加入一個(gè)就記錄一個(gè)版本，線(xiàn)段樹(shù)里記錄區(qū)間里數(shù)的數(shù)量，在查詢(xún)時(shí)，只要二分出區(qū)間數(shù)的數(shù)量大于等于k的最小版本即可，這個(gè)版本對(duì)應(yīng)插入的點(diǎn)就是要求的第 k 小點(diǎn)，時(shí)間復(fù)雜度是 $O(n{\log }^{2}n)$ 的和 y 是一個(gè)量級(jí)的，可能是由于常數(shù)問(wèn)題，所以運(yùn)行上要慢。
題目鏈接

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>using namespace std;const int N = 100010;int n, m;
int idx, root[N], cnt;
int g[N];struct node
{int v, id;bool operator<(const node &W)const{return v < W.v;}
}a[N];struct Node
{int l, r;int v, sum = 0;
}tr[N * 4 + N * (int)ceil(log2(N))];void pushup(int u)
{int &l = tr[u].l, &r = tr[u].r;tr[u].sum = tr[l].sum + tr[r].sum;
}int build(int l, int r)
{int p = ++ idx;if (l == r){tr[p].v = -0x3f3f3f3f;tr[p].sum = 0;return p;}int mid = l + r >> 1;tr[p].l = build(l, mid);tr[p].r = build(mid + 1, r);pushup(p);return p;
}int insert(int p, int l, int r, int x, int k)
{int q = ++ idx;tr[q] = tr[p];if (l == r){tr[q].v = k;if (k > -0x3f3f3f3f) tr[q].sum = 1;return q;}int mid = l + r >> 1;if (x <= mid) tr[q].l = insert(tr[p].l, l, mid, x, k);else tr[q].r = insert(tr[p].r, mid + 1, r, x, k);pushup(q);return q;
}int query(int p, int l, int r, int x, int y)
{if (x <= l && r <= y) return tr[p].sum;int mid = l + r >> 1;int sum = 0;if (x <= mid) sum += query(tr[p].l, l, mid, x, y);if (y > mid) sum += query(tr[p].r, mid + 1, r, x, y);return sum;
}bool check(int x, int l, int r, int k)
{return query(root[x], 1, n, l, r) >= k;
}int main()
{cin >> n >> m;root[0] = build(1, n);for (int i = 1; i <= n; i ++ ) {int x;scanf("%d", &x);a[i] = {x, i};g[i] = x;}sort(a + 1, a + n + 1);for (int i = 1; i <= n; i ++ ) {root[i] = insert(root[i - 1], 1, n, a[i].id, a[i].v);// cout << i << endl;}while (m -- ){int ls, rs, k;scanf("%d%d%d", &ls, &rs, &k);int l = 0, r = n, mid;while (l < r){mid = l + r >> 1;if (check(mid, ls, rs, k)) r = mid;else l = mid + 1;}printf("%d\n", a[l].v);}// cout << query(root[5], 1, n, 2, 5);return 0;}