终于写了一次可持久化Treap，做的是可持久化序列的模板题。
TreapTreap=Tree+Heap，是一个随机化的数据结构。它的每个节点至少有两个关键字，一个是我们要存储的\(val\)，一个是随机堆关键字，我把它称为\(hp\)。Treap满足的性质是\(val\)从小到大，并且每个节点的\(hp\)都小于（或都大于）儿子节点的\(hp\)值。也就是说，通过一个随机数来让Treap具有堆的性质，从而使得其期望深度为\(O(logn)\)。
旋转Treap可以通过旋转来保持其平衡，操作与splay类似。
非旋转非旋转Treap是本文的重点。由于Treap同时具有二叉搜索树和堆的性质，我们考虑利用堆的性质来保持平衡。想一想之前提到过的左偏树的平衡方法，我们可以得到一个基于Split和Merge操作的Treap，称为非旋转Treap。
Split\(split(x,k)\)返回一个\(pair\)，表示把\(x\)为根的树的前\(k\)个元素放在一颗树中，后面的放在另一颗树中，返回这两棵树的根。
这个操作实现起来非常简单。如果\(x\)的左子树的\(size\ge k\)，那么直接递归进左子树，把左子树分出来的第二颗树和当前的\(x\)和右子树合并。否则递归右子树。写的时候注意一下顺序即可。
Merge\(merge(x,y)\)返回merge出的树的根。同样递归实现。如果\(hp(x)<hp(y)\)，则\(merge(rc(x),y)\)，否则\(merge(x,lc(y))\)。
非旋转Treap的关键在于不需要维护父亲节点的信息，故可以可持久化！
每次split和merge走到的所有点都新建一个即可。注意下传标记也要新建点。
代码可持久化序列这道题要求支持三个操作：
\(\text{1 l r}\)，翻转\(l\)到\(r\)的区间
\(\text{2 l r}\)，询问\(l\)的到\(r\)的区间和
\(\text{3 p}\)，回到\(p\)时刻
每次修改新建点打翻转标记即可。
#include<cstdio> #include<cctype> #include<cstring> #include<cstdlib> #include<ctime> #include<utility> #include<algorithm> using namespace std; typedef pair<int,int> Pair; int read() { int x=0,f=1; char c=getchar(); for (;!isdigit(c);c=getchar()) if (c==\'-\') f=-1; for (;isdigit(c);c=getchar()) x=x*10+c-\'0\'; return x*f; } const int maxn=5e4+5; const int nlogn=1.3e7+5; struct node { int x,hp,l,r,sum,size; bool rev; void clear() { x=hp=l=r=sum=size=rev=0; } }; struct TREAP { int pool[nlogn]; int pooler; node t[nlogn]; int now,all; int root[maxn]; TREAP ():now(0),pooler(1) { for (int i=1;i<nlogn;++i) pool[i]=i; root[now]=pool[pooler++]; } int newroot() { int ret=pool[pooler++]; return ret; } int newnode(int x) { int ret=pool[pooler++]; t[ret].hp=rand(); t[ret].size=1; t[ret].x=t[ret].sum=x; return ret; } void delnode(int x) { t[x].clear(); pool[--pooler]=x; } void next() { root[++all]=newroot(); t[root[all]]=t[root[now]]; now=all; } void back(int x) { now=x; } void update(int x) { t[x].sum=t[x].x+t[t[x].l].sum+t[t[x].r].sum; t[x].size=t[t[x].l].size+t[t[x].r].size+1; } void pushdown(int x) { if (!t[x].rev) return; if (t[x].l) { int tx=newnode(t[t[x].l].x); t[tx]=t[t[x].l]; t[tx].rev^=true; t[x].l=tx; } if (t[x].r) { int tx=newnode(t[t[x].r].x); t[tx]=t[t[x].r]; t[tx].rev^=true; t[x].r=tx; } swap(t[x].l,t[x].r); t[x].rev=false; } int merge(int x,int y) { if (!x) return y; if (!y) return x; int now; if (t[x].hp<=t[y].hp) { now=newnode(t[x].x); t[now]=t[x]; pushdown(now); t[now].r=merge(t[now].r,y); } else { now=newnode(t[y].x); t[now]=t[y]; pushdown(now); t[now].l=merge(x,t[now].l); } update(now); return now; } Pair split(int x,int p) { if (t[x].size==p) return make_pair(x,0); int now=newnode(t[x].x); t[now]=t[x]; pushdown(now); int l=t[now].l,r=t[now].r; if (t[l].size>=p) { t[now].l=0; update(now); Pair g=split(l,p); now=merge(g.second,now); return make_pair(g.first,now); } else if (t[l].size+1==p) { t[now].r=0; update(now); return make_pair(now,r); } else { t[now].r=0; update(now); Pair g=split(r,p-t[l].size-1); now=merge(now,g.first); return make_pair(now,g.second); } } void rever(int l,int r) { ++l,++r; Pair g=split(root[now],l-1); Pair h=split(g.second,r-l+1); int want=h.first; int here=newnode(t[want].x); t[here]=t[want]; t[here].rev^=true; int fi=merge(g.first,here); int se=merge(fi,h.second); root[now]=se; } int query(int l,int r) { ++l,++r; Pair g=split(root[now],l-1); Pair h=split(g.second,r-l+1); int want=h.first; int ret=t[want].sum; int fi=merge(g.first,want); int se=merge(fi,h.second); root[now]=se; return ret; } void insert(int x) { int k=newnode(x); root[now]=merge(root[now],k); } } Treap; int main() { #ifndef ONLINE_JUDGE freopen("test.in","r",stdin); freopen("my.out","w",stdout); #endif srand(time(0)); int n=read(),m=read(); for (int i=1;i<=n;++i) { int x=read(); Treap.insert(x); } while (m--) { int op=read(); if (op==1) { Treap.next(); int l=read(),r=read(); Treap.rever(l,r); } else if (op==2) { int l=read(),r=read(); int ans=Treap.query(l,r); printf("%d\n",ans); } else if (op==3) { Treap.back(read()); } } return 0; }