并查集

板子

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

洛谷P3367 【模板】并查集

#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,CA,B,C，其中 AA 吃 BB，BB 吃 CC，CC 吃 AA。现有 nn 个动物，有个人关于它们说了 qq 句话，每句话分为两种：

  1. XX 和 YY 是同类。
  2. XX 吃 YY。

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

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

#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] 银河英雄传说

一开始有 3000030000 艘战舰，每个一列，之后 TT 个操作。

  1. 把第 ii 列的战舰全部并到第 jj 列。
  2. 求战舰 ii 与战舰 jj 间相差几艘战舰，若不在一列输出 −1-1。

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

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

#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;
}

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

区间最值操作

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

image

HDU5306 Gorgeous Sequence

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

定义：MaxMax 为处理区间中的最大值，sese 为次大值，cntcnt 为区间中最大值的个数。

  1. 若 t≥Maxt\ge Max，此次操作没有任何意义，返回。
  2. 若 se≤t<Maxse\le t<Max，此次操作仅能更新最大值，把区间和加上 cnt(Max−t)cnt(Max-t)，再 Max←tMax\leftarrow t。
  3. 若 t<set<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

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

#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;
}

结束。

  1. About
  2. Contact Us
  3. Privacy
  4. Terms of Service
  5. Copyright Complaint
  6. Language
  7. Legacy mode
  8. Theme
  2. 粤ICP备2021104657号
  3. Worker 0, 11ms
  4. Powered by Hydro v4.14.1 Community