AOJ 2450 Do use segment tree

LC木の理解が浅かったため、図が微妙に間違っています。気をつけてください。

HL 分解+遅延 segment tree でも解けるが、ここでは link-cut tree で解く。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2450

問題

木と Q 個のクエリが与えられる。クエリは次の 2 種類である。

  • a-b パス上の値を c に書き換える
  • a-b パス上の連続部分列の和の最大値を求める

解法(列の問題)

分割統治法を使う。区間 S を区間 SL,SR に分割して、

  • 区間 SL に完全に含まれる最大部分列
  • 区間 SR に完全に含まれる最大部分列
  • 区間 SL, SR をまたぐ最大部分列

のうち最大のものを求めればいい。もし segment tree で解くのであれば、

  • [*,*] の形の最大部分列
  • [l,*] の形の最大部分列
  • [*, r] の形の最大部分列
  • [l,r] の総和

を各ノードに持たせてあげるといい。

link-cut tree の使い方

HL 分解で解けそうなパスクエリの問題を link-cut tree で解く場合、以下の機能を実装するといい。

  • expose(v): v から root へパスを繋げる
  • link(u,v): u の親を v とする
  • evert(u): u を根とする

この辺の実装方針は プログラミングコンテストでのデータ構造 2 ~動的木編~ に書かれている。

これらを使って u-v パスクエリを処理するにはどうすればいいか。

まず link を使って木を構築する。

f:id:pekempey:20160525193908p:plain:w400

evert(u) をする。

f:id:pekempey:20160525193912p:plain:w400

expose(v) をする。

f:id:pekempey:20160525193919p:plain:w400

※この図なんだけど、本来はvのすぐ下でパスが切れてます。

evert(u)→expose(v) という操作をすることで、u-v クエリを root-v クエリに変えることができた。さて、このとき u,v が属するパスは v が根で、u が最も左の子であるような二分木になっている。さらによく処理を見ると、v の右部分木は存在しない。

f:id:pekempey:20160525194212p:plain:w400

※この図はvの右部分木が null になっているのが正しいです。

よってパスの値は v を見るだけで分かる。

たとえば総和クエリであれば、二分木には部分木の総和を持たせておけばいい。


マージする向きが関係してくるパスクエリの場合 link-cut tree の方が精神的に楽。もう少し改良したい。

gist.github.com

平衡二分探索木系の遅延評価に慣れてれば、そこまで実装が難しいという訳ではなさそう。といいつつ、splay 木の原理がよく分かってないので危ない実装をしてるかもしれない。