クエリ平方分割による解法を説明します。

以後、問題で与えられる無向グラフを \(G\)、頂点集合を \(V\coloneqq\{1,\ldots,N\}\) とします。

まず、ある正整数 \(B\) を決めておき、クエリを \(B\) 個ずつに分割し、各ブロックごとにクエリを処理することを考えます。

いま、あるクエリのブロック \((x_l,\ldots,x_r)\) を処理したいとします。ここで、ブロックの処理の開始時点で、すべての \(i\in\{1,\ldots,N\}\) に対して頂点 \(i\) に書かれている値 \(\mathrm{ans}[i]\) が正しく求まっていると仮定します。逆に、この仮定を破らないために、ブロックの処理の終了時点で \(\mathrm{ans}\) は正しく求まっている必要があることに注意します。

クエリ \(x_l,\ldots,x_r\) を処理する過程において、\(x_l,\ldots,x_r\) の中に現れないような頂点の更新はブロックの処理の最後にまとめて行ってもよいです。そこで、\(x_l,\ldots,x_r\) の中に現れる頂点だけを集めた集合 \(X\coloneqq\{v\in V\mid \exists i\in\{l,\ldots,r\}\;\mathrm{s.t.}\;x_i=v\}\) による 誘導部分グラフ \(G[X]\) を構築しておき、各クエリは \(G[X]\) に対するクエリとして処理します。

\(G[X]\) の構築は \(O(N+M+B)\) で行うことができます。また、\(\vert X\vert\leq B\) なので、各クエリは愚直に計算しても一回当たり \(O(B)\) で処理することが出来ます。従って、この部分の計算量は \(O(N+M+B^2)\) です。

さて、クエリたちを \(G[X]\) に対するものと読み替えたので、すべての \(v\in X\) に対しては \(\mathrm{ans}[v]\) が正しく求まっていますが、\(v\not\in X\) であるような頂点に対しては更新が反映されていません。

頂点 \(v\not\in X\) に対しては、\(v\) に隣接する頂点に対するクエリのうち、最新のものさえ分かればよいです。従って、各頂点に対して最新のクエリの情報、すなわち、クエリの時刻とその当時に書かれていた値の組を持っておけばよいです。

以上より、全体 \(O((N+M+B^2)\cdot Q/B)\) でこの問題が解けました。例えば \(B=\lfloor\sqrt{Q}\rfloor\) とすれば、\(O((N+M+Q)\sqrt{Q})\) となります。

C++ による実装例 (1710 ms)

C++ で 1700ms 以上掛かっているため、例えば PyPy のような比較的遅いと言われる言語で本解法により AC することは難しいと思われます。しかし、実測においては \(B\) を上記提出のように \(\sqrt{Q}\) 付近に設定するのが最適とは限らず、値をうまく調整することで高速化されて AC できることがあります。実際に、以下の PyPy による提出は \(B=7000\) とし、その他細かい高速化を施すことで 1427 ms で通っています。

PyPy による実装例 (1427 ms)

その他言語:

Java による実装例 (1287 ms)