Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

JOI Open Contest 2015 - Sterilizing Spray

しばらく競プロをやっていなかったのと、ちょっと卒論の気晴らしをしたかったので、昔解いていなかった問題を漁ってました。
結果恐ろしいくらい時間を溶かしました……今から進捗出します。ごめんなさい(´;ω;`)

ジャッジもテストデータも今は無いので、サンプルを通した程度で解けたものと判断しています。
愚直解とあとで出力を比較してみます。

問題概要

 N 要素からなる配列  C と、整数  K が与えられる。次の 3 つのタイプのクエリを合計  Q 個処理せよ。

  1.  a_i 番目の要素の値を  b_i に書き換える。
  2.  l_i 番目の要素から  r_i 番目の要素を  K で割る。小数点以下は切り捨てる。
  3.  l_i 番目の要素から  r_i 番目の要素までの和を求める。
  •  1 \leqq N, Q \leqq 10^5
  •  1 \leqq K \leqq 10
  •  1 \leqq C_i, b_i \leqq 10^9
続きを読む