1901. Zju2112 Dynamic Rankings 樹狀數組套主席樹 模闆

😊 | Powered By HeartFireY

Problem Analysis

草草看了一眼題目，差點以為是可持久化線段樹的裸闆子。于是就回顧了以下可持久化線段樹和主席樹的基本操作，與本題目進行對比：

可持久化線段樹支援的操作是

1. 在某個曆史版本上修改某一個位置上的值
2. 通路某個曆史版本的某一位置上的值

主席樹的作用則主要是查詢區間第小的值，這是得益于其基于權值數組建立可持久化線段樹的效果。是以他的每次區間更新都會産生一個新的根節點。産生新的根節點的原因是主席樹利用了字首和的思想，維護區間起點到某個節點的資訊，利用滿足區間可加性資訊維護的性質查詢區間資訊。是以它隻能查詢靜态區間資訊。

那麼本題目顯然是屬于查詢動态區間第小的問題。

那麼我們就需要通過一些特殊的解決方式來處理這類問題：樹套樹結構。

我們使用樹套樹的基本思想是，不同的工作交給不同的資料結構來完成：主席樹仍然負責解決區間第小的問題，樹狀數組則負責解決區間修改的問題。

那麼怎麼實作呢？

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

const int N = 1e4 + 10, maxn = 1000000000;


int a[N], n, m;
int root[N], lc[N << 8], rc[N << 8], sum[N << 8], num;
int L[N], R[N], cnt1, cnt2;

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

void update(int &rt, int l,int r, int x, int v){
    if(!rt) rt = ++num;
    sum[rt] += v;
    if(l == r) return;
    int mid = l + r >> 1;
    if(x <= mid) update(lc[rt], l, mid, x, v);
    else update(rc[rt], mid + 1, r, x, v);
}

int query(int l, int r, int k){
    if(l == r) return l;
    int cur = 0, mid = l + r >> 1;
    for(int i = 1; i <= cnt1; i++) cur -= sum[lc[L[i]]];
    for(int i = 1; i <= cnt2; i++) cur += sum[lc[R[i]]];
    if(cur >= k){
        for(int i = 1; i <= cnt1; i++) L[i] = lc[L[i]];
        for(int i = 1; i <= cnt2; i++) R[i] = lc[R[i]];
        return query(l, mid, k);
    }
    else{
        for(int i = 1; i <= cnt1; i++) L[i] = rc[L[i]];
        for(int i = 1; i <= cnt2; i++) R[i] = rc[R[i]];
        return query(mid + 1, r, k - cur);
    }
}

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        for(int j = i; j <= n; j += lowbit(j)) update(root[j], 0, maxn, a[i], 1);
    }
    for(int i = 1; i <= m; i++){
        char op;
        int u, v, k;
        cin >> op >> u >> v;
        if(op == 'Q'){
            cin >> k;
            cnt1 = cnt2 = 0;
            for(int i = u - 1; i; i -= lowbit(i)) L[++cnt1] = root[i];
            for(int i = v; i; i -= lowbit(i)) R[++cnt2] = root[i];
            cout << query(0, maxn, k) << endl;
        }
        else{
            for(int i = u; i <= n; i += lowbit(i)) update(root[i], 0, maxn, a[u], -1);
            a[u] = v;
            for(int i = u; i <= n; i += lowbit(i)) update(root[i], 0, maxn, a[u], 1);
        }
    }
    return 0;
}