公式解説で述べられている平衡二分木を利用した方針の概要です。

列 \(((1, X'_1), (2, X'_2), \ldots, (N, X'_N))\) を平衡二分木で管理します。ただし、\(X'_i\) が等しい \(i\) が複数あれば、その内最小の \(i\) だけを管理します。例えば \(X' = (1, 1, 1, 2, 4, 4, 5)\) は \(((1, 1), (4, 2), (5, 4), (7, 5))\) という形で管理されます。

\(((1, 1), (4, 2), (5, 4), (7, 5))\) に対して \(X'_3 \gets 4\) と更新するクエリが来れば、列は \(((1, 1), {\color{blue}\underset{\text{削除}}{\underline{(4, 2), (5, 4)}}}, (7, 5)) \to ((1, 1), {\color{red}{\underset{\text{追加}}{\underline{(3, 4)}}}}, (7, 5))\) と変化します。また、 \(((1, 1), (3, 4), (7, 5))\) に対して \(X'_4 \gets 2\) と更新するクエリが来れば、列は\(((1, 1), {\color{blue}\underset{\text{削除}}{\underline{(3, 4)}}}, (7, 5)) \to ((1, 1), {\color{red}{\underset{\text{追加}}{\underline{(3, 2), (5, 4)}}}}, (7, 5))\) と変化します。

クエリによって挿入される要素は高々 \(2\) つです。一方、削除される要素は最大で \(N\) 個程度になります。しかし、削除される要素の個数の総和は挿入された要素の個数の総和で抑えられることに注目すれば、全体では \(O(N+Q)\) 個しか削除されません。

以上で本問題を \(O((N + Q) \log N)\) 時間で解くことができました。

実装例 (C++, 172ms)