競プロ典型 90 問 017 - Crossing Segments 解説

準備やりました．

問題リンク(Twitter/原案) 問題リンク(AtCoder/OJ)

これも QCFium 法が通ったので，制約が上がりました．

解説

小課題は略

円環の問題だが，実は好きなところで切って考えられる． 互いに被覆し合わない，重なる区間の組の数が数えたい．これは，次のようにして数えられる．

• 区間を終点順でソートする．
• 配列の $l_i$ 番目にある値を答えに加算し，$[l_i+1,r_i-1]$ の要素に $1$ を加算する．
• これを全ての区間に対して順に行い，最後に答えを出力する．

区間加算一点取得のクエリは，一点加算区間取得クエリの双対問題として，Binary Indexed Tree(Fenwick Tree) を使うことで高速に実現できる．計算量は，$O(N+M(\log N+\log M))$ となる．