Znzryb's Blog
0%

ABC-380- E - 1D Bucket Tool（一维填色工具，桶工具）（维护权相等联通块）

Posted on Edited on

思路讲解

前置知识：并查集，以及如何维护联通块数量和上下限

主要思路就是我们把颜色相同且连在一起的作为一个联通块，如果对这个联通块进行染色，就把根节点染一下颜色，然后看左界-1颜色和右界+1颜色，看看要不要合并。

至于数颜色数量嘛，需要用到维护的该联通块数量

1
2
3
4
5
6
7
8
9
inline void changeColor(ll x,ll c){
	ll fax=find(x);
	// 现在把这个联通块改成c这个颜色
	// 所以c现在这个颜色有的块数量加上该联通块块数量
	colorCnt[c]+=Cnt[fax];
	// 原来的这一颜色拥有的块数量自然是要减的
	colorCnt[color[fax]]-=Cnt[fax];
	color[fax]=c;
}

AC代码

https://atcoder.jp/contests/abc380/submissions/61033055

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cctype>
#include <array>

using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(5e5)+10;
ll n,T,q;
ll color[N],fa[N];
// color是这个联通块的颜色，只有始祖节点有意义
// fa是并查集的数组
// Cnt 记的是这个联通块的数量
ll Cnt[N];	// 当然，只有始祖节点的Cnt才是有意义的
// colorCnt记载的是这个颜色的数量
ll colorCnt[N];
// lr 记载该联通块的左右界,同样只有始祖节点的才有意义
struct upBoundLowBound{
	ll l,r;
}lr[N];

inline ll find(ll x){
	if(x>n || x<1)
		return 0;
	if(fa[x]==x)
		return x;
	fa[x]=find(fa[x]);
	return fa[x];
}

inline void merge(ll x,ll y){
	ll fax=find(x),fay=find(y);
	if(fax==fay)
		return;
	fa[fax]=fay;
	// 处理联通块子节点数量合并
	Cnt[fay]+=Cnt[fax];
	// 处理上下界合并
	lr[fay].l=min(lr[fax].l,lr[fay].l);
	lr[fay].r=max(lr[fax].r,lr[fay].r);
}

inline void changeColor(ll x,ll c){
	ll fax=find(x);
	// 现在把这个联通块改成c这个颜色
	// 所以c现在这个颜色有的块数量加上该联通块块数量
	colorCnt[c]+=Cnt[fax];
	// 原来的这一颜色拥有的块数量自然是要减的
	colorCnt[color[fax]]-=Cnt[fax];
	color[fax]=c;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>q;
	// 初始化
	for(int i=1;i<=n;++i){
		color[i]=i;
		fa[i]=i;
		Cnt[i]=1;
		colorCnt[i]=1;
		lr[i].l=i;
		lr[i].r=i;
	}
	for(int _=1;_<=q;++_){
		ll op,x,c;
		cin>>op;
		if(op==1){
			cin>>x>>c;
			changeColor(x, c);
			ll lowfa,upfa,fax;
			fax=find(x);
			lowfa=find(lr[fax].l-1);
			upfa=find(lr[fax].r+1);
			if(color[upfa]==c)
				merge(x,upfa);
			if(color[lowfa]==c)
				merge(x,lowfa);
		}else{
			cin>>c;
			cout<<colorCnt[c]<<endl;
		}
	}
	return 0;
}

/*
WA https://atcoder.jp/contests/abc380/submissions/61030202
wa了8个，等等看看问题出在哪
5 6
1 5 4
1 4 2
2 2
1 3 2
1 2 3
2 3

*/

心路历程（WA，TLE，MLE……）

WA https://atcoder.jp/contests/abc380/submissions/61030202

原因是我们还要维护一个块的上界和下界，以确定他是否和其他联通块因为颜色相同而相连。