关于带标记并查集的一些想法
一粒夸克
2021-04-04 10:12:47
### 灵感来自于[[SCOI2011]棘手的操作](https://www.luogu.com.cn/problem/P3273)
最开始的时候，我看见这个题目，感觉可以不用左偏树
因为题目中说的是 **“将。。。值增加v”**
所以这些点权只会越来越大
所以只要用并查集维护联通，每次增加点权时更新一下最大值就好了
[直到我把代码交上去之后，我才意识到 v 可以小于 0](https://www.luogu.com.cn/record/48945355)（居然还过了一个点。。。）
所以这篇博客就和这题没什么关系了
------------
### 考虑如何给一个并查集加标记
为了算法的效率，打标记的操作最好在 O(1) 时间内完成，不然这种算法和其他算法相比可能就没有价值
紧接着要考虑标记的下传
首先想到的思路是在向上找父亲时，把父亲的标记加在自己身上
而并查集与左偏树、线段树之类的二叉树最大的不同在于：
**并查集中一个节点的儿子数量是不确定的，所以它不能像线段树那样 $pushdown$ 一次后直接把标记清空**
那么问题就是，我要如何防止一个标记被反复加到同一个点上
### 想了两种思路:
------------
### 1.
我的第一种思路：
如图，我访问到了蓝色节点，而它的父亲正好有一个标记（红色）
那么我把标记加到蓝色节点的 $val$ 上，然后把蓝色节点提到它的父亲节点上面，蓝色节点的子节点接到黑色节点上
这样就可以保证标记内的所有点都会且只会只会被标记更新一次了
(蓝色节点的父亲节点不是根节点的情况）
问题在于 **“把蓝色节点提到它的父亲节点上面，蓝色节点的子节点接到黑色节点上”** 这个操作不太好实现
伪代码：
```cpp
int fa[300005],w[300005],type[300005];
int find(int x){
if(fa[x]==x)return x;
int y=find(fa[x]);
if(type[fa[x]){
w[x]+=type[fa[x]];
这里需要干点什么来把 x 的儿子转移到 fa[x] 上
fa[fa[x]]=x;
}
return fa[x]=y;
}
```
如果有人会写的话欢迎在评论区下方留言
------------
### 2.
第二种思路：
还以这张图为例
### 先考虑蓝色节点的父亲不是根节点的情况
我们在拿蓝色节点的父亲节点的标记更新蓝色节点的 $val$ 时，也把标记加到蓝色节点的标记上
这样就可以保证标记内的所有点都会且只会只会被标记更新一次了
### 再考虑蓝色节点的父亲是根节点的情况
该返回返回，什么也别干就行了
### 并查集+$pushdown$ :
```cpp
int find(int x){
if(fa[x]==x)return x;
int y=find(fa[x]);
if(y^fa[x]){
w[x]+=type[fa[x]];
type[x]+=type[fa[x]];
}
return fa[x]=y;
}
```
### 最后查询某个点的 $val$ 时再把根节点的 type 加上：
```cpp
void query(){
long long a;
scanf("%lld",&a);
int y=find(a);
printf("%lld\n",w[a]+type[y]);
}
```
### 该合并合并：
```cpp
void merge(){
long long a,b;
scanf("%lld%lld",&a,&b);
a=find(a);
b=find(b);
type[a]-=type[b];
w[a]+=type[a];
fa[a]=b;
}
```
### 对一个联通块打标记：
```cpp
void add(){
long long a,b;
scanf("%lld%lld",&a,&b);
int y=find(a);
type[y]+=b;
}
```
有人问，这种并查集可以维护什么一般化的操作和信息？
我的理解是，这篇博客解决了上文中所说的 ：
**“并查集中一个节点的儿子数量是不确定的，所以它不能像线段树那样 $pushdown$ 一次后直接把标记清空”**
这一问题
所以凡是线段树可以维护的标记，这种并查集应该都可以维护
线段树可以对一个区间干什么，这种并查集也就可以对一个集合干什么
------------
### 最后，附上[[SCOI2011]棘手的操作](https://www.luogu.com.cn/problem/P3273)的十分代码
```cpp
#include<bits/stdc++.h>
using namespace std;
int fa[300005],n,q;
long long w[300005],type[300005];
long long a,b,tot,mx[300005],alltyp;
int find(int x){
if(fa[x]==x)return x;
int y=find(fa[x]);
if(y^fa[x]){
w[x]+=type[fa[x]];
type[x]+=type[fa[x]];
}
return fa[x]=y;
}
char c[3];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lld",&w[i]);
fa[i]=i;
mx[i]=w[i];
tot=max(tot,w[i]);
}
scanf("%d",&q);
for(int i=0;i<q;i++){
scanf("%s",c);
if(c[0]=='U'){
scanf("%lld%lld",&a,&b);
a=find(a);
b=find(b);
if(a==b)continue;
type[a]-=type[b];
w[a]+=type[a];
fa[a]=b;
mx[b]=max(mx[b],mx[a]+type[a]);
}
else if(c[0]=='A'){
if(c[1]=='1'){
scanf("%lld%lld",&a,&b);
int y=find(a);
w[a]+=b;
mx[y]=max(mx[y],w[a]);
tot=max(tot,w[a]+type[y]);
}
else if(c[1]=='2'){
scanf("%lld%lld",&a,&b);
int y=find(a);
type[y]+=b;
tot=max(tot,mx[y]+type[y]);
}
else {
scanf("%lld",&a);
alltyp+=a;
}
}
else if(c[0]=='F'){
if(c[1]=='1'){
scanf("%lld",&a);
int y=find(a);
printf("%lld\n",w[a]+type[y]+alltyp);
}
else if(c[1]=='2'){
scanf("%lld",&a);
int y=find(a);
printf("%lld\n",mx[y]+type[y]+alltyp);
}
else {
printf("%lld\n",tot+alltyp);
}
}
}
return 0;
}
```