Codeforces #406 (Div. 1) B: Legacy

解法

セグメント木の上でダイクストラ

セグメント木にある各頂点でダイクストラする。
もう少しきちんと説明する。
まず、
操作2について考えてみる
v->[l, r]
であった。
[l, r]は、セグメント木のいくつかの対応する頂点に分解できる。(図1)
この頂点はたかだかlog(n)個。
あるセグメントxへ移動できるならば、その子孫のセグメントへも移動できる。
セグメントxの表す範囲をs(x)のように表すと
s(y)⊆s(x)であるようなすべてのセグメントyへ移動できる。(図2)
なので、すべてのセグメント木上の頂点について、あらかじめ親から子へコスト0の辺を張っておく。
あとは操作2ごとに、v->セグメントxへコストwの辺を張る。

操作3について考えてみる
[l,r]->v
であった。
先と同様に[l,r]をいくつかのセグメントに分解できる。
その一つをセグメントxとしたとき、
s(y)⊆s(x)であるようなすべてのセグメントからvへ移動できるはず。
なので、先とは逆にあらかじめ子から親へコスト0の辺を張っておき、(図3)
あとは操作3ごとに、セグメントx->vへコストwの辺を張る。

操作1は操作2,操作3の1種なので解けている。

ただ、操作2と操作3は一緒に処理しようとするとうまくいかない。
操作2の準備として親から子へコスト0の辺を張った。また操作
3の準備として子から親へコスト0の辺を張った。
これでは任意の親子間でコスト0の双方向の辺があることになり、任意の頂点間の距離が0となってしまい
うまくいかない。

ここで一工夫する。
セグメント木を2個作って行き来させる。2個のセグメント木をそれぞれS,Tとする。
Sは子から親へのコスト0の辺を持ち(図2)、Tは親から子へのコスト0の辺を持つ(図3)。
操作2,3の辺を張るのはいずれもS->Tとセグメント木を横断するようにする。
またTの任意の頂点から、Sの対応する頂点へコスト0の辺を張る。(図4)

わかりづらいので、このグラフの意図を。
Sのグラフ上の頂点は、その頂点から移動できるようになるまでのコストを持ち、
Tのグラフ上の頂点は、ある操作によってその頂点に到達するまでのコストを持つ。
セグメントx「へ」移動できるならセグメントx「から」移動できるはず。だから、コスト0の辺をTからSへ張ったのだった。

あとは、このグラフでダイクストラするだけ。