AcWing 255. 第K小数
自己想出来的，感觉要容易想到，使用可持久化线段树，时间上要比y的慢一倍。大体思想就是，我们从小到大依次加入一个数，每加入一个就记录一个版本，线段树里记录区间里数的数量，在查询时，只要二分出区间数的数量大于等于k的最小版本即可，这个版本对应插入的点就是要求的第 k 小点，时间复杂度是 O ( n log 2 n ) O(n\log^2n) O(nlog2n) 的和 y 是一个量级的，可能是由于常数问题，所以运行上要慢。
题目链接
#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;}