POJ 2892: Tunnel Warfare

問題

街がN個ならんでいて、ある街iはi-1の街とi+1の街と接続されている(両端は除く)。このとき、街を破壊するクエリ、最後に壊された街を復旧するクエリ、そして、指定された街からみて、連続な破壊されていない街の数を答えるクエリの3つがM個与えられる。素早くクエリを処理せよ。

制約条件

1 <= N, M <= 50000

解法

情報の見方を少し変えて、左からi番目の街までに壊された街の数を配列a[1],…,a[N]を計算する。

すると、連続な破壊されていない街の数は、指定された街iが持つ数a[i]の配列中でのlower_boundとupper_boundの差から1を引いたものになる。

もう少し噛み砕いて言うと、a[i]以上のものが初めて配列中に現れる番号がlower_boundで、a[i]より大きいものが初めて配列に現れる番号がupper_boundで、その差から1を引いたものになる。

で、情報をどう持つかというと、BIT上にa[i]を持って、更新のクエリの処理が素早く行えるようにしておく。


別解

上のBITを使ったコードの計算量はO(M(logN)^2)になるのですが、実はBITを使わなくてもsetを使った方法でO(MlogN)の解法があります。

こっちの方が実装も簡単なんだけど、なぜかBITを使ったコードの方が結果は早かったです(BITの方は360ms, setの方は547ms)。

STLの実装の問題で、オーバーヘッドが結構あるんでしょうか?わかる人がいたら教えてください(笑)。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です