【蓝桥杯·推导部分和】并查集：从“食物链”到“推导部分和”

       笔者备赛蓝桥杯，遇此题只想到似乎可以用前缀和，但只有想法却不知如何实现。看题解，方知并查集。于是笔者找了找并查集相关例题，从 【AcWing 240.食物链】 入手掌握并查集。笔者算法掌握尚浅，如有谬误还在请评论区中指正。

并查集

笔者总结归纳并查集，有以下四个要点：

1.查：递归查找结点的祖先结点

2.并：将有关系的两点祖先通过赋值为相同祖先，实现关系合并

3.路径压缩：在查找祖先时再加一层递归，使节点直接指向祖先结点，省去一系列中间结点

4.初始化：将所有结点的父结点初始化为自己

在此附上B站一位大佬讲解并查集的视频，笔者收获颇多：

https://www.bilibili.com/video/BV1jv411a7LK?p=1&vd_source=7d0c62ec920356539e4943703e5abea9

在优化后的路径压缩部分，在查找祖先结点的同时将递归返回的祖先结点赋给该节点的父结点，从而实现有关系的各点有共同的父结点（祖先结点）

【AcWing 240.食物链】

分析可知，A、B、C三者构成吃与被吃的循环关系。借鉴网上大佬的思路，可以定义关系如下：

1. 如果某个结点到根结点之间的距离是1，表示该结点可以吃掉根结点

2. 如果某个结点到根结点之间的距离是2，表示该结点可以吃掉其父结点，因为其父结点又可以吃掉根结点，因此由循环关系可得根结点一定可以吃掉距离为2的顶点

3. 如果某个结点距离根结点的距离为3，那么说明该结点与根结点是同类

【原文链接：https://blog.csdn.net/m0_46680603/article/details/119491946】

通过将某一结点距离根结点之间的距离 mod 3所得的结果判断出当前结点与根结点之间的关系。
（1）dis(该结点) % 3 == 0 ：该结点与根结点同类
（2）dis(该结点) % 3 == 1 ：该结点吃根结点
（3）dis(该结点) % 3 == 2 ：该结点被根结点吃

关系确定后，需要记录各结点到根节点的距离，这里考虑路径压缩

至此，我们可以总结一下并查集问题的思路步骤：

1. 明确各元素之间的关系

2. 通过各结点距离根节点（关系合并的公共祖先）距离的数值运算表示关系

3. 路径压缩，更新父节点，更新到根节点距离【合并】

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N=5e4+10;
int p[N],d[N];
int n,m;

int find(int x){
	if(x!=p[x]){
		int t=find(p[x]);
		d[x]+=d[p[x]];
		p[x]=t;
	}
	return p[x];
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) p[i]=i;
	
	int res=0;
	while(m--){
		int t,x,y;
		cin>>t>>x>>y;
		
		if(x>n||y>n){
			res++;
		}
		else{
			int px=find(x), py=find(y);
			if(t==1){
				if(px==py&&(d[x]-d[y])%3!=0) res++;
				else if(px!=py){
					p[px]=py;
					d[px]=d[y]-d[x];
					
				}
			}//if
			else{
				if(px==py&&(d[x]-d[y]-1)%3!=0) res++;
				else if(px!=py){
					p[px]=py;
					d[px]=d[y]+1-d[x];
					
				}
				
			}//else
			
		}//else
		
	}//while
	cout<<res<<endl;
	return 0;
	
}//main

【蓝桥杯2022 省A】推导部分和

为什么会想到用并查集？

        考虑到本题中数列求部分和，容易联想到使用前缀和求解。若要求L到R区间数的和，用前缀和 S（R）-S（L-1）即可表示。那么我们就可以考虑用并查集建立区间端点之间的联系以判断是否可以求值，用权重数组来表示区间和。

        考虑使用并查集，那么需要考虑合并与分开时结点到根节点的距离如何求解。此文详细介绍推导过程，笔者很受启发【https://blog.csdn.net/m0_59139260/article/details/129672133】借用大佬的思路，令t代替l-1：

如果l-1与r在同一集合中（合并为相同根节点），那么部分和可求，反之输出UNKNOWN。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long ll;
const int N = 1e5+10;
ll d[N];//到根的权重 
int p[N];//并查集 
int n,m,q;

int find(int x){
	if(x!=p[x]){
		int t=p[x];
		p[x]=find(p[x]);
		d[x]+=d[t];
		
	}
	return p[x];
	
}//find

int main(){
	cin>>n>>m>>q;
	
	for(int i=1;i<=n;i++) p[i]=i;
	
	while(m--){
		ll l,r,s;
		cin>>l>>r>>s;
		int pl=find(l-1), pr=find(r);
		
		p[pl]=pr;
		d[pl]=d[r]-d[l-1]-s;
		
	}//while合并
	
	while(q--){
		int l,r;
		cin>>l>>r;
		
		int pl=find(l-1), pr=find(r);
		
		if(pl!=pr){
			cout<<"UNKNOWN"<<endl;
		}
		
		else cout<<d[r]-d[l-1]<<endl;
		
	} //while查询 
	
	return 0;
}//main