yukicoder No.743 Segments on a Polygon

問題

M頂点の凸多角形の頂点同士をN本順番に線分で結ぶ。
このとき、頂点は一度線分に使われたら2度は選ばれない。
i番目に結んだ線分の頂点a_iとb_iの情報が与えられるので、追加した線分同士の交点の総数を答えよ。
(もし、ある交点が複数の線分からなる場合は、1つの交点ではなく、各線分同士の交点として数え上げる)

制約

• 1 <= N <= 10^5
• 3 <= M <= 2*10^5
• 0 <= a_i, b_i < M

解法

頂点a_iとb_iを結ぶときは、始点終点ではないので、a_iとb_iを交換してもかまわないことがわかる。以下、a_i < b_iで考える。
重要な性質として、「頂点を結ぶ順番は関係ない」ということに気付く必要がある。

交点ができるケースを考えるために、多角形を直線上にのばして、線分を曲線で表した以下のような図を考える。

今は、太線の線分を追加する場合を考える。
交点ができるケースは、①と③のケースで、a_iからb_iの間にある頂点に、a_i以下b_i以上の頂点からの線分がある場合になっている。

図の左側付近(①と②のケース)を考える。
左側から太線の交点を作る①(a_j, b_jとする)は、a_jがa_iよりも左側にあり、交点を作らない②(a_k, b_kとする)は、a_kがa_iよりも右側にある。
したがって、「頂点を結ぶ順番は関係ない」性質から、左側から順番に線分を追加していき、すでに結んだ頂点のうち、bにあたる部分がa_iとb_i内に何個あるか？がわかればよい。
これはBITなどでO(logM)で求められる。

図の右側付近(③のケース)を考える。
しかし、③を追加する場合を考えると、これは上記の①のケースに当たるので、太線の追加時には考えなくてよいことがわかる。

したがって、追加する線分のa_iを小さい方から順番に追加していき、追加した線分のb_iをBITなどで記録しつつ、a_j, b_jの線分を追加する場合は、a_jからb_j内に含まれるb_iの個数をカウントしていけばO(N log M)で求められる。