BZOJ 3673 persistent and look-up by zky

subject

BZOJ 3673
LUOGU 3402
Description

n sets m operations
Operation:
1 a b merges the set of a,b
2 k returns to the state after the k-th operation (query is counted as operation)
3 a b asks if a and B belong to the same set. If yes, output 1, otherwise output 0
0<n,m<=2*10^4

Input

Output

Sample Input

5 6
1 1 2
3 1 2
2 0
3 1 2
2 1
3 1 2

Sample Output

1
0
1

HINT

Source

Author SB

Title Solution

  • I don't know how to do it, but the code is very short
    UPD: the author uses rope, which is the persistent balance tree in stl
    KuribohG told me that I can use the persistent line tree to realize the persistent array t
    Now that there are persistent arrays, you can use a heuristics combination of re merging and query sets to properly merge them (so you only need to modify one fa at a time).

  • The heuristic combination of parallel search sets is to merge by rank, and the initial rank of all sets is 0
    Merge to set the father of the root with the smallest rank as the root with the largest rank
    If the rank is the same, select any one as the parent node and add its rank + 1
    Rank is maintained as fa.

  • But in fact, if the data is random, it's OK to merge at will. There's no need to merge by rank
    UPD: rank is not easy to use sometimes. It's better to maintain the size of subtree...
    In addition, ndsf found that as long as direct violence can abuse T T.

Quote from hzwer

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
template<typename T>inline void read(T &x)
{
	x=0;
	T f=1,ch=getchar();
	while (!isdigit(ch) && ch^'-') ch=getchar();
	if (ch=='-') f=-1, ch=getchar();
	while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48), ch=getchar();
	x*=f;
}
struct rec
{
	int l,r;
}tree[maxn*30];
int Ed[maxn],tot;//Ed [] is the version number, tot is the total number of nodes (these are the chairman tree)
int n,m,fa[maxn*30],deep[maxn*30];//deep [] stores the maximum depth, fa [] stores the father of a point in a version
inline void build(int &now,int l,int r)
{
	now=++tot;
	if (l==r)
	{
		fa[now]=l;//Initial version: the father is himself, just like the father of each point is himself
		return ;
	}
	int mid=(l+r)>>1;
	build(tree[now].l,l,mid);
	build(tree[now].r,mid+1,r);
}
//The president tree maintains: who is the father of every version and every point
inline void update(int &now,int last,int l,int r,int x,int f)//Change x's father to f
{
	now=++tot;
	if (l==r)
	{
		fa[now]=f;
		deep[now]=deep[last];
		return ;
	}
	tree[now]=tree[last];//deep [] for heuristic merging
	int mid=(l+r)>>1;
	if (x<=mid)
		update(tree[now].l,tree[last].l,l,mid,x,f);
	else
		update(tree[now].r,tree[last].r,mid+1,r,x,f);
}

inline int query(int now,int l,int r,int x)//Ask the father of a point in a version
{
	if (l==r)
		return now;
	int mid=(l+r)>>1;
	if (x<=mid)
		return query(tree[now].l,l,mid,x);
	else
		return query(tree[now].r,mid+1,r,x);
}

inline void add(int now,int l,int r,int x)//Add one to the depth of each point in a join set connection block
{
	if (l==r)
	{
		++deep[now];
		return ;
	}
	int mid=(l+r)>>1;
	if (x<=mid)
		add(tree[now].l,l,mid,x);
	else
		add(tree[now].r,mid+1,r,x);
}
inline int get(int ed,int x)//ed version number
{
	register int f=query(ed,1,n,x);//Search for the father of a point in this version
	if (x==fa[f]) return f;
	return get(ed,fa[f]);//Parallel lookups without path compression
}
int main()
{
	read(n);read(m);
	build(Ed[0],1,n);
	for (register int opt,k,a,b,i=1;i<=m;++i)
	{
		read(opt);
		if (opt==1)
		{
			Ed[i]=Ed[i-1];
			read(a);read(b);
			register int f1=get(Ed[i],a);
			register int f2=get(Ed[i],b);
			if (fa[f1]==fa[f2]) continue;
			if (deep[f1] > deep[f2])
				swap(f1,f2);//Combine the big ones to the small ones, and ensure that the number of F 1 son nodes must be less than or equal to F 2
			update(Ed[i],Ed[i-1],1,n,fa[f1],fa[f2]);
			if (deep[f1]==deep[f2])
				add(Ed[i],1,n,fa[f2]);//Because f2 is not f1, the depth of f1 should be increased by 1
          //We use heuristic merging to ensure the complexity of merging and searching sets
		}
		else if (opt==2)
		{
			read(k);
			Ed[i]=Ed[k];
		}
		else
		{
			Ed[i]=Ed[i-1];
			read(a);read(b);
			register int f1=get(Ed[i],a);
			register int f2=get(Ed[i],b);
			if (fa[f1]==fa[f2]) puts("1");
			else puts("0");
		}
	}
	return 0;
}

Tags: less

Posted on Mon, 02 Dec 2019 04:49:39 -0800 by richardw