読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

±RMQによるLCAの実装

構築 O(n) 質問 O(1) のやつ。AOJ の以下の問題で verify した。 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_C 基本的には euler-tour + sparse table RMQ。euler-tour したときの深さ列が ±1 で変化することを利用して高速化する。 …