3/17 PKU

2481 Cows

牛が何頭かいる。牛はそれぞれ範囲を持っている。牛Aの範囲が、牛Bの範囲を完全に含み、かつ完全に一致はしないとき、牛Aは牛Bより強い。各牛について、その牛より強い牛の数を求めよ。

X軸に範囲の左端、Y軸に範囲の右端をとった散布図を書いてみると、平面走査×Segment Treeで解ける。範囲が完全に一致する牛の処理に注意。