CVBB ACM Team

用户工具

站点工具

您在这里: front_page » 2020-2021 » teams » legal_string » jxm2001 » 无旋treap
2020-2021:teams:legal_string:jxm2001:无旋treap

这是本文档旧的修订版！

目录

$\text{fhq treap}$

算法简介

$\text{Treap}$ 的无旋版本，支持快速分裂、合并以及可持久化。

算法思想

$\text{Treap}$ 保证深度的方法为给每个结点赋随机的优先级 $r$，权值方面 $\text{Treap}$ 为二叉搜索树，优先级方面 $\text{Treap}$ 为堆。

而当每个点的权值 $val$、$r$ 确定后树的形态唯一，这与操作顺序无关。而由于 $r$ 的随机性，保证了 $\text{Treap}$ 的深度。

$\text{fhq treap}$ 利用了 $\text{Treap}$ 的这条性质，实现了 $O(\log n)$ 的 $\text{split}$ 和 $\text{merge}$。

$\text{split}$ 操作分两种，分别用于维护集合和序列。第一种 $\text{split}$ 操作根据权值 $v$ 将 $\text{fhq treap}$ 分成两部分。

每层 $\text{split}$ 都会到达结点 $k$ 的子节点，所以时间复杂度为原树的深度，根据 $\text{Treap}$ 的性质，深度为 $O(\log n)$。 

void split(int k,int &k1,int &k2,int v){
	if(!k) return k1=k2=0,void();
	if(node[k].val<=v){
		k1=k;split(node[k].ch[1],node[k1].ch[1],k2,v);pushup(k1);
	}else{
		k2=k;split(node[k].ch[0],k1,node[k2].ch[0],v);pushup(k2);
	}
}

另一种 $\text{split}$ 操作根据节点数 $\text{sz}$ 将 $\text{fhq treap}$ 分成两部分。 

void split(int k,int &k1,int &k2,int rk){
	if(!k) return k1=k2=0,void();
	pushdown(k);
	if(node[node[k].ch[0]].sz+1<=rk){
		k1=k;split(node[k].ch[1],node[k1].ch[1],k2,rk-node[node[k].ch[0]].sz-1);pushup(k1);
	}else{
		k2=k;split(node[k].ch[0],k1,node[k2].ch[0],rk);pushup(k2);
	}
}

$\text{merge}$ 操作根据优先级 $r$ 合并两棵树，要求保证前一棵树的结点权值均小于后一棵树的结点权值。

每层 $\text{merge}$ 都会到达结点 $k1$ 或 $k2$ 的子节点，所以时间复杂度为两树的深度和，根据 $\text{Treap}$ 的性质，深度为 $O(\log n)$。 

void merge(int &k,int k1,int k2){
	if(!k1||!k2)return k=k1|k2,void();
	if(node[k1].r>node[k2].r){
		k=k1;merge(node[k].ch[1],node[k1].ch[1],k2);pushup(k);
	}else{
		k=k2;merge(node[k].ch[0],k1,node[k2].ch[0]);pushup(k);
	}
}

有了 $\text{split}$ 和 $\text{merge}$ 操作，不难得到其他操作。

代码模板

集合维护版本

洛谷p6136

查看代码

查看代码 

const int MAXN=2e6+5;
struct fhq_treap{
	int root;
	struct Node{
		int val,r,sz,ch[2];
	}node[MAXN];
	int pool[MAXN],top,tot;
	int New(int v){
		int x=top?pool[top--]:++tot;
		node[x].val=v,node[x].r=rand(),node[x].sz=1,node[x].ch[0]=node[x].ch[1]=0;
		return x;
	}
	void Del(int x){if(x)pool[++top]=x;}
	void pushup(int k){node[k].sz=node[node[k].ch[0]].sz+node[node[k].ch[1]].sz+1;}
	void split(int k,int &k1,int &k2,int v){
		if(!k) return k1=k2=0,void();
		if(node[k].val<=v){
			k1=k;split(node[k].ch[1],node[k1].ch[1],k2,v);pushup(k1);
		}else{
			k2=k;split(node[k].ch[0],k1,node[k2].ch[0],v);pushup(k2);
		}
	}
	void merge(int &k,int k1,int k2){
		if(!k1||!k2)return k=k1|k2,void();
		if(node[k1].r>node[k2].r){
			k=k1;merge(node[k].ch[1],node[k1].ch[1],k2);pushup(k);
		}else{
			k=k2;merge(node[k].ch[0],k1,node[k2].ch[0]);pushup(k);
		}
	}
	void insert(int v){
		int lef,rig;
		split(root,lef,rig,v);
		merge(lef,lef,New(v));
		merge(root,lef,rig);
	}
	void erase(int v){
		int lef,mid,rig;
		split(root,lef,rig,v);
		split(lef,lef,mid,v-1);
		Del(mid);
		merge(mid,node[mid].ch[0],node[mid].ch[1]);
		merge(lef,lef,mid);
		merge(root,lef,rig);
	}
	int rank(int v){
		int lef,rig,ans;
		split(root,lef,rig,v-1);
		ans=node[lef].sz+1;
		merge(root,lef,rig);
		return ans;
	}
	int kth(int rk){
		int pos=root;
		while(true){
			if(rk==node[node[pos].ch[0]].sz+1)return node[pos].val;
			else if(rk<node[node[pos].ch[0]].sz+1)pos=node[pos].ch[0];
			else rk-=node[node[pos].ch[0]].sz+1,pos=node[pos].ch[1];
		}
	}
	int pre(int v){
		int lef,rig,rk;
		split(root,lef,rig,v-1);
		rk=node[lef].sz;
		merge(root,lef,rig);
		return kth(rk);
	}
	int suf(int v){
		int lef,rig,rk;
		split(root,lef,rig,v);
		rk=node[lef].sz+1;
		merge(root,lef,rig);
		return kth(rk);
	}
}tree;
int main()
{
    int n=read_int(),m=read_int(),opt,x,last=0,ans=0;
    while(n--){
    	x=read_int();
    	tree.insert(x);
	}
    while(m--){
    	opt=read_int(),x=read_int()^last;
    	switch(opt){
    		case 1:
    			tree.insert(x);
    			break;
    		case 2:
    			tree.erase(x);
    			break;
    		case 3:
    			ans^=(last=tree.rank(x));
    			break;
    		case 4:
    			ans^=(last=tree.kth(x));
    			break;
    		case 5:
    			ans^=(last=tree.pre(x));
    			break;
    		case 6:
    			ans^=(last=tree.suf(x));
    			break;
		}
	}
	enter(ans);
    return 0;
}

序列维护版本

洛谷p3391

查看代码

查看代码 

const int MAXN=2e6+5;
struct fhq_treap{
	int root,tot;
	vector<int> sequence;
	struct Node{
		int r,val,sz,flip,ch[2];
	}node[MAXN];
	int New(int v){
		int x=++tot;
		node[x].val=v,node[x].r=rand(),node[x].sz=1;
		return x;
	}
	void pushup(int k){node[k].sz=node[node[k].ch[0]].sz+node[node[k].ch[1]].sz+1;}
	void pushdown(int k){
		if(node[k].flip){
			swap(node[k].ch[0],node[k].ch[1]);
			node[node[k].ch[0]].flip^=1;
			node[node[k].ch[1]].flip^=1;
			node[k].flip=0;
		}
	}
	void split(int k,int &k1,int &k2,int rk){
		if(!k) return k1=k2=0,void();
		pushdown(k);
		if(node[node[k].ch[0]].sz+1<=rk){
			k1=k;split(node[k].ch[1],node[k1].ch[1],k2,rk-node[node[k].ch[0]].sz-1);pushup(k1);
		}else{
			k2=k;split(node[k].ch[0],k1,node[k2].ch[0],rk);pushup(k2);
		}
	}
	void merge(int &k,int k1,int k2){
		if(!k1||!k2)return k=k1|k2,void();
		if(node[k1].r>node[k2].r){
			pushdown(k1);k=k1;merge(node[k].ch[1],node[k1].ch[1],k2);pushup(k);
		}else{
			pushdown(k2);k=k2;merge(node[k].ch[0],k1,node[k2].ch[0]);pushup(k);
		}
	}
	void build(){
		_for(i,0,sequence.size())
		merge(root,root,New(sequence[i]));
	}
	void Flip(int L,int R){
		int lef,mid,rig;
		split(root,lef,rig,R);
		split(lef,lef,mid,L-1);
		node[mid].flip^=1;
		merge(lef,lef,mid);
		merge(root,lef,rig);
	}
	void output(){
		sequence.clear();
		dfs(root);
	}
	void dfs(int k){
		if(!k) return;
		pushdown(k);
		dfs(node[k].ch[0]);
		sequence.push_back(node[k].val);
		dfs(node[k].ch[1]);
	}
}tree;
int main()
{
	int n=read_int(),m=read_int(),L,R;
	_rep(i,1,n)
	tree.sequence.push_back(i);
	tree.build();
	while(m--){
		L=read_int(),R=read_int();
		tree.Flip(L,R);
	}
	tree.output();
	_for(i,0,n)
	space(tree.sequence[i]);
    return 0;
}
2020-2021/teams/legal_string/jxm2001/无旋treap.1595738680.txt.gz · 最后更改: 2020/07/26 12:44 由 jxm2001

页面工具

除额外注明的地方外，本维基上的内容按下列许可协议发布： CC Attribution-Share Alike 4.0 International
CC Attribution-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki
京ICP备20018844号-3