Blog Detail

C20250465's blog
集训演讲
C20250465 LV 8 @ 1 year ago

并查集

板子

从一些简单的内容讲起。并查集，可以解决合并集合与查询两个数是否在一个集合的数据结构，通过数组 fa[i] 记录 $i$ 的父亲，每次查询搜到根然后合并或查询，因此并查集可以近似看成森林。话不多说，先上代码：

#include <bits/stdc++.h>
using namespace std;
int fa[int(1e4+10)];
int find(int x)//找根
{
	if(fa[x]==x) return x;//根的父亲是自己
	else
	{
		fa[x]=find(fa[x]);//路径压缩
		return fa[x];
	}
}
void merge(int x,int y)//合并
{
	fa[find(x)]=find(y);
}
void check(int x,int y)//是否在一个集合
{
	if(find(x)==find(y)) cout<<"Y"<<endl;
	else cout<<"N"<<endl;
}
int main()
{
	int n,m,x,y,z;
	cin>>n>>m;
	for(int i=1;i<=n;i++) fa[i]=i;
	while(m--)
	{
		cin>>z>>x>>y;
		if(z==1)
		{
			merge(x,y);
		}
		else if(z==2)
		{
			check(x,y);
		}
	}
	return 0;
}

这个是最基本的并查集。那么接下来上点难度。

种类并查集

顾名思义，种类并查集就是把并查集分成多个类别。不过这个“类别”有时候是真的分出来的，例如关押罪犯；有时候只是把 fa 数组扩到多倍而已，例如下面这个例题。

[NOI2001] 食物链

大致意思：有三种动物 $A,B,C$ ，其中 $A$ 吃 $B$ ， $B$ 吃 $C$ ， $C$ 吃 $A$ 。现有 $n$ 个动物，有个人关于它们说了 $q$ 句话，每句话分为两种：

$X$ 和 $Y$ 是同类。
$X$ 吃 $Y$ 。

当他的某句话与前面的某句矛盾，表达的意思是 $X$ 吃 $X$ ，或 $X,Y$ 之中有一者大于 $n$ 时，我们认定他撒谎了。求有多少谎话。

种类并查集的典。我们并不知道这 $n$ 个动物属于哪种，因此初始时把它们各分配到三个并查集里，若出现第一句话，则在同种并查集中连边，否则在异种并查集中连边，然后就是板子了。代码如下：

#include <bits/stdc++.h>
using namespace std;
int fa[int(1e6+10)];
int find(int x)
{
	if(fa[x]==x) return x;
	else
	{
		fa[x]=find(fa[x]);
		return fa[x];
	}
}
int check(int x,int y)
{
	if(find(x)==find(y)) return 1;
	return 0;
}
int merge(int x,int y)
{
	fa[find(x)]=find(y);
}
int main()
{
	int n,q,ans=0;
	cin>>n>>q;
	for(int i=1;i<=3*n;i++) fa[i]=i;//三个种类
	while(q--)
	{
		int opt,x,y;
		cin>>opt>>x>>y;
		if(x>n||y>n)//谎话
		{
			ans++;
			continue;
		}
		if(opt==1)
		{
			if(check(x+n,y)||check(y+n,x)) ans++;//已在异种连边，表示x吃y或y吃x
			else
			{
				merge(x,y);//同种连边
				merge(x+n,y+n);
				merge(x+2*n,y+2*n);
			}
		}
		else
		{
			if(x==y) ans++;//x吃x
			else if(check(x,y)||check(x,y+n)) ans++;//x,y同类或y吃x
			else
			{
				merge(y,x+n);//异种连边
				merge(y+n,x+2*n);
				merge(y+2*n,x);
			}
		}
	}
	cout<<ans;
	return 0;
}

个人感觉这个不难，至少比下面这个算法简单。

带权并查集

依然是顾名思义，就是有权的并查集，可以解决摆积木问题。

[NOI2002] 银河英雄传说

一开始有 $30000$ 艘战舰，每个一列，之后 $T$ 个操作。

把第 $i$ 列的战舰全部并到第 $j$ 列。
求战舰 $i$ 与战舰 $j$ 间相差几艘战舰，若不在一列输出 $-1$ 。

带权并查集的典。维护三个数组， $fa,num,fr$ ， $num_i$ 表示 $i$ 所在的一列有几艘战舰， $fr_i$ 表示 $i$ 的前面有几艘战舰。

接下来在 find() 函数递归后更新 $fr$ ，以及每次操作后更新就行了。

#include <bits/stdc++.h>
using namespace std;
int fa[30010],num[30010],fr[30010];
int find(int x)
{
	if(fa[x]==x) return x;
	int tp=find(fa[x]);//先递归
	fr[x]+=fr[fa[x]];//x前面的战舰数要加上它父亲前面的战舰数
	fa[x]=tp;
	return tp;
}
int main()
{
	int q;
	cin>>q;
	for(int i=1;i<=30000;i++)
	{
		fa[i]=i;
		num[i]=1;
		fr[i]=0;
	}
	while(q--)
	{
		char opt;
		int x,y;
		cin>>opt>>x>>y;
		if(opt=='M')
		{
			int findx=find(x),findy=find(y);
			fr[findx]+=num[findy];//x的根前面加上了y所在的列的所有战舰
			fa[findx]=findy;//接上去
			num[findy]+=num[findx];//y的根的队列长度加上x的根的
			num[findx]=0;//销毁队列x
		}
		else
		{
			if(find(x)!=find(y)) cout<<-1<<endl;
			else cout<<abs(fr[x]-fr[y])-1<<endl;
		}
	}
	return 0;
}

前面的例题也才橙蓝绿，对于竞赛组而言要上点难度。

区间最值操作

不知道什么是区间最值操作？

HDU5306 Gorgeous Sequence

线段树，但是区间取 $\min$ 看着很难，考虑分类讨论。

定义： $Max$ 为处理区间中的最大值， $se$ 为次大值， $cnt$ 为区间中最大值的个数。

若 $t\ge Max$ ，此次操作没有任何意义，返回。
若 $se\le t<Max$ ，此次操作仅能更新最大值，把区间和加上 $cnt(Max-t)$ ，再 $Max\leftarrow t$ 。
若 $t<se$ ，此处不能进行任何剪枝，暴力递归到叶子。

那么这个就是主要思路，上核心代码（未AC，仅供参考，正确性准确，毕竟当时让老师也帮忙调了一天都没找到错），全部代码过长：

//ls左儿子,rs右儿子
void pushup(int p)
{
	int ls=p*2,rs=p*2+1; 
	d[p]=d[ls]+d[rs];
	if(maxx[ls]==maxx[rs])
	{
		maxx[p]=maxx[ls];
		se[p]=max(se[ls],se[rs]);
		cnt[p]=cnt[ls]+cnt[rs];
	}
	else if(maxx[ls]>maxx[rs])
	{
		maxx[p]=maxx[ls];
		se[p]=max(se[ls],maxx[rs]);
		cnt[p]=cnt[ls];
	}
	else
	{
		maxx[p]=maxx[rs];
		se[p]=max(maxx[ls],se[rs]);
		cnt[p]=cnt[rs];
	}
} 
void tagged(int p,long long t)//标记实现
{
	if(maxx[p]<=t) return;
	d[p]+=(t-maxx[p])*cnt[p];
	maxx[p]=tag[p]=t;
}
void pushdown(int p)//标记下传
{
	if(tag[p]==-1) return;
	tagged(p*2,tag[p]);
	tagged(p*2+1,tag[p]);
	tag[p]=-1;
}
void build(int s,int t,int p)//建树
{
	tag[p]=-1;
	if(s==t)
	{
		d[p]=a[s];
		se[p]=-1;
		maxx[p]=a[s];
		cnt[p]=1;
		return;
	}
	int m=(s+t)>>1;
	build(s,m,p*2);
	build(m+1,t,p*2+1);
	pushup(p);
}
void ar_min(int l,int r,int s,int t,int p,long long v)//区间取min
{
	if(maxx[p]<=v) return;
	if(s==t)
	{
		d[p]=min(d[p],v);
		maxx[p]=min(maxx[p],v);
		se[p]=-1;
		cnt[p]=1;
		tag[p]=-1;
		return;
	}
	if(l<=s&&t<=r&&se[p]<v)
	{
		tagged(p,v);
		return;
	} 
	int m=(s+t)>>1;
	pushdown(p);
	if(l<=m) ar_min(l,r,s,m,p*2,v);
	if(r>m) ar_min(l,r,m+1,t,p*2+1,v);
	pushup(p);
}
int query_max(int l,int r,int s,int t,int p)//求区间最大
{
	if(l<=s&&t<=r) return maxx[p];
	int m=(s+t)>>1,ans1=-1,ans2=-1;
	pushdown(p);
	if(l<=m) ans1=query_max(l,r,s,m,p*2);
	if(r>m) ans2=query_max(l,r,m+1,t,p*2+1);
	return max(ans1,ans2);
}
long long query_sum(int l,int r,int s,int t,int p)//区间求和
{
	if(l<=s&&t<=r) return d[p];
	long long m=(s+t)>>1,ans=0;
	pushdown(p);
	if(l<=m) ans+=query_sum(l,r,s,m,p*2);
	if(r>m) ans+=query_sum(l,r,m+1,t,p*2+1);
	return ans;
}

难度可能高了点，那么来道蓝的。

普通平衡树

由于本人太菜，不会 treap，在这里指讲一下 splay 板子，其他是真的不会啊（懒）。

先来看看平衡树能干嘛。

P3369 【模板】普通平衡树

那么来谈一下 splay 的核心：旋转。旋转指的是在不改变树中序遍历的情况下将一个节点旋转到根，主要的旋转就六种，可以参考 OI Wiki，个人认为也只能硬背这段旋转代码：

void rotate(int x)
{
	int y=fa[x],z=fa[y],pos=get(x);//get为判断x是左儿子还是右儿子
	ch[y][pos]=ch[x][pos^1];//ch是左右儿子
	if(ch[x][pos^1]) fa[ch[x][pos^1]]=y;
	ch[x][pos^1]=y;
	fa[y]=x;
	fa[x]=z;
	if(z) ch[z][y==ch[z][1]]=x;
	maintain(x);
	maintain(y);
}

然后就是三个基本函数：

void maintain(int x)
{
	sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+cnt[x];
}
void clear(int x)
{
	fa[x]=ch[x][0]=ch[x][1]=val[x]=cnt[x]=sz[x]=0;
}
int get(int x)
{
	if(x==ch[fa[x]][0]) return 0;
	else return 1;
}

然后就是 splay 函数，即把节点转到根。

void splay(int x)
{
	while(fa[x])
	{
		if(fa[fa[x]])
		{
			if(get(x)==get(fa[x])) rotate(fa[x]);
			else rotate(x); 
		}
		rotate(x);
	}
	r=x;
}

剩下几个函数我就配合代码讲：

void ins(int k)
{
	if(!r)
	{
		tot++;
		val[tot]=k;
		cnt[tot]++;
		r=tot;
		maintain(r);
		return;
	}
	int cur=r,f=0;
	while(1)
	{
		if(val[cur]==k)
		{
			cnt[cur]++;
			maintain(f);
			maintain(cur);
			splay(cur);
			break;
		}
		f=cur;
		if(val[cur]<k)
		cur=ch[cur][1];
		else cur=ch[cur][0];
		if(!cur)
		{
			tot++;
			val[tot]=k;
			cnt[tot]++;
			fa[tot]=f;
			if(val[f]<k)
			ch[f][1]=tot;
			else ch[f][0]=tot;
			maintain(tot);
			maintain(f);
			splay(tot);
			break;
		}
	}
}
int rk(int k)
{
	int ans=0,cur=r;
	while(1)
	{
		if(k<val[cur])
		cur=ch[cur][0];
		else
		{
			ans+=sz[ch[cur][0]];
			if(k==val[cur])
			{
				splay(cur);
				return ans+1;
			}
			ans+=cnt[cur];
			cur=ch[cur][1];
		}
	}
}
int kth(int k)
{
	int cur=r;
	while(1)
	{
		if(ch[cur][0]&&k<=sz[ch[cur][0]]) cur=ch[cur][0];
		else
		{
			k-=sz[ch[cur][0]]+cnt[cur];
			if(k<=0)
			{
				splay(cur);
				return val[cur];
			}
			cur=ch[cur][1];
		}
	}
}
int pre()
{
	int cur=ch[r][0];
	if(!cur) return cur;
	while(ch[cur][1]) cur=ch[cur][1];
	splay(cur);
	return cur;
}
int nxt()
{
	int cur=ch[r][1];
	if(!cur) return cur;
	while(ch[cur][0]) cur=ch[cur][0];
	splay(cur);
	return cur;
}
void del(int k)
{
	rk(k);
	if(cnt[r]>1)
	{
		cnt[r]--;
		maintain(r);
		return;
	}
	if(!ch[r][0]&&!ch[r][1])
	{
		clear(r);
		r=0;
		return;
	}
	if(!ch[r][0])
	{
		int cur=r;
		r=ch[r][1];
		fa[r]=0;
		clear(cur);
		return;
	}
	if(!ch[r][1])
	{
		int cur=r;
		r=ch[r][0];
		fa[r]=0;
		clear(cur);
		return;
	}
	int cur=r,x=pre();
	fa[ch[cur][1]]=x;
	ch[x][1]=ch[cur][1];
	clear(cur);
	maintain(r);
}

平衡树对于像我这样的初学者还是有点抽象的，除了 rotate 函数我觉得要死记硬背之外，其他的还是要靠理解。

可持久化线段树

最后一个内容。也是只讲板子。题目链接先放一个，

洛谷P3834 【模板】可持久化线段树2

就是静态区间第 $k$ 大。配合代码讲一下：

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;
int ls[MAXN<<5],rs[MAXN<<5],rt[MAXN<<5],sum[MAXN<<5],a[MAXN],ind[MAXN],len,tot=0,n,m;
int id(int val)//求val是第几位
{
	return lower_bound(ind,ind+len+1,val)-ind;
}
int build(int s,int t)//建树，动态开点
{
	int r=++tot;
	if(s==t) return r;
	int m=(s+t)>>1;
	ls[r]=build(s,m);
	rs[r]=build(m+1,t);
	return r;
}
int update(int k,int s,int t,int r)//更新，但是是预处理的一部分
{
	int d=++tot;
	ls[d]=ls[r];rs[d]=rs[r];sum[d]=sum[r]+1;
	if(s==t) return d;
	int m=(s+t)>>1;
	if(k<=m) ls[d]=update(k,s,m,ls[d]);
	else rs[d]=update(k,m+1,t,rs[d]);
	return d;
}
int query(int s,int t,int l,int r,int k)//查询
{
	int m=(l+r)>>1,x=sum[ls[t]]-sum[ls[s]];
	if(l==r) return l;
	if(k<=x) return query(ls[s],ls[t],l,m,k);
	else return query(rs[s],rs[t],m+1,r,k-x);
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	memcpy(ind,a,sizeof ind);
	sort(ind+1,ind+n+1);
	len=unique(ind+1,ind+n+1)-ind-1;
	rt[0]=build(1,len);
	for(int i=1;i<=n;i++) rt[i]=update(id(a[i]),1,len,rt[i-1]);
	int l,r,k;
	for(int i=1;i<=m;i++)
	{
		cin>>l>>r>>k;
		cout<<ind[query(rt[l-1],rt[r],1,len,k)]<<endl;
	}
	return 0;
}

结束。

集训演讲

并查集

板子

种类并查集

带权并查集

区间最值操作

普通平衡树

可持久化线段树

Status

Development

Support

集训演讲

并查集

板子

种类并查集

带权并查集

区间最值操作

普通平衡树

可持久化线段树

Status

Development

Support

Don't have an account?

SIGN IN