终于写了一次可持久化Treap，做的是可持久化序列的模板题。

Treap

Treap=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;

}

巴特西

可持久化Treap

Treap

旋转

非旋转

Split

Merge

代码

最新文章

热门文章