P8686. 修改数组

发表于 分类于 阅读次数： Waline： 本文字数： 406 阅读时长 ≈ 1 分钟

考点

  • 并查集

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
const int LEN = 1e6 + 50;
int n, fa[LEN];

int find(int x) {
  if (fa[x] == x) return x;
  return fa[x] = find(fa[x]);
}

int main() {
  int x, anc;
  cin >> n;
  for (int i = 1; i < LEN; ++i) fa[i] = i;
  while (n--) {
    cin >> x;
    cout << (anc = find(x)) << " ";
    fa[anc] = anc + 1;
  }
  return 0;
}

思路

并查集在搜索上的妙用

考虑以下例子：

  1. 初始状态下，数组为空；分别输入2、1，数组变成{2, 1}

  2. 再输入1，你会希望数组内的1元素指向3，这样就不必暴力地轮询加1

    如果输入2呢？你也希望数组内的2元素指向3

    塞入3后，数组变成{2, 1, 3}

  3. 再输入1，你希望数组内的1元素指向4

    如果输入2呢？你希望数组内的2元素指向4

    如果输入3呢？你还是希望数组内的3元素指向4

    塞入4后，数组变成{2, 1, 3, 4}

  4. 再输入1，你希望数组内的1元素指向5

    如果输入2呢？你希望数组内的2元素指向5

    如果输入3呢？你希望数组内的3元素指向5

    如果输入4呢？你还是希望数组内的4元素指向5

    塞入4后，数组变成{2, 1, 3, 4, 5}

发现了吗，每次查询的时候，我们都会希望原数组是个经过路径压缩后的并查集

所以每次查询完结点的祖先后，令祖先的祖先为祖先 + 1即可，代表下次查询应该指向的值