Educational Codeforces Round 10 D. Nested Segments

http://codeforces.com/contest/652/problem/D

問題概要

n 個の区間 [L_i, R_i] が与えられる。i 番目の区間が含む区間の個数をすべての i に対して求めよ。

解法

BIT を使う。

区間の左端が小さい方から処理していき、処理した区間は削除する。このようにすると、ある区間 [L, R] を処理するとき未処理の区間の左端は必ず L 以上になる。

あとは右端が R 以下の区間の個数が求まればよく、これは BIT で処理できる。 最初に右端に 1 を加算しておき、区間を削除するときに右端に -1 加算すればいい。

具体的な動作は次のスライドを参照。

Educational Codeforces Round 10 D. Nested Segments from pekempey

左端と右端を座標圧縮しないと BIT が使えない。

BIT を unordered_map で動的化させたコードも通るには通ったが 1652 ms も掛かった。

• 添字が負だとバグるので適当に下駄を履かせる。
• あらかじめ reserve しておかないと TLE する。

という点に注意。

Educational Codeforces Round 10 D. Nested Segments

BIT に慣れてれば簡単。