洛谷题单指南-线段树的进阶用法-P2617 Dynamic Rankings

原题链接：https://www.luogu.com.cn/problem/P2617

题意解读：动态求区间第k小问题。

解题思路：树套树的典型应用，具体阐述参考：https://www.cnblogs.com/jcwy/p/18640914

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;

struct Op
{
    char op;
    int l, r, k;
    int x, y;
} ops[N];

struct Node
{
    int L, R;
    int cnt;
} tr[N * 400];

int root[N], idx;
int a[N];
vector<int> b; //用于离散化
vector<int> tmpl, tmpr; //缓存查询的根节点
int n, m;

//获取x离散化之后的值
int lsh(int x)
{
    return lower_bound(b.begin(), b.end(), x) - b.begin() + 1;
}

int lowbit(int x)
{
    return x & -x;
}

void pushup(int u)
{
    tr[u].cnt = tr[tr[u].L].cnt + tr[tr[u].R].cnt;
}

//将根为u的线段树中值val的数量增加add
int update(int u, int l, int r, int val, int num)
{
    if(!u) u = ++idx;
    if(l == r)
    {
        tr[u].cnt += num;
        return u;
    }
    int mid = l + r >> 1;
    if(val <= mid) tr[u].L = update(tr[u].L, l, mid, val, num);
    else tr[u].R = update(tr[u].R, mid + 1, r, val, num);
    pushup(u);
    return u;
}

//在根为tmpr、tmpl的线段树查询第k小值
//左子树的元素数量=tmpr所有线段树左子树的元素数量-tmpl所有线段树左子树的元素数量
int query(int l, int r, int k)
{
    if(l == r) return l;
    int res = 0;
    for(int i = 0; i < tmpr.size(); i++) res += tr[tr[tmpr[i]].L].cnt;
    for(int i = 0; i < tmpl.size(); i++) res -= tr[tr[tmpl[i]].L].cnt;
    int mid = l + r >> 1;
    if(res >= k)
    {
        for(int i = 0; i < tmpr.size(); i++) tmpr[i] = tr[tmpr[i]].L;
        for(int i = 0; i < tmpl.size(); i++) tmpl[i] = tr[tmpl[i]].L;
        return query(l, mid, k);
    }
    else
    {
        for(int i = 0; i < tmpr.size(); i++) tmpr[i] = tr[tmpr[i]].R;
        for(int i = 0; i < tmpl.size(); i++) tmpl[i] = tr[tmpl[i]].R;
        return query(mid + 1, r, k - res);
    }
}

//利用树状数组将root[pos]~root[n]线段树中值val的数量加num
void add(int pos, int val, int num)
{
    for(int i = pos; i <= n; i += lowbit(i))
        root[i] = update(root[i], 1, b.size(), val, num);
}   

//利用树状数组在root[l]~root[r]线段树中查询第k小的值
int find_kth(int l, int r, int k)
{
    tmpr.clear();
    tmpl.clear();
    //缓存要查询的root[1]~root[r]的值涉及的线段树根节点
    for(int i = r; i; i -= lowbit(i)) tmpr.push_back(root[i]);
    //缓存要查询的root[1]~root[l-1]的值涉及的线段树根节点
    for(int i = l - 1; i; i -= lowbit(i)) tmpl.push_back(root[i]);
    return query(1, b.size(), k);
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        b.push_back(a[i]);
    }
    for(int i = 1; i <= m; i++)
    {
        cin >> ops[i].op;
        if(ops[i].op == 'Q') cin >> ops[i].l >> ops[i].r >> ops[i].k;
        else if(ops[i].op == 'C')
        {
            cin >> ops[i].x >> ops[i].y;
            b.push_back(ops[i].y);
        }
    }

    //排序，去重，用于离散化
    sort(b.begin(), b.end());
    b.erase(unique(b.begin(), b.end()), b.end());

    for(int i = 1; i <= n; i++) add(i, lsh(a[i]), 1);
    for(int i = 1; i <= m; i++)
    {
        if(ops[i].op == 'Q')
        {
            cout << b[find_kth(ops[i].l, ops[i].r, ops[i].k) - 1] << endl;
        }
        else if(ops[i].op == 'C')
        {
            add(ops[i].x, lsh(a[ops[i].x]), -1);
            a[ops[i].x] = ops[i].y;
            add(ops[i].x, lsh(a[ops[i].x]), 1);
        }
    }
}