可持久化的 fhq_treap

· · 题解

在我看来，\text{fhq treap} 最大的优点就是实现了期望复杂度为 O(\log_2n) 的可持久化文艺平衡树，这一点将它的功能和 \text{splay}、块状链表区分开了。

说到底，可持久化和普通的到底有什么区别？其实就是：后面的操作不能影响到前面的节点，于是当一个节点发生改变时，要将自己复制一遍。

这样，时间和空间都是 O(n\log_2n) 的，复杂度可以接受。

有一个重点：对 \text{Treap} 来说，只要树堆的性质得到满足，一般树高都在 2\log_2n 左右，但前提是要满足树堆性质！于是，如果在复制节点时不复制随机因子，由于树堆的性质得不到满足，树的高度就会退化成 O(n)。

上代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e7+7;
char buf[N+5],*p1,*p2,c;
#define gc (p1==p2&&(p2=(p1=buf)+fread(buf,1,N,stdin),p1==p2)?EOF:*p1++)
inline ll read(){
    ll an=0,f=1;while(!isdigit(c=gc))if(c=='-')f=-f;
    do an=an*10+(48^c);while(isdigit(c=gc));return an*f;
}
int t[N][7],cnt,tim,Q,rt[N];
ll sum[N],dat[N],las;
#define l(x) t[x][0]
#define r(x) t[x][1]
#define s(x) t[x][2]
#define rv(x) t[x][3]
#define d(x) t[x][4]
#define dfn(x) t[x][5]
#define rd(x) t[x][6]
inline void cp(int &x){
    if(x&&dfn(x)<tim){
        dat[++cnt]=dat[x],sum[cnt]=sum[x];
        for(int i=0;i<7;++i)t[cnt][i]=t[x][i];
        dfn(x=cnt)=tim;
    }
}
inline void pp(int &x){
    s(x)=s(l(x))+s(r(x))+1;
    sum[x]=sum[l(x)]+sum[r(x)]+dat[x];
}
inline void Rev(int &x){
    if(x)cp(x),swap(l(x),r(x)),rv(x)^=1;
}
inline void pd(int &x){
    cp(x);if(rv(x))Rev(l(x)),Rev(r(x)),rv(x)=0;
}
void split(int &x,int &y,int k,int now=rt[tim]){
    if(!now)return void(x=y=0);pd(now);
    if(k<=s(l(now))){
        cp(y=now),split(x,l(y),k,l(y)),pp(y);
    }else{
        cp(x=now),split(r(x),y,k-s(l(now))-1,r(x)),pp(x);
    }return;
}
int merge(int x,int y){
    if(!x||!y)return x|y;pd(x),pd(y);
    if(rd(x)<rd(y)){
        r(x)=merge(r(x),y),pp(x);return x;
    }else{
        l(y)=merge(x,l(y)),pp(y);return y;
    }
}
int main(){
    mt19937 rg(N^time(0));
    srand(time(0)^N);
    int v,op,x,l,r,p,L,R;
    Q=read();
    for(tim=1;tim<=Q;++tim){
        v=read(),op=read();
        rt[tim]=rt[v];
        if(op<3){
            p=read()^las;
            if(op&1){
                split(L,R,p),dfn(++cnt)=tim,rd(cnt)=rg()^rand();
                dat[cnt]=sum[cnt]=read()^las,s(cnt)=1;
                rt[tim]=merge(merge(L,cnt),R);
            }else{
                split(L,rt[tim],p-1);
                split(rt[tim],R,1);
                rt[tim]=merge(L,R);
            }
        }else{
            l=read()^las,r=read()^las;
            split(L,rt[tim],l-1);
            split(rt[tim],R,r-l+1);
            if(op&1)Rev(rt[tim]);
            else printf("%lld\n",las=sum[rt[tim]]);
            rt[tim]=merge(merge(L,rt[tim]),R);
        }
    }return 0;
}