To boldly go where no one has gone before.

【学习笔记】Dynamic Rankings

2019-03-16 03:17:21


题目P2617

顾名思义,$Dynamic$ $Rankings$是指一种可以动态查询区间第$k$小的数据结构。这里可以用树状数组$+$线段树$+$主席树来维护,具体为用树状数组来保存线段树历史版本的前缀和,然后用主席树思想查询区间第$k$小值。这差不多都能算作树套树套树了,如果可以很快打出来,代码能力会提高不少。

动态建树

这里由于需要将输入数据离散化,所以是先读入完了再建树。建线段树的过程当中也可以顺便把树状数组给更新了,比如这里就表示当前以$x$为根节点新建一个子树,作为线段树的一个历史版本,并用树状数组$C[i]$维护区间节点个数信息。由于树状数组维护前缀和非常方便,查询起来也非常快,所以这里选择用树状数组储存前缀和信息。

inline void build_tree(int &x, int l, int r, int k, int d) {
    if(!x)
        x = ++cnt;
    C[x] += d;
    if(l == r)
        return;
    int mid = (l + r) >> 1;
    if(k <= mid)
        build_tree(tree[x].ls, l, mid, k, d);
    else
        build_tree(tree[x].rs, mid+1, r, k, d);
    return;
}

修改+更新主席树

由于主席树特性,相邻历史版本之间只有一条链的差距,所以在进行更新版本的时候可以使用刚才的$build\_tree()$进行操作,操作的时候也要顾及树状数组特性,由$C[x]$向$C[n]$进行覆盖。 不过这里还有个玄学操作,那就是$lower\_bound()$居然还可以这样用!通过$lower\_bound()$减去序列名,就可以直接得到下标,这招学到了。这里$\_x$表示第一个需要修改的线段树/树状数组标号。

inline void edit_tree(int x, int t) {
    int _x = lower_bound(b+1, b+_n+1, a[x]) - b;
    for(register int i = x; i <= n; i += lowbit(i)) 
        build_tree(root[i], 1, _n, _x, t);
    return;
}

查询第$k$小

这里利用的就是主席树的思想了,用线段树在$r$节点的信息减去线段树在$l-1$节点的信息就可以得到$[l,r]$区间信息。静态主席树可以直接$O(1)$跑出来,但是如果涉及到了修改,一般就只能用$O(n)$去跑。但是由于之前我们维护了一个树状数组$C[i]$,所以可以直接加速查询速度至$O(logn)$,相对地就可以跑得快一些了。

如果已经预处理出了所有需要查询到的树状数组下标,那么直接跑一次差分就完事了。这里$t1[i]$和$t2[i]$表示的就是需要查询到的树状数组的下标,所以$sum$先加上$C[tree[t2[i]].ls]$再减去$C[tree[t1[i]].ls]$,得到的就是两版本左子树不同节点的个数。如果$sum\ge k$,就说明左边节点数比查询的$k$要多,所以向左儿子跳去,即:把所有的$t1[i]$、$t2[i]$更新为对应线段树的左儿子,然后递归;否则向右儿子跳去,找右子树内第$k-sum$小即可。

inline int QueryKth(int l, int r, int k) {
    if(l == r)
        return l;
    int mid = (l + r) >> 1;
    int sum = 0;
    for(register int i = 1; i <= n2; i++)
        sum += C[tree[t2[i]].ls];
    for(register int i = 1; i <= n1; i++)
        sum -= C[tree[t1[i]].ls];
    if(sum >= k) {
        for(register int i = 1; i <= n1; i++)
            t1[i] = tree[t1[i]].ls;
        for(register int i = 1; i <= n2; i++)
            t2[i] = tree[t2[i]].ls;
        return QueryKth(l, mid, k);
    }
    else {
        for(register int i = 1; i <= n1; i++)
            t1[i] = tree[t1[i]].rs;
        for(register int i = 1; i <= n2; i++)
            t2[i] = tree[t2[i]].rs;
        return QueryKth(mid+1, r, k-sum);
    }
}

查询的处理过程

查询$[l,r]$的第$k$小元素的时候,先预处理出所有待处理的树状数组的标号,然后直接从$[1,\_n]$开始查找即可($\_n$是离散化之后的区间长度)。

inline int QueryKth_Pre(int l, int r, int k) {
    n1 = n2 = 0;
    for(register int i = l - 1; i >= 1; i -= lowbit(i))
        t1[++n1] = root[i];
    for(register int i = r; i >= 1; i -= lowbit(i))
        t2[++n2] = root[i];
    return QueryKth(1, _n, k);
}

骚气的$\textbf{unique()}$离散化

离散化本身挺蛋疼,之前我还在用这种基础写法:

inline void Discrete() {
    sort(node+1, node+n+1);
    a[node[1].id] = 1;
    rev[1] = node[1].num;
    for(register int i = 2; i <= n; i++) {
        if(node[i].num != node[i-1].num)
            id++;
        a[node[i].id] = id;
        rev[id] = node[i].num;
    }
    return;
}

虽然很蠢,却是最中用的。

不过,现在看来这个样子搞完全是没有必要了。又是一个强大的$STL$——

$\textbf{STL}$大法好!上网搜索$\textbf{unique()}$有真相!

一种叫做$unique()$的$STL$可以直接帮我们完成去重的操作,并返回离散化之后序列的$end()$迭代器。上面也有提到,迭代器减去序列名就可以直接得到下标,所以这样两句话就可以完成排序$+$离散化操作:

sort(b+1, b+1+_n);
_n = unique(b+1, b+1+_n) - b - 1;

其中$\_n$即为离散化之后的序列长度,上文有提到。这个$unique()$真是太好了哇!

$main()$函数也写得差不多就可以了。需要注意修改点权的时候,$edit\_tree(c[i],-1)$后要先把$\textbf{a[c[i]]}$给更新为$\textbf{d[i]}$,然后再$\textbf{edit\_tree(c[i],1)}$,这个样子就成功完成了修改。

int main() {
    scanf("%d%d", &n, &m);
    for(register int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        b[++_n] = a[i];
    }
    for(register int i = 1; i <= m; i++) {
        char ch = getchar();
        while(ch != 'Q' &&ch != 'C')
            ch = getchar();
        if(ch == 'Q')
            scanf("%d%d%d", &c[i], &d[i], &e[i]);
        else {
            scanf("%d%d", &c[i], &d[i]);
            b[++_n] = d[i];
        }
    }
    sort(b+1, b+1+_n);
    _n = unique(b+1, b+1+_n) - b - 1;
    for(register int i = 1; i <= n; i++)
        edit_tree(i, 1);
    for(register int i = 1; i <= m; i++) {
        if(e[i])
            printf("%d\n", b[QueryKth_Pre(c[i], d[i], e[i])]);
        else {
            edit_tree(c[i], -1);
            a[c[i]] = d[i];
            edit_tree(c[i], 1);
        }
    }
    return 0;
}

完整代码

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

const int MAXN = 500010;

int a[MAXN], b[MAXN], c[MAXN], d[MAXN], e[MAXN];
struct SEGTREE {
    int ls, rs, v;
} tree[MAXN * 20];
int C[MAXN * 20];
int n1, n2, t1[MAXN], t2[MAXN];
int cnt = 0, root[MAXN];
int n, _n, m;

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

inline void build_tree(int &x, int l, int r, int k, int d) {
    if(!x)
        x = ++cnt;
    C[x] += d;
    if(l == r)
        return;
    int mid = (l + r) >> 1;
    if(k <= mid)
        build_tree(tree[x].ls, l, mid, k, d);
    else
        build_tree(tree[x].rs, mid+1, r, k, d);
    return;
}

inline void edit_tree(int x, int t) {
    int _x = lower_bound(b+1, b+_n+1, a[x]) - b;
    for(register int i = x; i <= n; i += lowbit(i)) 
        build_tree(root[i], 1, _n, _x, t);
    return;
}

inline int QueryKth(int l, int r, int k) {
    if(l == r)
        return l;
    int mid = (l + r) >> 1;
    int sum = 0;
    for(register int i = 1; i <= n2; i++)
        sum += C[tree[t2[i]].ls];
    for(register int i = 1; i <= n1; i++)
        sum -= C[tree[t1[i]].ls];
    if(sum >= k) {
        for(register int i = 1; i <= n1; i++)
            t1[i] = tree[t1[i]].ls;
        for(register int i = 1; i <= n2; i++)
            t2[i] = tree[t2[i]].ls;
        return QueryKth(l, mid, k);
    }
    else {
        for(register int i = 1; i <= n1; i++)
            t1[i] = tree[t1[i]].rs;
        for(register int i = 1; i <= n2; i++)
            t2[i] = tree[t2[i]].rs;
        return QueryKth(mid+1, r, k-sum);
    }
}

inline int QueryKth_Pre(int l, int r, int k) {
    n1 = n2 = 0;
    for(register int i = l - 1; i >= 1; i -= lowbit(i))
        t1[++n1] = root[i];
    for(register int i = r; i >= 1; i -= lowbit(i))
        t2[++n2] = root[i];
    return QueryKth(1, _n, k);
}

int main() {
    scanf("%d%d", &n, &m);
    for(register int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        b[++_n] = a[i];
    }
    for(register int i = 1; i <= m; i++) {
        char ch = getchar();
        while(ch != 'Q' &&ch != 'C')
            ch = getchar();
        if(ch == 'Q')
            scanf("%d%d%d", &c[i], &d[i], &e[i]);
        else {
            scanf("%d%d", &c[i], &d[i]);
            b[++_n] = d[i];
        }
    }
    sort(b+1, b+1+_n);
    _n = unique(b+1, b+1+_n) - b - 1;
    for(register int i = 1; i <= n; i++)
        edit_tree(i, 1);
    for(register int i = 1; i <= m; i++) {
        if(e[i])
            printf("%d\n", b[QueryKth_Pre(c[i], d[i], e[i])]);
        else {
            edit_tree(c[i], -1);
            a[c[i]] = d[i];
            edit_tree(c[i], 1);
        }
    }
    return 0;
}