こちらのユーザー解説と同様ですが、Gitの概念を用いて説明します。

永続SegmentTreeは強力ですが、整備していない人も多いでしょう。

この問題ではどの時点の状態からどのような変更があったかを管理できれば十分です。 これはGitでのバージョン管理に似ていて、

• \(A_i\)をbranch \(i\)
• branch \(i\) のHEADは commit hash \(P_i\)を指す

と思えば、

• 操作1: branch \(X_i\)のHEADをbranch \(Y_i\)のHEADにresetする
• 操作2: branch \(X_i\)のHEAD \(P_{X_i}\)から\(data[Y_i]\)を\(Z_i\)に書き換えcommitを行う

に対応します。

Gitのcommit hashの関係が木構造のようになっていることを考えると、 Fenwick Treeなど点加算・区間和取得が高速にできるデータ構造を持つことで、 クエリを先読みしてオイラーツアーの要領で解くことができます。

具体的にはDFSの行きがけがcommit履歴を進め(点加算)、戻りがけで親commitにcheckout(ロールバック)することに対応します。

詳細はコードを読むのが早いでしょう。

実装例 C++ 68ms

※Gitの仕組みは実際にはもっと複雑で面白いです。