可持久化fhq-treap学习笔记

可持久化fhq-treap----- 支持查询历史版本的非旋treap

luogu扣图:

先看看为啥他可以可持久化

由于fhq-Treap是没有旋转操作的
所以每次操作后的其它没有操作的节点间的关系不变
而有旋转平衡树是要改变的，所以就不大能进行可持久化了

过程

回想，主席树的方法:
每次用log的内存记录一次操作
这可持久平衡树也一样
每次merge或者split都新开节点记录路径
路径是log级的，所以内存也在nlogn的级别(当然不是nlog，是操作log)
还是用结构体吧，容易赋值
其实也就是加了几句话
其实也就是和主席树差不多
其实也没啥说的，看代码去吧

别的

SovietPower：一点(很小的)优化？ 操作3.4.5.6都不会改原树，root[i]=root[ver]可以直接赋值，不需要再Merge了
xx:为什么
SovietPower：你的合并操作的内存都是新开的，但你这一次操作(是opt的操作辣)是没有改变任何值，所以你直接用上一次的就好，拆开的内存不用管就好

注意&&出错&&吐槽

我们截取merge函数的一部分

    if(e[x].pri<e[y].pri) {
        int p=++cnt;
        e[p]=e[x];
        rs(p)=merge(rs(p),y);
        pushup(p);
        return p;
    }
}

那是不是可以写成

    if(e[x].pri<e[y].pri) {
        int p=++cnt;
        e[p]=e[x];
        rs(p)=merge(rs(p),y);
        pushup(p);
        return p;
    }

当然是不对的啊，你还要递归呢，cnt当然要变化了
这数组模拟内存浪费的有点多呀，指针应该就没这毛病了，不过我还是学不下去指针233

模板->luoguP3835代码

#include <iostream>
#include <ctime>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#define ls(x) e[x].ls
#define rs(x) e[x].rs
#define FOR(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const int maxn=500007;
const int inf=0x7fffffff;
int read() {
    int x=0,f=1;char s=getchar();
    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
    return x*f;
}
struct node {
    int ls,rs,size,val,pri;
}e[maxn*50];
int cnt,rt[maxn*50];
void pushup(int x) {
    e[x].size=e[ls(x)].size+e[rs(x)].size+1;
}
int make_edge(int x) {
    e[++cnt].val=x;
    e[cnt].size=1;
    e[cnt].pri=rand();
    return cnt;
}
int merge(int x,int y) {
    if(!x||!y) return x+y;
    if(e[x].pri<e[y].pri) {
        int p=++cnt;
        e[p]=e[x];
        rs(p)=merge(rs(p),y);
        pushup(p);
        return p;
    }
    else  {
        int p=++cnt;
        e[p]=e[y];
        ls(p)=merge(x,ls(p));
        pushup(p);
        return p;
    }
}
void split(int now,int k,int &x,int &y) {
    if(!now) x=y=0;
    else {
        if(e[now].val<=k) {
            e[x=++cnt]=e[now];
            split(rs(now),k,rs(x),y);
            pushup(x);
        }
        else {
            e[y=++cnt]=e[now];
            split(ls(now),k,x,ls(y));
            pushup(y);
        }
    }
}
inline int k_th(int now,int k) {
    while(233) {
        if(k==e[ls(now)].size+1) return now;
        if(k<=e[ls(now)].size) now=ls(now);
        else k-=e[ls(now)].size+1,now=rs(now);
    }
}
int main() {
    int n=read(),x,y,z;
    FOR(i,1,n) {
        int tim=read(),opt=read(),a=read();
        rt[i]=rt[tim];
        if(opt==1) {
            split(rt[i],a,x,y);
            rt[i]=merge(merge(x,make_edge(a)),y);
        } else if(opt==2) {
            split(rt[i],a,x,z);
            split(x,a-1,x,y);
            y=merge(ls(y),rs(y));
            rt[i]=merge(merge(x,y),z);
        } else if(opt==3) {
            split(rt[i],a-1,x,y);
            printf("%d\n",e[x].size+1);
            rt[i]=merge(x,y);
        } else if(opt==4) {
            printf("%d\n",e[k_th(rt[i],a)].val);
        } else if(opt==5) {
            split(rt[i],a-1,x,y);
            if(e[x].size) {
                printf("%d\n",e[k_th(x,e[x].size)].val);
                rt[i]=merge(x,y);
            }
            else printf("%d\n",-inf);
        } else {
            split(rt[i],a,x,y);
            if(e[y].size) {
                printf("%d\n",e[k_th(y,1)].val);
                rt[i]=merge(x,y);
            }
            else printf("%d\n",inf);
        }
    }
    return 0;
}