差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:jxm2001:无旋treap [2020/07/08 12:34]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:无旋treap [2021/08/11 10:37] (当前版本)
jxm2001 [集合维护版本]
@@ 行 12: / 行 12: @@
 $\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)$。
 <code cpp>
@@ 行 24: / 行 28: @@
 </code>
-$\text{split}$ 操作为根据权值 $v$ 将 $\text{fhq treap}$ 分成两部分。
+另一种 $\text{split}$ 操作根据节点数 $\text{sz}$ 将 $\text{fhq treap}$ 分成两部分。
-每层 $\text{split}$ 都会到达结点 $k$ 的子节点，所以时间复杂度为原树的深度，根据 $\text{Treap}$ 的性质，深度为 $O(\log n)$。
+<code cpp>
+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);
+	}
+}
+</code>
+$\text{merge}$ 操作根据优先级 $r$ 合并两棵树，要求保证前一棵树的结点权值均小于后一棵树的结点权值。
+每层 $\text{merge}$ 都会到达结点 $k1$ 或 $k2$ 的子节点，所以时间复杂度为两树的深度和，根据 $\text{Treap}$ 的性质，深度为 $O(\log n)$。
 <code cpp>
@@ 行 38: / 行 56: @@
 }
 </code>
-$\text{merge}$ 操作为合并两棵树，要求保证前一棵树的结点权值均小于后一棵树的结点权值。
-每层 $\text{merge}$ 都会到达结点 $k1$ 或 $k2$ 的子节点，所以时间复杂度为两树的深度和，根据 $\text{Treap}$ 的性质，深度为 $O(\log n)$。
 有了 $\text{split}$ 和 $\text{merge}$ 操作，不难得到其他操作。
@@ 行 47: / 行 61: @@
 ===== 代码模板 =====
-[[https://www.luogu.com.cn/problem/P6136|洛谷p6136]]
+==== 集合维护版本 ====
+[[https://www.luogu.com.cn/problem/P3369|洛谷p3369]]
 <hidden 查看代码>
 <code cpp>
-#include <iostream>
+const int MAXN=1e5+5;
-#include <cstdio>
+namespace fhq_treap{
-#include <cstdlib>
-#include <algorithm>
-#include <string>
-#include <sstream>
-#include <cstring>
-#include <cctype>
-#include <cmath>
-#include <vector>
-#include <set>
-#include <map>
-#include <stack>
-#include <queue>
-#include <ctime>
-#include <cassert>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-#define mem(a,b) memset(a,b,sizeof(a))
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-    int t=0;bool sign=false;char c=getchar();
-    while(!isdigit(c)){sign|=c=='-';c=getchar();}
-    while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-    return sign?-t:t;
-}
-inline LL read_LL(){
-    LL t=0;bool sign=false;char c=getchar();
-    while(!isdigit(c)){sign|=c=='-';c=getchar();}
-    while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-    return sign?-t:t;
-}
-inline char get_char(){
-    char c=getchar();
-    while(c==' '||c=='\n'||c=='\r')c=getchar();
-    return c;
-}
-inline void write(LL x){
-    register char c[21],len=0;
-    if(!x)return putchar('0'),void();
-    if(x<0)x=-x,putchar('-');
-    while(x)c[++len]=x%10,x/=10;
-    while(len)putchar(c[len--]+48);
-}
-inline void space(LL x){write(x),putchar(' ');}
-inline void enter(LL x){write(x),putchar('\n');}
-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 node_cnt;
 	int New(int v){
-		int x=top?pool[top--]:++tot;
+		int k=++node_cnt;
-		node[x].val=v,node[x].r=rand(),node[x].sz=1,node[x].ch[0]=node[x].ch[1]=0;
+		node[k].val=v;
-		return x;
+		node[k].r=rand(),node[k].sz=1,node[k].ch[0]=node[k].ch[1]=0;
+		return k;
+	}
+	#define lch(k) node[node[k].ch[0]]
+	#define rch(k) node[node[k].ch[1]]
+	void push_up(int k){
+		node[k].sz=lch(k).sz+rch(k).sz+1;
 	}
-	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);
+			k1=k;
+			split(node[k].ch[1],node[k1].ch[1],k2,v);
+			push_up(k1);
 		}else{
-			k2=k;split(node[k].ch[0],k1,node[k2].ch[0],v);pushup(k2);
+			k2=k;
+			split(node[k].ch[0],k1,node[k2].ch[0],v);
+			push_up(k2);
 		}
 	}
@@ 行 123: / 行 100: @@
 		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);
+			k=k1;
+			merge(node[k].ch[1],node[k1].ch[1],k2);
+			push_up(k);
 		}else{
-			k=k2;merge(node[k].ch[0],k1,node[k2].ch[0]);pushup(k);
+			k=k2;
+			merge(node[k].ch[0],k1,node[k2].ch[0]);
+			push_up(k);
 		}
 	}
@@ 行 138: / 行 119: @@
 		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);
@@ 行 172: / 行 152: @@
 		return kth(rk);
 	}
-}tree;
+	#undef lch
+	#undef rch
+};
 int main()
 {
-    int n=read_int(),m=read_int(),opt,x,last=0,ans=0;
+    int n=read_int(),opt,x;
     while(n--){
-    	x=read_int();
+    	opt=read_int(),x=read_int();
-    	tree.insert(x);
-	}
-    while(m--){
-    	opt=read_int(),x=read_int()^last;
     	switch(opt){
     		case 1:
-    			tree.insert(x);
+    			fhq_treap::insert(x);
     			break;
     		case 2:
-    			tree.erase(x);
+    			fhq_treap::erase(x);
     			break;
     		case 3:
-    			ans^=(last=tree.rank(x));
+    			enter(fhq_treap::rank(x));
     			break;
     		case 4:
-    			ans^=(last=tree.kth(x));
+    			enter(fhq_treap::kth(x));
     			break;
     		case 5:
-    			ans^=(last=tree.pre(x));
+    			enter(fhq_treap::pre(x));
     			break;
     		case 6:
-    			ans^=(last=tree.suf(x));
+    			enter(fhq_treap::suf(x));
     			break;
 		}
 	}
-	enter(ans);
     return 0;
 }
@@ 行 209: / 行 186: @@
 </hidden>
+==== 序列维护版本 ====
+[[https://www.luogu.com.cn/problem/P3391|洛谷p3391]]
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e5+5;
+namespace Treap{
+	int root;
+	struct Node{
+		int val;
+		int r,sz,ch[2];
+		int flip;
+	}node[MAXN];
+	int node_cnt;
+	int new_node(int v){
+		int k=++node_cnt;
+		node[k].val=v;
+		node[k].r=rand(),node[k].sz=1,node[k].ch[0]=node[k].ch[1]=0;
+		node[k].flip=0;
+		return k;
+	}
+	#define lch(k) node[node[k].ch[0]]
+	#define rch(k) node[node[k].ch[1]]
+	void push_up(int k){
+		node[k].sz=lch(k).sz+rch(k).sz+1;
+	}
+	void push_flip(int k){
+		swap(node[k].ch[0],node[k].ch[1]);
+		node[k].flip^=1;
+	}
+	void push_down(int k){
+		if(node[k].flip){
+			push_flip(node[k].ch[0]);
+			push_flip(node[k].ch[1]);
+			node[k].flip=0;
+		}
+	}
+	void split(int k,int &k1,int &k2,int rk){
+		if(!k)return k1=k2=0,void();
+		push_down(k);
+		if(lch(k).sz+1<=rk){
+			k1=k;
+			split(node[k].ch[1],node[k1].ch[1],k2,rk-lch(k).sz-1);
+			push_up(k1);
+		}
+		else{
+			k2=k;
+			split(node[k].ch[0],k1,node[k2].ch[0],rk);
+			push_up(k2);
+		}
+	}
+	void merge(int &k,int k1,int k2){
+		if(!k1||!k2)return k=k1|k2,void();
+		if(node[k1].r>node[k2].r){
+			push_down(k1);
+			k=k1;
+			merge(node[k].ch[1],node[k1].ch[1],k2);
+			push_up(k);
+		}
+		else{
+			push_down(k2);
+			k=k2;
+			merge(node[k].ch[0],k1,node[k2].ch[0]);
+			push_up(k);
+		}
+	}
+	int Stack[MAXN];
+	void build(int k){
+		if(!k)return;
+		build(node[k].ch[0]);
+		build(node[k].ch[1]);
+		push_up(k);
+	}
+	void build(int *a,int n){
+		int top=0;
+		Stack[top]=0;
+		node[0].r=0x7fffffff;
+		_for(i,0,n){
+			int k=new_node(a[i]);
+			while(node[k].r>node[Stack[top]].r)top--;
+			node[k].ch[0]=node[Stack[top]].ch[1];
+			node[Stack[top]].ch[1]=k;
+			Stack[++top]=k;
+		}
+		node[0].ch[0]=node[0].ch[1]=0;
+		root=Stack[1];
+		build(root);
+	}
+	void flip(int L,int R){
+		int lef,mid,rig;
+		split(root,lef,rig,R);
+		split(lef,lef,mid,L-1);
+		push_flip(mid);
+		merge(lef,lef,mid);
+		merge(root,lef,rig);
+	}
+	void dfs(int k,int *a){
+		if(!k)return;
+		push_down(k);
+		dfs(node[k].ch[0],a);
+		a[lch(k).sz]=node[k].val;
+		a+=lch(k).sz+1;
+		dfs(node[k].ch[1],a);
+	}
+};
+int a[MAXN];
+int main()
+{
+	int n=read_int(),m=read_int();
+	_for(i,0,n)a[i]=i+1;
+	Treap::build(a,n);
+	while(m--){
+		int lef=read_int(),rig=read_int();
+		Treap::flip(lef,rig);
+	}
+	Treap::dfs(Treap::root,a);
+	_for(i,0,n)space(a[i]);
+	return 0;
+}
+</code>
+</hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具