BZOJ 1901: Dynamic Rankings – [树套树/主席树][模板]


题目传送门(BZOJ)
>原文链接<

题解 :

带修主席树模板

维护一个数据结构, 支持单点修改, 区间查询K大.

区间第K大可以方便的用主席树维护, 但是若要改某个版本的主席树, 则其后面所有的主席树都要做此修改.

利用树状数组维护前缀的性质, 把要修的x及其在树状数组后面的点一起扔到数组里, 从上到下一起更新.

对于查询, 把l-1r的在树状数组中的点都扔到树状数组里, 每层用\sum\limits_i t[r[i]]-\sum\limits_j t[l-1[j]]来判断当前权值线段树左儿子权值和, 按照一般的方法去选择递归左右子树, 选择之后把所有的当前点都置成其对应的ls/rs.

代码 :

#include 
#include 
#include 
#include 
#define mid ((l+r)/2)
using namespace std;
const int N = 120000;
const int INF = 1e9;
int t[N*50], ls[N*50], rs[N*50], root[N];
int ax[N], ay[N], a[N], n, m;
void insert(int l, int r, int &x, int y, int pos, int c) {
    static int _ = 0;
    if(!x) x = ++_;
    if(l == r) return t[x] = t[y]+c, void();
    if(pos <= mid) rs[x] = rs[y], insert(l, mid, ls[x], ls[y], pos, c);
    else ls[x] = ls[y], insert(mid+1, r, rs[x], rs[y], pos, c);
    t[x] = t[ls[x]] + t[rs[x]];
}
int query(int l, int r, int k) {
    if(l == r) return l;
    int sizl = 0;
    for(int i = 1; i <= *ay; i ++ ) sizl += t[ls[ay[i]]];
    for(int i = 1; i <= *ax; i ++ ) sizl -= t[ls[ax[i]]];
    if(k <= sizl) {
        for(int i = 1; i <= *ay; i ++ ) ay[i] = ls[ay[i]];
        for(int i = 1; i <= *ax; i ++ ) ax[i] = ls[ax[i]];
        return query(l, mid, k);
    }
    else {
        for(int i = 1; i <= *ay; i ++ ) ay[i] = rs[ay[i]];
        for(int i = 1; i <= *ax; i ++ ) ax[i] = rs[ax[i]];
        return query(mid+1, r, k-sizl);
    }
}
int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++ ) {
        scanf("%d", &a[i]);
        for(int j = i; j <= n; j += j&-j)
            insert(0, INF, root[j], root[j], a[i], 1);
    }
    char opt[3];
    while(m -- ) {
        int x, y;
        scanf("%s%d%d", opt, &x, &y);
        if(opt[0] == 'C') {
            for(int j = x; j <= n; j += j&-j) insert(0, INF, root[j], root[j], a[x], -1);
            a[x] = y;
            for(int j = x; j <= n; j += j&-j) insert(0, INF, root[j], root[j], a[x], 1);
        }
        else {
            int k;
            scanf("%d", &k);
            *ax = *ay = 0;
            for(int j = y; j; j -= j&-j) ay[++*ay] = root[j];
            for(int j = x-1; j; j -= j&-j) ax[++*ax] = root[j];
            printf("%d\n", query(0, INF, k));
        }
    }
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注