問題 解法1 クエリ平方分割 もしクエリが1つしかない場合、以下の方法で求められる。 森の連結成分ごとに適当に根を取り、DFSで各頂点の親を求めると、各クエリについて、 と の親のいずれかが候補になるため、親を とすると、辺 と辺 が存在するかを、辺集…

問題 解法 以下 0-indexed とする。 の場合、区間を一方向に伸ばしながら Segment Tree 上の二分探索を行うなどして求める。 それ以外のとき、各 に対し、自身より大きい値か小さい値かしか興味がないので便宜上 + と - とおく。 (1) +0+ や -0- のとき この…