title: 一类链式并查集问题
categories:

ICPC
tags:
null
abbrlink: 1875215d
date: 2024-11-23 00:00:00

链接：https://ac.nowcoder.com/acm/contest/69510/G
来源：牛客网

你在一个星球上，外星人amiloac想让你管理一条河流，该河流有 $x$ 段，每两段之间有一个挡板隔开，每一段都有各自的颜色 $a$ 。你需要管理 $q$ 天，每一天你需要做以下的一种操作。

$1\ l\ r$ 将第 $l$ 至 $r$ 段河流的所有未打开的挡板打开。

$2\ x$ 询问你第 $x$ 段河流的颜色是什么。

对于任意相邻的两段，它们之间的隔板被打开后的瞬间，河流的颜色会混合变成颜色最深的河流的颜色， $a$ 越大，颜色越深。

注：隔板打开后，河流的段数不会变。请注意不同寻常的空间限制！

第一行为两个整数 $n,q(1\le n \le 5 \cdot 10^5),(1\le q\le 5 \cdot 10^5)$ ，分别表示河流的段数和管理的天数。
第二行为 $n$ 个整数 $a_i(1\le i\le n),(1\le a_i\le 10^9)$ ,表示每一段河流的颜色。
接下来 $q$ 行每行第一个数 $op(1\le op\le 2)$ 表示操作：
如果 $op=1$ ，则给出两个数 $l,r(1\le l\le r\le n)$ ，表示你需要将第 $l$ 至 $r$ 段河流的所有未打开的挡板打开；
如果 $op=2$ ，则给出一个数 $x(1\le x\le n)$ ，表示询问你第 $x$ 段河流的颜色是什么。
对于每次操作 $2$ ，输出一个整数 $ans$ ，表示第 $x$ 段河流的颜色。

解法：并查集。

每一次打开挡板，便将当前的河段与下一段河流合并，然后跳到下一段尚未与当前河段合并的河流继续合并。
本题卡空间把线段树卡掉了。

int n, m;
int a[N];
int fa[N];
int nx[N];
int get(int x) { return x == fa[x] ? x : fa[x] = get(fa[x]) ; }
void solve(){
	int q;cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)fa[i]=i,nx[i]=i+1;
	for(int i=1;i<=q;i++){
		int op;cin>>op;
		if(op==1){
			int l,r;cin>>l>>r;
			int g;
			while(nx[get(l)]<=r){//
//我们只关注当前点所在的集合根，所以get(L);
//看这个集合最多已经合并到哪，下一个要更新的点是谁
//,使用nx[get(l)]，如果大于r，说明这段河流挡板已经被打开过了


//下面是合并操作，我们找到当前要更新的点nx[get(l)]
//更新需要和他最新值比较，这需要找他的根y，从此x合并到y
//虽然nx指针没有更新，但是f更新了就够了
				int x=get(l),y=get(nx[x]);
				fa[x]=y;
				a[y]=max(a[x],a[y]);
				//nx[l]表示下一个和L不在同一个连通块的点
				//nx[get(l)]表示下一个和    L的的根节点      不在同一个连通块的点
				//本质上根节之间跳来跳去
				l=nx[x];
			}
		}
		else {
			int x;cin>>x;
			  cout << a[get(x)] << '\n' ;
		}
	}
}

白雪皑皑

题目背景

“柴门闻犬吠，风雪夜归人”，冬天，不期而至。千里冰封，万里雪飘。空中刮起了鸭毛大雪。雪花纷纷，降落人间。美能量星球（pty 在 spore 上的一个殖民地）上的人们被这美景所震撼。但是 pty 却不高兴，他不喜欢白色的世界，他觉得这样太单调了。所以他想对雪花进行染色，让世界变得多彩些。

题目描述

现在有 $n$ 片雪花排成一列。 pty 要对雪花进行 $m$ 次染色操作，第 $i$ 次染色操作中，把第 $((i\times p+q)\bmod n)+1$ 片雪花和第 $((i\times q+p)\bmod n)+1$ 片雪花之间的雪花（包括端点）染成颜色 $i$ 。其中 $p,q$ 是给定的两个正整数。他想知道最后 $n$ 片雪花被染成了什么颜色。没有被染色输出 $0$ 。

输入格式

输入共四行，每行一个整数，分别为 $n,m,p,q$ ，意义如题中所述。

输出格式

输出共 $n$ 行，每行一个整数，第 $i$ 行表示第 $i$ 片雪花的颜色。

样例 #1

样例输入 #1

样例输出 #1

提示

对于 $20\%$ 的数据满足： $n,m\leq 1000$ 。
对于 $40\%$ 的数据满足： $n\leq 8000$ ， $m\leq 10^6$ 。
对于 $80\%$ 的数据满足： $n\leq 5\times 10^5$ ， $m\leq 10^7$ 。
对于 $100\%$ 的数据满足： $1\leq n\leq 10^6$ ， $1\leq m\leq 10^7$ 。

保证 $1\leq m\times p+q,m\times q+p\leq 2\times 10^9$ 。

// Problem: P2391 白雪皑皑
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2391
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
//# define int long long
#define ull unsigned long long
#define pii pair<int,int>

#define baoliu(x, y) cout << fixed << setprecision(y) << x
#define endl  "\n"
#define debug1(x) cerr<<x<<" "
#define  debug2(x) cerr<<x<<endl
const int N = 1e6 + 10;
const int M = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-8;
int n, m;
int a[N];
int f[N];
int nx[N];
int ans[N];

//f[x]表示x后第一个可操作的节点。
int find(int x) { return x == f[x] ? x : f[x] = find(f[x]) ; }
void solve(){
	int q,p;
	cin>>n>>m>>p>>q;
	for(int i=1;i<=n;i++)f[i]=i;
	f[n+1]=n+1;
	for(int i=m;i>=1;i--){
		int tl=(i*p+q)%n+1;
		int tr=(i*q+p)%n+1;
		int l=min(tl,tr);
		int r=max(tl,tr);
		int j=l;
	while(j<=r){
		//下一个没被染色的点
		int tmp=find(j);//看一下j的根,也是下一个没被染色的点
		if(tmp==j){//根是自己，说明之前没染色
			ans[j]=i;
			f[j]=find(j+1);//染色了，维护这个关系。把j指向j+1的根节点
		}
		//j=tmp;
		j=f[j];//j跳到下一个没被染色的点
		if(j==n+1)break;//这里要注意，不然越界死循环，需要提前预处理一下
	}
		
	}
	for(int i=1;i<=n;i++)cout<<ans[i]<<endl;
	
	
}


int main() {
    cin.tie(0);
    
    ios::sync_with_stdio(false);

    int t;
   //cin>>t;
     t=1;
    while (t--) {
solve();
    }
    return 0;
}

2024迎新春多校G

在一个一维坐标轴上有 $n$ 个点，坐标分别为 $1,2,...,n-1,n$ 。初始的时候每个点上都有一个障碍物，坐标为 $i$ 上的障碍物坚固程度为 $a_i$ 。现在 $Bingbong$ 有 $m$ 次操作或者询问：

将坐标为 $p$ 上的障碍物的坚固程度减去 $x$ ，若减去后该障碍物的坚固程度小于等于 $0$ ，则该障碍物消失。
询问若一个人从坐标为 $p$ 的位置向右走，他最多可以到达哪个位置？（如果到达存在障碍物的坐标点或者到达坐标点 $n$ 则停止向右走）

https://ac.nowcoder.com/acm/contest/73955/G

我们用f[x]记录从x开始下一个没被干掉的障碍物，每次修改操作的时候，我们去判断会不会把障碍物消灭，如果消灭，那我们去找一下下一个位置已经拓展到哪了，也是就是find(pos+1),然后让x指向他，也就是赋值给f[x],这样就成功维护了这个链表并查集

int n, m;
int a[N];
int f[N];
int find(int x){
	if(f[x]==x)return f[x];
	f[x]=find(f[x]);
	return f[x];
}
void solve(){
	cin>>n;cin>>m;
	for(int i=1;i<=n;i++)f[i]=i;
	f[n+1]=n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=m;i++){
		int op;cin>>op;
		if(op==2){
			int pos;cin>>pos;
			f[pos]=find(pos);//这步很重要，在查询前要处理子节点
			cout<<f[pos]<<endl;
		}
		else {
			int pos,x;cin>>pos>>x;
			a[pos]-=x;
			if(a[pos]<=0){
				f[pos]=find(f[pos+1]);//合并的时候只维护了根节点得关系
			}
		}
	}
	
}