読者です 読者をやめる 読者になる 読者になる

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$
続きを読む