ABC 136 F - Enclosed Points

• 問題
• AC
• AC (range tree)
• AC (range tree with fractional cascading)

各点$i \in S$について、$i$が何回数えられるかを求めればよいので、包除を考えるのがよさそう。点$i$の上下左右の領域にある点の集合$L, R, D, U \in S$を定める:

$L(i) := \{(x, y) \in S| x<x_i\} \\ R(i) := \{(x, y) \in S| x_i < x\} \\ D(i) := \{(x, y) \in S | y<y_i\} \\ U(i) := \{(x, y) \in S| y_i < y\}$

点$i$を含む$S$の部分集合の総数は

$2^N - 2^{|L(i)|}-2^{|R(i)|}-2^{|D(i)|}-2^{|U(i)|} \\ +2^{|L(i) \cap U(i)|}+2^{|L(i) \cap D(i)|}+2^{|R(i) \cap U(i)|}+2^{|R(i) \cap D(i)|}-1$

で求まるので、これを$i \in S$について足し合わせればよい。¹

さて、$|L(i)|, |R(i)|, |D(i)|, |U(i)|$は点を$x$座標や$y$座標についてソートしておけば尺取り法や二分探索等でそれぞれ求まる……が、よく見ると$x_i \neq x_j, y_i \neq y_j (i \neq j)$という条件があるので、単に整数$0, 1, ..., N-1$が1回ずつ現れるだけであった。したがって、

$\begin{aligned} & \sum_{i \in S}\bigl(2^N-1 - 2^{|L(i)|}-2^{|R(i)|}-2^{|D(i)|}-2^{|U(i)|} \bigr) \\ & = N \cdot (2^N-1) - 4 \cdot (2^0 + 2^1 + ... + 2^{N-1}) \\ & = (N-4)(2^N-1) \end{aligned}$

である。

次に$|L(i) \cap D(i)|, |L(i) \cap U(i)|, |R(i) \cap D(i)|, |R(i) \cap U(i)|$を求める。$(x_i, y_i)_{i \in \{1, ..., N\}}$を$x$座標についてソート済み($x_1 \le x_2 \le ... \le x_N$)とする。順序付きの集合$O$を用意して、$y_1, y_2, ..., y_N$の順に$O$に入れていく時、点$i$を処理した時点で$O$の中の$y_i$未満の点の総数は$|L(i) \cap D(i)|$に等しく、$y_i$より大きい点の総数は$|L(i) \cap U(i)|$に等しい。同様のことを逆順$y_N, y_{N-1}, ..., y_1$でやれば$|R(i) \cap D(i)|, |R(i) \cap U(i)|$が求まる。

---

2Dのクエリを処理できるデータ構造があればテクニックが無くてもできそう。2Dセグメント木とかウェーブレット行列とかいろいろあるようだが、このスライドを眺めていて、とりあえずrange treeがすぐに書けそうに見えたので書いた。かなり重いが一応通った。

fractional cascadingでオーダーを落とすやつも書いた。

---

1. 最後の$-1$は空集合を除いている。 ↩︎