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;
}