Codeforces #12 D Ball

問題非常簡短﹕給了 $N$ 個三維空間的點，問有多少個點 $i$ 使得存在點 $j$ 令 $x_i < x_j, y_i < y_j, z_i < z_j$ 。 $1 \le N \le 500000$ ， $0 \le x_i, y_i, z_i \le 10^9$ 。

其實做法非常經典，屬練習題程度，可是我比較笨，老是想不出正確的方法。

為 $x_i$ 排序，然後把 $y_i$ 離散化。按 $x_i$ 從大至小遍歷，則問題等價於找出 $y_i < y_j$ 並且 $z_i < z_j$ 。再把問題重新看一下則是尋找 $\max_{j: y_i < y_j}\{z_j\}$ 。因 $y_i$ 已離散化則不妨把它看成位置，現求在點 $i$ 的情況下，範圍 $j \in [y_i+1, M]$ 內 $z_j$ 的最大值，當中 $M$ 是指 $y_i$ 有多少個不同的數值(即離散化後的最大值)。如此一來即是求範圍內最大值，線段樹秒殺之。

注意題目要求的是 $x_i < x_j$ 。遍歷 $x_i$ 值從大至小的時候要把相同的 $x_i$ 值暫緩更新，否則會出錯。附一樣例作例子。

3
0 0 0
0 0 1
0 0 1