蓝桥杯2019年第十届省赛真题-修改数组

题目

题目链接

题解

思维+并查集。

难的不是使用并查集，而是看出来能用并查集。

由于之前做过，有点印象，所以一下想到了并查集

大概一说，fa[x]表示x要更新到多少，每次将x的fa更新为多少？更新为x+1？不一定，这得看x+1更新到了多少，如果x+1在之前都更新到了x+k，那么x肯定不能仅更新到x+1，而是更新到x+k+1。整体来看，我们x的更新取决于x+1，x +1取决于x+2，……这些数的fa值都可以指向同一个数x+k+1。有点并查集的意思吧。

题解连接

注意卡cin，cout。

具体题解看别人的吧，懒得写了，下午摆烂了，所以晚上得刷够六道题补回来。

代码

#include
using namespace std;
const int N = 1e6+10;

int n, x, fa[N];

int find (int x) {
	return fa[x] == x ? x : fa[x] = find (fa[x]);
}
 
int main()
{
	cin >> n;
	for (int i = 0;i