算法
(计算连通分量的大小) $O(M)$
把每一对两个数不相等的 $(a_i, a_{n - 1 - i})$ 连边,对于同一个联通分量内的所有点可以用同一个整数替代,所以答案就是每个连通分量的大小减一做累加和。
C++ 代码
#include <bits/stdc++.h>
#include <atcoder/all>
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using namespace atcoder;
int main() {
int n;
cin >> n;
vector<int> a(n);
rep(i, n) cin >> a[i];
const int M = 200005;
dsu d(M);
rep(i, n) d.merge(a[i], a[n - 1 - i]);
int ans = 0;
rep(i, M) {
if (d.leader(i) != i) continue;
ans += d.size(i) - 1;
}
cout << ans << '\n';
return 0;
}