差别

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

--- 2020-2021:teams:legal_string:jxm2001:可持久化数据结构_1 [2020/06/01 18:12]
jxm2001 创建
+++ 2020-2021:teams:legal_string:jxm2001:可持久化数据结构_1 [2020/08/17 15:23] (当前版本)
jxm2001
@@ 行 1: / 行 1: @@
-====== 可持续化线段树 ======
+====== 可持久化线段树 ======
 ===== 算法简介 =====
-一种可以维护历史版本的线段树，时间复杂度和空间复杂度均为 $O\left(n+m\log n\right)$
+一种可以维护历史版本的线段树，时间复杂度和空间复杂度均为 $O\left(n+m\log n\right)$。
-===== 算法思想 ====
+===== 算法思想 =====
-显然如果对每个历史版本都重建线段树保存时间复杂度和空间复杂度均为 $O\left(nm\right)$
+显然如果对每个历史版本都重建线段树保存时间复杂度和空间复杂度均为 $O\left(nm\right)$。
-但如果可以重复利用部分结点信息，则可以降低时间复杂度和空间复杂度
+但如果可以重复利用部分结点信息，则可以降低时间复杂度和空间复杂度。
-考虑仅对线段树修改路径上的点进行复制、修改，每次修改的时间复杂度和空间复杂度可降为$O\left(\log n\right)$
+考虑仅对线段树修改路径上的点进行复制、修改，每次修改的时间复杂度和空间复杂度可降为$O\left(\log n\right)$。
 ===== 算法应用 =====
-==== 可持续化数组 ====
+==== 可持久化数组 ====
 [[https://www.luogu.com.cn/problem/P3919|洛谷p3919]]
@@ 行 23: / 行 23: @@
 维护一个长度为 $n$ 的数组，支持下列操作：
-. 在某个历史版本上修改某一个位置上的值
+. 在某个历史版本上修改某一个位置上的值。
-. 访问某个历史版本上的某一位置的值
+. 访问某个历史版本上的某一位置的值。
-每进行一次操作就会生成一个新的版本，版本编号即为当前操作的编号
+每进行一次操作就会生成一个新的版本，版本编号即为当前操作的编号。
 **题解**
-用可持续化线段树维护数组，线段树叶子节点记录对应对应位置数组数值，时间复杂度和空间复杂度均为 $O\left(n+m\log n\right)$
+用可持久化线段树维护数组，线段树叶子节点记录对应对应位置数组数值，时间复杂度和空间复杂度均为 $O\left(n+m\log n\right)$。
 <hidden 查看代码>
 <code cpp>
-#include <cstdio>
-#include <algorithm>
-#include <cstring>
-#include <cctype>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-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 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=1e6+5;
 struct Node{
@@ 行 124: / 行 101: @@
 **题意**
-维护一个长度为 $n$ 的数组，$m$ 次查询，每次查询给定闭区间内第 $k$ 小的数
+维护一个长度为 $n$ 的数组，$m$ 次查询，每次查询给定闭区间内第 $k$ 小的数。
 **题解**
-关于第 $k$ 小问题，首先想到使用类似名次树的方法查询
+关于第 $k$ 小问题，首先想到使用类似名次树的方法查询。
-记数组元素为 $a[1\sim n]$，建立空线段树，依次在线段树第 $a[i]$ 位置插入一个元素，线段树需维护区间所含元素个数，并记录历史版本
+记数组元素为 $a[1\sim n]$，建立空线段树，依次在线段树第 $a[i]$ 位置插入一个元素，线段树需维护区间所含元素个数，并记录历史版本。
-设查询区间为 $[l,r]$ ，这历史版本 $r$ 与 历史版本 $l-1$ 的对应节点差值即为 元素 $a[l\sim r]$ 在节点维护范围内所含元素个数
+设查询区间为 $[l,r]$ ，这历史版本 $r$ 与 历史版本 $l-1$ 的对应节点差值即为 元素 $a[l\sim r]$ 在节点维护范围内所含元素个数。
-在此基础上，便可以使用名次树查询第 $k$ 小元素，同时考虑到数据范围需要对数组进行离散化，时间复杂度和空间复杂度均为 $O\left(n+m\log n\right)$
+在此基础上，便可以使用名次树查询第 $k$ 小元素，同时考虑到数据范围需要对数组进行离散化，时间复杂度和空间复杂度均为 $O\left(n+m\log n\right)$。
 <hidden 查看代码>
 <code cpp>
+const int MAXN=1e6+5;
+struct Node{
+	int lef,rig,val;
+};
+Node node[MAXN*20];
+int cnt,root[MAXN],a[MAXN],b[MAXN];
+inline int nodecopy(int k){
+	node[++cnt]=node[k];
+	return cnt;
+}
+void build(int &k,int lef,int rig){
+	k=++cnt;
+	int mid=lef+rig>>1;
+	if(lef==rig)
+	return;
+	build(node[k].lef,lef,mid);
+	build(node[k].rig,mid+1,rig);
+}
+void update(int &k,int p,int lef,int rig,int pos){
+	k=nodecopy(p);
+	node[k].val++;
+	if(lef==rig)
+	return;
+	int mid=lef+rig>>1;
+	if(mid<pos)
+	update(node[k].rig,node[p].rig,mid+1,rig,pos);
+	else
+	update(node[k].lef,node[p].lef,lef,mid,pos);
+}
+int query(int k1,int k2,int lef,int rig,int rk){
+	int mid=lef+rig>>1;
+	if(lef==rig)
+	return mid;
+	int lc1=node[k1].lef,lc2=node[k2].lef,lz=node[lc2].val-node[lc1].val;
+	if(rk>lz)
+	return query(node[k1].rig,node[k2].rig,mid+1,rig,rk-lz);
+	else
+	return query(node[k1].lef,node[k2].lef,lef,mid,rk);
+}
+int main()
+{
+	int n=read_int(),q=read_int(),m;
+	build(root[0],1,n);
+	_rep(i,1,n)
+	a[i]=read_int();
+	memcpy(b+1,a+1,sizeof(int)*n);
+	sort(b+1,b+n+1);
+	m=unique(b+1,b+n+1)-b;
+	_rep(i,1,n)
+	update(root[i],root[i-1],1,n,lower_bound(b+1,b+m+1,a[i])-b);
+	int l,r,k,ans;
+	while(q--){
+		l=read_int(),r=read_int(),k=read_int();
+		ans=query(root[l-1],root[r],1,n,k);
+		enter(b[ans]);
+	}
+	return 0;
+}
 </code>
 </hidden>
@@ 行 148: / 行 183: @@
 **题意**
-维护一个长度为 $n$ 的数组，支持下列操作：
+维护 $n$ 个集合，每个集合初始时只有一个元素 $i$。
-. 在某个历史版本上修改某一个位置上的值
+接下来 $m$ 操作，操作分三种：
-. 访问某个历史版本上的某一位置的值
+. 合并 $a$ ，$b$ 所在集合。
-每进行一次操作就会生成一个新的版本，版本编号即为当前操作的编号
+. 回到第 $k$ 次操作状态。
+. 询问 $a$ ，$b$ 是否在同一集合。
 **题解**
-关于第 $k$ 小问题，首先想到使用类似名次树的方法查询
+显然不能用路径压缩，可以考虑启发式合并，将深度小的集合并到深度大的里面。
-记数组元素为 $a[1\sim n]$，建立空线段树，依次在线段树第 $a[i]$ 位置插入一个元素，线段树需维护区间所含元素个数，并记录历史版本
+考虑将普通版本的启发式合并的数组改成可持久化数组即可，时间复杂度 $O\left(n+m\log^2 n\right)$ ，空间复杂度为 $O\left(n+m\log n\right)$。
-设查询区间为 $[l,r]$ ，这历史版本 $r$ 与 历史版本 $l-1$ 的对应节点差值即为 元素 $a[l\sim r]$ 在节点维护范围内所含元素个数
-在此基础上，便可以使用名次树查询第 $k$ 小元素，时间复杂度和空间复杂度均为 $O\left(n+m\log n\right)$
 <hidden 查看代码>
 <code cpp>
+const int MAXN=1e5+5;
+struct Node{
+	int lef,rig,fa,d;
+};
+Node node[MAXN*30];
+int cnt,root[MAXN<<1],n,q;
+inline int nodecopy(int k){
+	node[++cnt]=node[k];
+	return cnt;
+}
+void build(int &k,int lef,int rig){
+	k=++cnt;
+	int mid=lef+rig>>1;
+	if(lef==rig)
+	return node[k].fa=mid,void();
+	build(node[k].lef,lef,mid);
+	build(node[k].rig,mid+1,rig);
+}
+void update_fa(int &k,int p,int lef,int rig,int pos,int F){
+	k=nodecopy(p);
+	if(lef==rig){
+		node[k].fa=F;
+		return;
+	}
+	int mid=lef+rig>>1;
+	if(mid<pos)
+	update_fa(node[k].rig,node[p].rig,mid+1,rig,pos,F);
+	else
+	update_fa(node[k].lef,node[p].lef,lef,mid,pos,F);
+}
+void update_dep(int &k,int p,int lef,int rig,int pos){
+	k=nodecopy(p);
+	if(lef==rig){
+		node[k].d++;
+		return;
+	}
+	int mid=lef+rig>>1;
+	if(mid<pos)
+	update_dep(node[k].rig,node[p].rig,mid+1,rig,pos);
+	else
+	update_dep(node[k].lef,node[p].lef,lef,mid,pos);
+}
+int query_id(int k,int lef,int rig,int pos){
+	int mid=lef+rig>>1;
+	if(lef==rig)
+	return k;
+	if(mid<pos)
+	return query_id(node[k].rig,mid+1,rig,pos);
+	else
+	return query_id(node[k].lef,lef,mid,pos);
+}
+int Find(int rt,int pos){
+	int id=query_id(rt,1,n,pos);
+	return node[id].fa==pos?id:Find(rt,node[id].fa);
+}
+void Union(int &rt,int p,int a,int b){
+	int x=Find(p,a),y=Find(p,b);
+	if(node[x].fa==node[y].fa)
+	return rt=p,void();
+	if(node[x].d>node[y].d)
+	swap(x,y);
+	update_fa(rt,p,1,n,node[x].fa,node[y].fa);
+	if(node[x].d==node[y].d)
+	update_dep(rt,rt,1,n,node[y].fa);
+}
+int main()
+{
+	n=read_int(),q=read_int();
+	build(root[0],1,n);
+	int opt,a,b;
+	_rep(i,1,q){
+		opt=read_int();
+		if(opt==1){
+			a=read_int(),b=read_int();
+			Union(root[i],root[i-1],a,b);
+		}
+		else if(opt==2)
+		root[i]=root[read_int()];
+		else{
+			root[i]=root[i-1];
+			a=read_int(),b=read_int();
+			int x=Find(root[i],a),y=Find(root[i],b);
+			if(node[x].fa==node[y].fa)
+			puts("1");
+			else
+			puts("0");
+		}
+	}
+	return 0;
+}
 </code>
 </hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具