差别

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

--- 2020-2021:teams:legal_string:jxm2001:可持久化数据结构_2 [2020/07/08 17:12]
jxm2001 创建
+++ 2020-2021:teams:legal_string:jxm2001:可持久化数据结构_2 [2020/07/27 22:57] (当前版本)
jxm2001 ↷ 页面2020-2021:teams:legal_string:可持久化数据结构_2被移动至2020-2021:teams:legal_string:jxm2001:可持久化数据结构_2
@@ 行 27: / 行 27: @@
 </code>
-我们会发现 ''merge(mid,node[mid].ch[0],node[mid].ch[1]);'' 语句并没有 $\text{split}$ 操作为其开点，这将导致错误。
+我们会发现 ''merge(mid,node[mid].ch[0],node[mid].ch[1])'' 语句并没有 $\text{split}$ 操作为其开点，这将导致错误。
 解决方案为所有相同关键字的节点共用一个位置，或者为 $\text{merge}$ 操作开点。考虑到前者编程较为复杂，这里选择后者。
+需要注意的是，在保证关键字唯一或维护序列时 $\text{merge}$ 操作不需要开点。
 ===== 算法模板 =====
+==== 集合维护版本 ====
 [[https://www.luogu.com.cn/problem/P3835|洛谷p3835]]
@@ 行 37: / 行 41: @@
 <hidden 查看代码>
 <code cpp>
-#include <iostream>
-#include <cstdio>
-#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=5e5+5,MAXM=40,Inf=0x7fffffff;
 int root[MAXN];
 struct fhq_treap{
+	int tot;
 	struct Node{
 		int val,r,sz,ch[2];
 	}node[MAXN*MAXM];
-	int tot;
 	int Copy(int k){
 		node[++tot]=node[k];
@@ 行 188: / 行 145: @@
     			enter(tree.suf(root[i]=root[v],x));
     			break;
+		}
+	}
+    return 0;
+}
+</code>
+</hidden>
+==== 序列维护版本 ====
+[[https://www.luogu.com.cn/problem/P5055|洛谷p5055]]
+需要注意的是，可持续化数据结构的标记下放操作需要复制子节点再下方。
+原因是可持续化数据结构多个父节点共用一个子节点，若直接对标记进行下放，将影响多个父节点，即影响多个历史版本。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=2e5+5,MAXM=80;
+int root[MAXN];
+struct fhq_treap{
+	int tot;
+	struct Node{
+		int r,val,sz,flip,ch[2];
+		LL sum;
+	}node[MAXN*MAXM];
+	int New(int v){
+		int x=++tot;
+		node[x].sum=node[x].val=v,node[x].r=rand(),node[x].sz=1;
+		return x;
+	}
+	int Copy(int k){
+		node[++tot]=node[k];
+		return tot;
+	}
+	void pushup(int k){
+		node[k].sz=node[node[k].ch[0]].sz+node[node[k].ch[1]].sz+1;
+		node[k].sum=node[node[k].ch[0]].sum+node[node[k].ch[1]].sum+node[k].val;
+	}
+	void pushdown(int k){
+		if(node[k].flip){
+			if(node[k].ch[0])node[k].ch[0]=Copy(node[k].ch[0]);
+			if(node[k].ch[1])node[k].ch[1]=Copy(node[k].ch[1]);
+			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=Copy(k);split(node[k].ch[1],node[k1].ch[1],k2,rk-node[node[k].ch[0]].sz-1);pushup(k1);
+		}else{
+			k2=Copy(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 Flip(int &root,int p,int L,int R){
+		int lef,mid,rig;
+		split(p,lef,rig,R);
+		split(lef,lef,mid,L-1);
+		node[mid].flip^=1;
+		merge(lef,lef,mid);
+		merge(root,lef,rig);
+	}
+	void Insert(int &root,int p,int pos,int v){
+		int lef,rig;
+		split(p,lef,rig,pos);
+		merge(lef,lef,New(v));
+		merge(root,lef,rig);
+	}
+	void erase(int &root,int p,int pos){
+		int lef,mid,rig;
+		split(p,lef,rig,pos);
+		split(lef,lef,mid,pos-1);
+		merge(root,lef,rig);
+	}
+	LL query(int root,int L,int R){
+		int lef,mid,rig;
+		split(root,lef,rig,R);
+		split(lef,lef,mid,L-1);
+		return node[mid].sum;
+	}
+}tree;
+int main()
+{
+	int n,v,opt;
+	LL p,x,l,r,last=0;
+	n=read_int();
+	_rep(i,1,n){
+		v=read_int(),opt=read_int();
+		switch(opt){
+			case 1:
+				p=read_LL()^last,x=read_LL()^last;
+				tree.Insert(root[i],root[v],p,x);
+				break;
+			case 2:
+				p=read_LL()^last;
+				tree.erase(root[i],root[v],p);
+				break;
+			case 3:
+				l=read_LL()^last,r=read_LL()^last;
+				tree.Flip(root[i],root[v],l,r);
+				break;
+			case 4:
+				l=read_LL()^last,r=read_LL()^last;
+				enter(last=tree.query(root[i]=root[v],l,r));
+				break;
 		}
 	}

CVBB ACM Team

用户工具

站点工具

差别

页面工具