AOJ 2170 Marked Ancestor

問題

Marked Ancestor | Aizu Online Judge

木に対してノードをマークするというクエリと、あるノードに対してマークされた最も近い祖先を答えるというクエリに答えよ。

解法

ノードをマークするというクエリは子全体に対するmax更新クエリとみなせ、最も近い祖先を答えるクエリは子に記録されたmaxを答えるクエリとみなせる。

よってEuler Tour Technique + 遅延評価セグメント木 で殴る👊👊👊

$ O(n log{n}) $

コード