题目

代码

#include <bits/stdc++.h>
using namespace std;const int N = 1e5 + 10;int a[N], b[N];
int n, m, len;
int rt[N], idx; // idx 是点分配器struct node
{int l, r;int s;
} tr[N * 22];int getw(int x)
{return lower_bound(b + 1, b + len + 1, x) - b;
}int build(int l, int r)
{int p = ++idx;tr[p].s = 0; // 初始化 sif (l < r){int mid = l + r >> 1;tr[p].l = build(l, mid);tr[p].r = build(mid + 1, r);}return p;
}int insert(int x, int l, int r, int v)
{int p = ++idx;tr[p] = tr[x];tr[p].s++; // 更新 sif (l < r){int mid = l + r >> 1;if (v <= mid) tr[p].l = insert(tr[x].l, l, mid, v);else tr[p].r = insert(tr[x].r, mid + 1, r, v);}return p;
}int query(int x, int y, int l, int r, int k)
{if (l == r) return l;int mid = l + r >> 1;int s = tr[tr[x].l].s - tr[tr[y].l].s; // 左子树的节点数if (k <= s) return query(tr[x].l, tr[y].l, l, mid, k);else return query(tr[x].r, tr[y].r, mid + 1, r, k - s);
}int main()
{scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++)scanf("%d", &a[i]), b[i] = a[i];sort(b + 1, b + n + 1);len = unique(b + 1, b + n + 1) - b - 1; // 初始化全局变量 lenrt[0] = build(1, len); // 使用 len 作为区间范围for (int i = 1; i <= n; i++)rt[i] = insert(rt[i - 1], 1, len, getw(a[i])); // 更新 rt[i]while (m--){int l, r, k;scanf("%d%d%d", &l, &r, &k);printf("%d\n", b[query(rt[r], rt[l - 1], 1, len, k)]); // 映射回 b，相对大小(位置)映射回实际大小}return 0;
}