本文共 2831 字，大约阅读时间需要 9 分钟。

1175 区间中第K大的数

一个长度为N的整数序列，编号0 - N - 1。进行Q次查询，查询编号i至j的所有数中，第K大的数是多少。

输出

共Q行，对应每一个查询区间中第K大的数。

输入样例

5

输出样例

7

代码实现

下面代码是求第k小的模板修改而来的。

#include
   
    using namespace std;const int N = 200000 + 5;int n, m, size, cnt = 0;int w[N];//用于记录原数组int s[N];//用于记录去重排序后数组int rk[N];//用于记录原数组的元素是第几小int root[N];//用于记录每个根节点的编号// 主席树struct President_tree {
       // ls,rs分别记录一个节点的左右儿子编号,sum记录经过该节点的次数    int ls, rs, sum;} t[N * 20];inline int read() {
       int x = 0;    int flagK = 1;    char c = getchar();    while (!isdigit(c)) {
           if (c == '-')flagK = -1;        c = getchar();    }    while (isdigit(c)) {
           x = x * 10 + c - '0';        c = getchar();    }    x *= flagK;    return x;}void build(int &node, int l, int r) {
       // 建一颗空树(虽然不建也没什么关系)    node = ++cnt;    if (l == r) return;    int mid = (l + r >> 1);    build(t[node].ls, l, mid);    build(t[node].rs, mid + 1, r);}void updata(int &node, int last, int l, int r, int s) {
       node = ++cnt;    t[node] = t[last];    // 通过上一次修改的值来修改    ++t[node].sum;    if (l == r) return;    int mid = (l + r >> 1);    if (s <= mid) {
           // 如果最后要插到叶子节点的位置在mid左边,就往左插        updata(t[node].ls, t[last].ls, l, mid, s);    } else {
           // 同理        updata(t[node].rs, t[last].rs, mid + 1, r, s);    }}int query(int node, int last, int l, int r, int k) {
       if (l == r) {
           //查询到了叶子节点时,就找到了是在去重排序后序列中第L位置的值        return s[l];    }    // 类似于splay的查询第k大    int sum = t[t[node].ls].sum - t[t[last].ls].sum, mid = (l + r >> 1);    if (k <= sum) {
           return query(t[node].ls, t[last].ls, l, mid, k);    } else {
           return query(t[node].rs, t[last].rs, mid + 1, r, k - sum);    }}int main() {
       int x, y, k;    n = read();    for (int i = 1; i <= n; i++) {
           w[i] = read();    }    memcpy(s, w, sizeof(s));    sort(s + 1, s + n + 1);    // unique可以将数组去重,因为unique返回的是一个地址,而数组以1开始,所以排序后的数组大小为这个值    size = unique(s + 1, s + n + 1) - s - 1;    build(root[0], 1, size);    // 处理每个数字是第几小,要在已经去重后的s数组中查找    for (int i = 1; i <= n; i++) {
           rk[i] = lower_bound(s + 1, s + size + 1, w[i]) - s;    }    for (int i = 1; i <= n; i++) {
           // 将每次修改后的线段树存下来,以根节点来找整棵树        updata(root[i], root[i - 1], 1, size, rk[i]);    }    m = read();    for (int i = 1; i <= m; i++) {
           // x y 的正常区间为 1到n        x = read();        y = read();        k = read();        // 当求最大且区间为 0到n-1 时需要这样改        k = y - x + 2 - k;        x++, y++;        printf("%d\n", query(root[y], root[x - 1], 1, size, k));    }    return 0;}
   

转载地址：https://blog.csdn.net/weixin_43820352/article/details/111238142 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！