Hatena::Grouptopcoder

週刊 spaghetti_source

2012-09-09

次回予告

00:01

次回は次の問題に答えるテクニックを紹介します.興味のある人は考えてみてください.ネタバレ禁止とかは特に無いので,解答を思いついた方は是非トラックバックでも飛ばしてください(=宣伝活動).

ちなみに:問題1は多くの人が解けると思います.事前知識なしで問題2を思いついた方は自慢できます.1・2は実装量はたいしたことはありません.


問題1(簡単)

n 個の数が与えられる.クエリとして

  • get(i): i 番目の数を返す
  • addRange(i, j, x): i~j 番目の数に x を足す

がたくさん飛んでくるので,答えよ.


問題2(普通)

n 個の数が与えられる.クエリとして

  • get(i): i 番目の数を返す
  • addRange(i, j, x): i~j 番目の数に x を足す
  • minRange(i, j): i~j 番目の数の中で最小の値を返す

がたくさん飛んでくるので,答えよ.


問題3(難)

n 個の数が与えられる.クエリとして

  • get(i): i 番目の数を返す
  • addRange(i, j, x): i~j 番目の数に x を足す
  • minRange(i, j): i~j 番目の数の中で最小の値を返す
  • insert(i, x): i 番目に新たに数 x を挿入する
  • remove(i): i 番目の数を削除する

がたくさん飛んでくるので,答えよ.

iwiwiiwiwi 2012/09/10 10:29 http://poj.org/problem?id=3580 これに含まれていると思いますし,同様に普通の平衡二分探索木でできると思います.もしもっとマニアックなデータ構造じゃないと出来ない問題にしたいなら,もっと変なクエリが必要だと思います.

spaghetti_sourcespaghetti_source 2012/09/10 13:50 既出だとは思っていましたが,まさかそのままより一般の問題があるとは思っていませんでした.

想定は普通の平衡二分探索木で,回転時に適切な更新を要するアレでしたが,addを遅延評価するのが主流みたいで,確かにそのほうが実装容易ですね.ぐぬぬ.

ゲスト



トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/spaghetti_source/20120909