週刊 spaghetti_source

次回予告

00:01

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

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

問題１（簡単）

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

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

がたくさん飛んでくるので，答えよ．

問題２（普通）

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

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

がたくさん飛んでくるので，答えよ．

問題３（難）

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

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

がたくさん飛んでくるので，答えよ．