IOI 2018 day1 - Werewolf
解法
Union Find のマージ過程を表す木を構築することで、ある時点である頂点からたどり着ける頂点の集合を、Euler Tour 上の区間として表すことができる。
頂点番号の昇順 / 降順にマージを行う。ある頂点$ uの Euler Tour 上の位置をそれぞれ$ x_u, y_uとおくと、クエリにおいて$ S_iからたどり着ける集合と$ E_iからたどり着ける集合が共通部分を持つかどうかの判定は、二次元矩形領域の点の数え上げによって行うことができる。
感想
地味に今まで知らなかったタイプの典型だった