Luogu P2617 Dynamic Rankings

带修主席树的模板，因为状态不好所以敲了很长时间，不过写完感觉能更好地理解主席树了。

核心其实就是树状数组套主席树，维护方法不再是以前的那种一步一修改，而是对于树状数组上的每一个点建立一棵权值线段树，然后一点一点地维护。这样就从朴素修改后缀所需要的每次\(O(NlogN)\)的复杂度，变成了修改\(log\)棵树所需要的\(O(Nlog^2N)\)。

几个注意事项：

1. 本题卡常。请使用离散化后的权值进行建树。

2. 本题卡常。不要用\(cin\)。

3. 因为是权值线段树，所以要先删除再添加。

4. 二分的时候也要带上全家桶（\(lowbit\)对应位）一起修改鸭~

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

const int N = 100010;
int INF = 1000000010;

int tot, rt[N];

int n, m, arr[N];

#define mid ((l + r) >> 1)
#define lowbit(x) (x & -x)

struct Segment_Tree {
    struct Segment_Node {
        int ls, rs, sz;
    }t[N << 9];
    
    Segment_Tree () {t[0].sz = 0;}
    
    void modify (int &v, int l, int r, int w, int del) {
        if (v == 0) v = ++tot; 
        t[v].sz += del;
        if (l != r) {
            if (w <= mid) {
                modify (t[v].ls, l, mid + 0, w, del);
            } else {
                modify (t[v].rs, mid + 1, r, w, del);
            }
        }
    } 
}seg;

int cnt, sep[N << 1];

int _sep (int w) {
    return lower_bound (sep + 1, sep + 1 + cnt, w) - sep;
}

void change (int pos, int val) {
    for (int i = pos; i <= n; i += lowbit (i)) {
        seg.modify (rt[i], 0, INF, _sep (arr[pos]), -1);
    }
    arr[pos] = sep[val];
    for (int i = pos; i <= n; i += lowbit (i)) {
        seg.modify (rt[i], 0, INF, _sep (arr[pos]), +1);
    }   
}

int query (int u, int v, int k) {
    static int _u[30], _v[30];
    // u 到 v 区间第 k 小
    int l = 0, r = INF; 
    _u[0] = _v[0] = 0;
    for (int i = u; i != 0; i -= lowbit (i)) _u[++_u[0]] = rt[i];
    for (int i = v; i != 0; i -= lowbit (i)) _v[++_v[0]] = rt[i];
    while (l < r) {
        int lch = 0;
        for (int i = 1; i <= _u[0]; ++i) lch -= seg.t[seg.t[_u[i]].ls].sz;
        for (int i = 1; i <= _v[0]; ++i) lch += seg.t[seg.t[_v[i]].ls].sz;
        if (k <= lch) {
            for (int i = 1; i <= _u[0]; ++i) _u[i] = seg.t[_u[i]].ls;
            for (int i = 1; i <= _v[0]; ++i) _v[i] = seg.t[_v[i]].ls;
            r = mid;
        } else {
            for (int i = 1; i <= _u[0]; ++i) _u[i] = seg.t[_u[i]].rs;
            for (int i = 1; i <= _v[0]; ++i) _v[i] = seg.t[_v[i]].rs;
            l = mid + 1;
            k -= lch;
        }
    }
    return r;
}

struct Query {
    int type, l, r, k, p, w;
}q[N];

int main () {
//  cin >> n >> m;
    scanf ("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf ("%d", &arr[i]);
        sep[++cnt] = arr[i];
    }
    for (int i = 1; i <= m; ++i) {
        static char opt[10];
        scanf ("%s", opt);  
        if (opt[0] == 'Q') {
            q[i].type = 0;
            scanf ("%d %d %d", &q[i].l, &q[i].r, &q[i].k);
        } else {
            q[i].type = 1;
            scanf ("%d %d", &q[i].p, &q[i].w);
            sep[++cnt] = q[i].w;
        }
    }
    sort (sep + 1, sep + 1 + cnt);
    cnt = unique (sep + 1, sep + 1 + cnt) - sep - 1; INF = cnt;
    for (int i = 1; i <= n; ++i) {
        for (int j = i; j <= n; j += lowbit (j)) {
            seg.modify (rt[j], 0, INF, _sep (arr[i]), +1);
        }
    } 
    for (int i = 1; i <= m; ++i) {
        if (q[i].type == 0) {
            printf ("%d\n", sep[query (q[i].l - 1, q[i].r, q[i].k)]);
        } else {
            change (q[i].p, _sep (q[i].w)); 
            
        }
    }
}

Luogu P2617 Dynamic Rankings

原文：https://www.cnblogs.com/maomao9173/p/10533634.html