ZOJ 2112 Dynamic Rankings（树状数组套主席树可修改区间第k小）题解

古城微笑少年丶 2021-12-20 04:53 214阅读 0赞

题意：求区间第k小，节点可修改

思路：如果直接用静态第k小去做，显然我更改一个节点后，后面的树都要改，这个复杂度太高。那么我们想到树状数组思路，树状数组是求前缀和，那么我们可以用树状数组套主席树，求出权值线段树前缀和，相减就是区间前缀和。而且我维护也只要改logn棵树就好了。具体看[JQ博客][JQ]。

代码：

#include<cmath>
    #include<set>
    #include<map>
    #include<queue>
    #include<cstdio>
    #include<vector>
    #include<cstring>
    #include <iostream>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    typedef unsigned long long ull;
    const int maxn = 5e4 + 10;
    const int M = maxn * 30;
    const ull seed = 131;
    const int INF = 0x3f3f3f3f;
    const int MOD = 1000000007;
    int a[maxn], root[maxn], tot;
    int sroot[maxn];    //树状数组的头
    int use[maxn];  //保存树状数组的头
    int n, m, L, R;
    vector<int> vv;
    struct node{
        int lson, rson;
        int sum;
    }T[maxn * 40];
    struct Que{
        int order;
        int l, r, k;
    }q[maxn];
    void init(){
        memset(T, 0, sizeof(T));
        memset(sroot, 0, sizeof(root));
        tot = 0;
        vv.clear();
    }
    int lowbit(int x){
        return x&(-x);
    }
    int getId(int x){
        return lower_bound(vv.begin(), vv.end(),x) - vv.begin() + 1;
    }
    void update(int l, int r, int &now, int pre, int v, int pos){
        T[++tot] = T[pre], T[tot].sum += v, now = tot;
        if(l == r) return;
        int m = (l + r) >> 1;
        if(pos <= m)
            update(l, m, T[now].lson, T[pre].lson, v, pos);
        else
            update(m + 1, r, T[now].rson, T[pre].rson, v, pos);
    }
    int add(int x, int v, int pos){
        for(int i = x; i <= n; i += lowbit(i)){
            update(1, vv.size(), sroot[i], sroot[i], v, pos);
        }
    }
    int SUM(int pos){
        int ret = 0;
        for(int i = pos; i > 0; i -= lowbit(i))
            ret += T[T[use[i]].lson].sum;
        return ret;
    }
    
    int query(int l, int r, int now, int pre, int k){
        if(l == r) return l;
        int sum = SUM(R) - SUM(L) + T[T[now].lson].sum - T[T[pre].lson].sum;
        int m = (l + r) >> 1;
        if(sum >= k){
            for(int i = R; i > 0; i -= lowbit(i)) use[i] = T[use[i]].lson;
            for(int i = L; i > 0; i -= lowbit(i)) use[i] = T[use[i]].lson;
            return query(l, m, T[now].lson, T[pre].lson, k);
        }
        else{
            for(int i = R; i > 0; i -= lowbit(i)) use[i] = T[use[i]].rson;
            for(int i = L; i > 0; i -= lowbit(i)) use[i] = T[use[i]].rson;
            return query(m + 1, r, T[now].rson, T[pre].rson, k - sum);
        }
    }
    
    int main(){
        int T;
        scanf("%d", &T);
        while(T--){
            init();
            scanf("%d%d", &n, &m);
            for(int i = 1; i <= n; i++){
                scanf("%d", &a[i]);
                vv.push_back(a[i]);
            }
            for(int i = 1; i <= m; i++){
                char o[5];
                scanf("%s", o);
                if(o[0] == 'Q'){
                    q[i].order = 0;
                    scanf("%d%d%d", &q[i].l, &q[i].r, &q[i].k);
                }
                else{
                    q[i].order = 1;
                    scanf("%d%d", &q[i].l, &q[i].k);
                    vv.push_back(q[i].k);
                }
            }
    
            sort(vv.begin(), vv.end());
            vv.erase(unique(vv.begin(), vv.end()), vv.end());
    
            for(int i = 1; i <= n; i++){
                update(1, vv.size(), root[i], root[i - 1], 1, getId(a[i]));
            }
            for(int i = 1; i <= m; i++){
                if(q[i].order == 0){
                    L = q[i].l - 1, R = q[i].r;
                    for(int j = R; j > 0; j -= lowbit(j)) use[j] = sroot[j];
                    for(int j = L; j > 0; j -= lowbit(j)) use[j] = sroot[j];
                    printf("%d\n", vv[query(1, vv.size(), root[R], root[L], q[i].k) - 1]);
                }
                else{
                    add(q[i].l, -1, getId(a[q[i].l]));
                    a[q[i].l] = q[i].k;
                    add(q[i].l, 1, getId(a[q[i].l]));
                }
            }
        }
        return 0;
    }

转载于:https://www.cnblogs.com/KirinSB/p/10766853.html

[JQ]: https://www.cnblogs.com/Jiaaaaaaaqi/p/10129249.html