并查集
板子
从一些简单的内容讲起。并查集,可以解决合并集合与查询两个数是否在一个集合的数据结构,通过数组 fa[i]
记录 i 的父亲,每次查询搜到根然后合并或查询,因此并查集可以近似看成森林。话不多说,先上代码:
洛谷P3367 【模板】并查集
这个是最基本的并查集。那么接下来上点难度。
种类并查集
顾名思义,种类并查集就是把并查集分成多个类别。不过这个“类别”有时候是真的分出来的,例如关押罪犯;有时候只是把 fa
数组扩到多倍而已,例如下面这个例题。
[NOI2001] 食物链
大致意思:有三种动物 A,B,C,其中 A 吃 B,B 吃 C,C 吃 A。现有 n 个动物,有个人关于它们说了 q 句话,每句话分为两种:
- X 和 Y 是同类。
- X 吃 Y。
当他的某句话与前面的某句矛盾,表达的意思是 X 吃 X,或 X,Y 之中有一者大于 n 时,我们认定他撒谎了。求有多少谎话。
种类并查集的典。我们并不知道这 n 个动物属于哪种,因此初始时把它们各分配到三个并查集里,若出现第一句话,则在同种并查集中连边,否则在异种并查集中连边,然后就是板子了。代码如下:
个人感觉这个不难,至少比下面这个算法简单。
带权并查集
依然是顾名思义,就是有权的并查集,可以解决摆积木问题。
[NOI2002] 银河英雄传说
一开始有 30000 艘战舰,每个一列,之后 T 个操作。
- 把第 i 列的战舰全部并到第 j 列。
- 求战舰 i 与战舰 j 间相差几艘战舰,若不在一列输出 −1。
带权并查集的典。维护三个数组,fa,num,fr,numi 表示 i 所在的一列有几艘战舰,fri 表示 i 的前面有几艘战舰。
接下来在 find()
函数递归后更新 fr,以及每次操作后更新就行了。
前面的例题也才橙蓝绿,对于竞赛组而言要上点难度。
区间最值操作
不知道什么是区间最值操作?

HDU5306 Gorgeous Sequence
线段树,但是区间取 min 看着很难,考虑分类讨论。
定义:Max 为处理区间中的最大值,se 为次大值,cnt 为区间中最大值的个数。
- 若 t≥Max,此次操作没有任何意义,返回。
- 若 se≤t<Max,此次操作仅能更新最大值,把区间和加上 cnt(Max−t),再 Max←t。
- 若 t<se,此处不能进行任何剪枝,暴力递归到叶子。
那么这个就是主要思路,上核心代码(未AC,仅供参考,正确性准确,毕竟当时让老师也帮忙调了一天都没找到错),全部代码过长:
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)
{
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,个人认为也只能硬背这段旋转代码:
然后就是三个基本函数:
然后就是 splay 函数,即把节点转到根。
剩下几个函数我就配合代码讲:
平衡树对于像我这样的初学者还是有点抽象的,除了 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)
{
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;
}
结束。