問題文

\(N\) 項からなる正整数列 \(A = (A_0,\ldots,A_{N-1})\) が与えられます。 以下の操作を \(0\) 回以上何度でも行える時、操作を最小何回行えば、 \(A\) を回文にすることができますか？

• ある正整数の組 \((x,y)\) を選ぶ。その後、現在 \(A\) に含まれる \(x\) をすべて \(y\) に置き換える。 なお、この問題では、全ての整数\( i (0\leq i \leq N-1)\) について、\(A_i =A_{N-1-i}\) が成り立つとき、またその時に限って、 \(A\) が回文であるといいます。

制約

• 入力はすべて整数

• \(1 \leq N \leq 2 \times 10^5\)

• \(1 \leq A_i \leq 2 \times 10^5\)

(解説の都合上、 \(A\) の添え字を 0-indexed にしています。)

STEP1　問題文の定式化

\(M\) を \(A\) のどの要素よりも大きな整数とします(例えば、 \(M = 200001\) とします)。 選ばれる整数はすべて \(M\) 未満として問題ありません。

各整数 \(x\ (0 \leq x \leq M-1)\) に対し、 すべての操作を行った後に置き換わる値を \(p(x)\) とおきます。 \(p(x) \neq x\) であるような \(x\) の個数が操作回数に対応します。

最終的に \(A\) は \((p(A_0),p(A_1),\ldots,p(A_{N-1}))\) に変化するので、これが回文であるためには、各 \(i\) に対し \(p(A_i) = p(A_{N-1-i})\) であることが必要です。

以上のことを踏まえると、問題文は次のように言い換えることができます。

\(N\) 項からなる正整数列 \(A = (A_0, \ldots, A_{N-1})\) が与えられます。また、次の条件を満たす写像 \(p:\{0,1,\ldots,M-1\} \to \{0,1,\ldots,M-1\}\) を考えます。

• すべての整数 \(i \ (0\leq i \leq N-1)\) に対し、 \(p(A_i) = p(A_{N-1-i})\) が成り立つ。
  

\(p(x) \neq x\) であるような \(x\) の個数としてありえる最小値を求めなさい。

以下では、「\(p(x) \neq x\) をみたす \(x\) の個数の最小値」の代わりに、「\(p(x) = x\) をみたす \(x\) の個数の最大値」を考えます。

STEP2　素集合データ構造の利用

\(p(A_i) = p(A_{N-1-i})\ (0 \leq i \leq N-1)\) をみたすような \(p\) について調べていきましょう。\(p\)で同じ値に写る要素同士が同じグループになるようなグループ分けがしたいです。そのために、素集合データ構造(disjoint set union)を利用します。

素集合データ構造とは、互いに共通部分を持たない集合の族を管理するデータ構造です。 \(A_i\) と \(A_{N-1-i}\) を同じ集合に含めるように、うまく族を構築しましょう。

まず、要素が1つの集合 \(M\)個 からなる族\((\{0\},\{1\},\ldots,\{M-1\})\) を用意します。 続いて、各 \(i (0 \leq i \leq N-1)\) に対して、順番に以下の操作を行います。

• \(A_i\) を要素に持つ集合と、 \(A_{N-1-i}\) を要素に持つ集合を併合する。

最終的にできる集合の族を、\((T_0, T_1, \ldots, T_{K-1})\) とおきます。 このとき、次の事実が成り立っています。

• 写像 \(p: \{0,1,\ldots,M-1\} \to \{0,1,\ldots,M-1\}\) に対し、以下の2つは同値である。
  • すべての\( i (0 \leq i \leq N-1)\) に対し、\(p(A_i) = p(A_{N-1-i})\) が満たされている
  • 要素\(x,y\) が同じ集合 \(T_k\) に含まれているとき、 \(p(x) = p(y)\) が満たされている

さて、\(p(x) =x\) であるような \(x\) の個数の最大値を求めることが課題でした。 実は、族に含まれる集合の個数 \(K\) がこのような最大値になります。以下そのことを示します。

最大値を \(K\) より大きくできないこと

各集合 \(T_k\) に対し、\(T_k\)の要素を \(p\) で移した値は一致するので、\(p(x) = x\) となる \(x\) は \(T_k\)の中に高々\(1\)つしかありません。よって、全体で考えても \(p(x) = x\) となる \(x\) は高々 \(K\)個です。

最大値を \(K\) にできること

各集合 \(T_k\) から1つずつ 要素\(s_k\) を選び、すべての\(T_k\) の要素 を \(s_k\) に移す写像 \(p\) を考えます。この \(p\) は条件をみたしており、\(K\) 個の整数 \(s_0, \ldots, s_{K-1}\) に対し \(p(x) = x\) が成り立っています。

以上により、素集合データ構造を用いることで、\(p(x) = x\) であるような \(x\) の個数の最大値 \(K\) を求めることができました。全体から \(K\) を引いた \(M -K\) が最終的な答えです。 計算量は \(O(M+N\alpha(M))\) なので、この解法は実行時間制限に間に合います。