Codeforces Round #427 C. Star sky
最大100x100の領域に、n個の星が(x[i], y[i])に初期の明るさs[i]で配置されている。星の明るさの最大値はcであり、時間ごとに1づつ増えていき、cに到達すると次の時間に0に戻り、また1づつ増えていく、を繰り返す。この時、q個のクエリ (t[i], x1[i], y1[i], x2[i], y2[i]) 「時刻t[i]に於ける左上が(x1[i], y1[i]), 右下が(x2[i], y2[i])の長方形領域の星の明るさの合計値を求めよ」に応答せよ。
星をmod (c+1)で分類し、c+1個の2次元累積和を作成しておく。すると初期明るさv(0<=v<=c)の星の数がそれぞれO(1)で計算できる。この星は時刻t[i]の時点で(t[i] + v) % (c+1) であるので、結局クエリがO(c)で回答できる。全体ではO(qc)。
