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

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

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

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

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

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

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

解法：并查集。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
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 却不高兴，他不喜欢白色的世界，他觉得这样太单调了。所以他想对雪花进行染色，让世界变得多彩些。

题目描述

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

1
2
3
4
4
3
2
4

样例输出 #1

1
2
3
4
2
2
3
0

提示

  • 对于 20%20\% 的数据满足：n,m≤1000n,m\leq 1000。
  • 对于 40%40\% 的数据满足：n≤8000n\leq 8000，m≤106m\leq 10^6。
  • 对于 80%80\% 的数据满足：n≤5×105n\leq 5\times 10^5，m≤107m\leq 10^7。
  • 对于 100%100\% 的数据满足：1≤n≤1061\leq n\leq 10^6，1≤m≤1071\leq m\leq 10^7。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
// 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

在一个一维坐标轴上有 nn 个点，坐标分别为 1,2,...,n−1,n1,2,...,n-1,n。 初始的时候每个点上都有一个障碍物，坐标为 ii上的障碍物坚固程度为 aia_i。 现在BingbongBingbong有 mm 次操作或者询问：

  1. 将坐标为 pp 上的障碍物的坚固程度减去 xx，若减去后该障碍物的坚固程度小于等于00，则该障碍物消失。

  2. 询问若一个人从坐标为 pp的位置向右走，他最多可以到达哪个位置？（如果到达存在障碍物的坐标点或者到达坐标点nn 则停止向右走）

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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]);//合并的时候只维护了根节点得关系
			}
		}
	}
	
}