AtCoder ABC206D KAIBUNsyo 题解

思路

观察到替换数字的过程，实际上就是将两个数字归为一类。借此不难联想到并查集的工作过程，因此我们可以考虑使用并查集解决这个问题。

我们使用并查集维护当前数字所属的集合，初始时对于数字 \(x\)，它位于集合 \(x\) 中。当我们发现本应相同但是并不在同一个集合内的数字时，我们不得不将其合并，并记录下一次操作。在操作的过程中，你不需要去判断究竟是改为了左边的或者右边的数字，只需要知道它们二者同属一个集合即可。需要注意的是，对于 \(a_i\)，他一开始属于集合 \(a_i\) 而不是集合 \(i\)，这个搞得我调了好一会儿，服了。

简单分析可以得到，程序的时间复杂度控制在了极其优秀的 \(\mathcal{O}(n \,\alpha(n))\)。

代码

#include <iostream>

#define int long long
#define get(x) (n - x + 1)

using namespace std;

int n, fa[200009], a[200009];

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

signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        fa[a[i]] = a[i];
    }
    int ans = 0;
    for (int i = 1; i <= n / 2; i++) {
        if (find(a[i]) != find(a[get(i)])) {
            fa[find(a[i])] = find(a[get(i)]);
            ans += 1;
        }
    }
    cout << ans;
}