Dynamic Rankings ZOJ - 2112 | 动态区间第k大->主席树 + 树状数组

题意：

分析：
-used数组存储接下来树状数组求和要用到的结点编号
代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//typedef __int128 lll;
#define print(i) cout << "debug: " << i << endl
#define close() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define mem(a, b) memset(a, b, sizeof(a))
const ll mod = 1e9 + 7;
const int maxn = 1e5;
const int inf = 0x3f3f3f3f;
struct node
{
    int lson, rson, num;
}t[maxn << 6];
struct node1
{
    int kind;
    int l, r, k;
    int pos, val;
}buf[maxn];
int n, q;
int root[maxn], tot, num;
int v[maxn], sorted[maxn];
int used[maxn], groot[maxn];

void init()
{
    tot = 0;
}
int getid(int x)
{
    return lower_bound(sorted + 1, sorted + 1 + num, x) - sorted;
}

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

int build(int l, int r)
{
    int tar = tot++;
    t[tar].num = 0;
    if(l < r)
    {
        int mid = l + r >> 1;
        t[tar].lson = build(l, mid), t[tar].rson = build(mid + 1, r);
    }
    return tar;
}

int update(int pre, int val, int num, int l, int r)
{
    int tar = tot++;
    t[tar] = t[pre], t[tar].num += num;
    if(l < r)
    {
        int mid = l + r >> 1;
        if(val <= mid) t[tar].lson = update(t[pre].lson, val, num, l, mid);
        else t[tar].rson = update(t[pre].rson, val, num, mid + 1, r);
    }
    return tar;
}

int update1(int pos, int val)
{
    for(int i = pos; i <= n; i += lowbit(i)) groot[i] = update(groot[i], getid(v[pos]), -1, 1, num);
    for(int i = pos; i <= n; i += lowbit(i)) groot[i] = update(groot[i], getid(val), 1, 1, num);
    v[pos] = val;
}

int query(int gl, int gr, int pre, int tar, int k, int l, int r)
{
    if(l == r) return l;
    int res = t[t[tar].lson].num - t[t[pre].lson].num;
    for(int i = gr; i >= 1; i -= lowbit(i)) res += t[t[used[i]].lson].num;
    for(int i = gl; i >= 1; i -= lowbit(i)) res -= t[t[used[i]].lson].num;
    int mid = l + r >> 1;
    if(res >= k)
    {
        for(int i = gr; i >= 1; i -= lowbit(i)) used[i] = t[used[i]].lson;
        for(int i = gl; i >= 1; i -= lowbit(i)) used[i] = t[used[i]].lson;
        return query(gl, gr, t[pre].lson, t[tar].lson, k, l, mid);
    }
    else
    {
        for(int i = gr; i >= 1; i-= lowbit(i)) used[i] = t[used[i]].rson;
        for(int i = gl; i >= 1; i -= lowbit(i)) used[i] = t[used[i]].rson;
        return query(gl, gr, t[pre].rson, t[tar].rson, k - res, mid + 1, r);
    }
}

int main()
{
   int t; cin >> t;
   while(t--)
   {
       init();
       cin >> n >> q;
       for(int i = 1; i <= n; i++) cin >> v[i], sorted[i] = v[i];
       int cnt = n;
       for(int i = 1; i <= q; i++)
       {
           char ope[10]; cin >> ope;
           if(ope[0] == 'Q')
           {
               buf[i].kind = 0;
               cin >> buf[i].l >> buf[i].r >> buf[i].k;
           }
           else
           {
               buf[i].kind = 1;
               cin >> buf[i].pos >> buf[i].val;
               sorted[++cnt] = buf[i].val;
           }
       }
       sort(sorted + 1, sorted + 1 + cnt);
       num = unique(sorted + 1, sorted + 1 + cnt) - sorted - 1;
       root[0] = build(1, num);
       for(int i = 1; i <= n; i++) root[i] = update(root[i - 1], getid(v[i]), 1, 1, num);
       for(int i = 1; i <= n; i++) groot[i] = root[0];
       for(int i = 1; i <= q; i++)
       {
           if(buf[i].kind == 0)
           {
               for(int j = buf[i].l - 1; j >= 1; j -= lowbit(j)) used[j] = groot[j];
               for(int j = buf[i].r; j >= 1; j -= lowbit(j)) used[j] = groot[j];
               int res = query(buf[i].l - 1, buf[i].r, root[buf[i].l - 1], root[buf[i].r], buf[i].k, 1, num);
               cout << sorted[res] << endl;
           }
           else
           {
               update1(buf[i].pos, buf[i].val);
           }
       }
   }
}