可持久化数据结构

数据结构

起风了,唯有努力生存。
随风逝,不带一丝伤痕。

有些时候我们会遇到一些奇奇怪怪的题目，例如需要你记录下一个数组的历史版本。
这时候我们怎么办呢？暴力所有开m个线段树/数组？$O(m*n*logn)$的空间估计多半吃不消
这时候我们就要引入一个神奇的数据解构 ——— 可持久化线段树(主席树)。

主席树主要可以用于处理区间第K大之类的问题。

而主席树的实质呢就是对每个前缀([1,1],[1,2],[1,3]...)建立一颗权值线段树，每次更改时如果左(右)儿子没变，我们直接指向他上一颗树的儿子即可，同时我们记录每颗权值线段树的根节点和左右儿子。这样每次我们最多更改$logn$个节点，空间降为$O(m*logn^2)$
我们可以看出这个主席树是具有可减性的。例如我们要求区间[l,r]的第K大时，我们只需用第r颗线段树减去第l-1颗线段树即可。
当然代码中我们肯定不是直接减啦，我们只需每次往下传递节点，统计答案时直接用$Sum[r]-Sum[l-1]$即可，这里r和l-1指的是这两颗权值线段树上的节点，不一定是L-1,R哦。

那么可持久化数组就可以用主席树轻松实现了，因为每次相当于更改一个节点，即单点修改。

基于此，我们就可以愉快地实现可持久化冰碴鸡了(@菜XX)

至于可持久化平衡树么。。。等我学了FHQ Treap再说吧
Code:

#include<bits/stdc++.h>
using namespace std;
#define mid ((l+r)>>1)
const int N=2e5+7;
int n,m,q,tot;
int a[N],b[N];
int rt[N],sum[N*20],ls[N*20],rs[N*20];
inline int build(int l,int r){
    int s=++tot;
    if(l<r){
        ls[s]=build(l,mid);
        rs[s]=build(mid+1,r);
    }
    return s;
}
inline int update(int pre,int l,int r,int x){
    int s=++tot;
    ls[s]=ls[pre];rs[s]=rs[pre];sum[s]=sum[pre]+1;
    if(l<r){
        if(x<=mid) ls[s]=update(ls[pre],l,mid,x);
        else rs[s]=update(rs[pre],mid+1,r,x);
    }
    return s;
}
inline int sa(int u,int v,int l,int r,int k){
    if(l==r) return l;
    int x=sum[ls[v]]-sum[ls[u]];
    if(x>=k) return sa(ls[u],ls[v],l,mid,k);
    else return sa(rs[u],rs[v],mid+1,r,k-x);
}
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i];
    sort(b+1,b+1+n);
    int m=unique(b+1,b+1+n)-b-1;
    rt[0]=build(1,m);
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(b+1,b+1+m,a[i])-b;
        rt[i]=update(rt[i-1],1,m,a[i]);
    }
    for(int i=1;i<=q;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        printf("%d\n",b[sa(rt[x-1],rt[y],1,m,z)]);
    }
}