Codeforces #187 Div2 B "Sereja and Array"
問題
http://codeforces.com/contest/315/problem/B
訳
セレジャは a1, a2, ..., an. というn個の整数で構成される配列を持っていた。セレジャはやんちゃボーイだったため、m個のオペレーションを完了させようとしている。各オペレーションは以下のような3種類がある。
op1. 配列のv_i番目の要素をx_iにする。 言い換えるならば、a[v_i] = x_iとする。 op2. 配列の各要素をy_i増加させる。 言い換えるならば、a[i] = a[i] + y_i ( 1 <= i <= n )とする。 op3. 配列のq_i番目の要素を紙に書き出す。つまりa[q_i]を出力する。
セレジャを助けるため、オペレーションの結果を出力せよ。
制約
1 <= n, m <= 10^5
考えた事
op2が実行されたとき、追加番号(シーケンス)と追加の総和を関連付けておく。
op1が実行されたとき、配列の初期値をセットし、その時の追加番号を持っておく。
op3が実行されたとき、初期値 + その時の追加番号 - 初期値がセットされたときの追加番号
ソースコード
int a[100050]; int addSum[100050]; int difIndex[100050]; int main() { int n, m; cin >> n >> m; for( int i = 1; i <= n; i++ ){ cin >> a[i]; } addSum[0] = 0; int addIndex = 0; memset( difIndex, 0, sizeof(difIndex) ); for( int i = 0; i < m; i++ ){ int op; cin >> op; if( op == 1 ){ int v, x; cin >> v >> x; a[v] = x; difIndex[v] = addIndex; } if( op == 2 ){ int y; cin >> y; addSum[addIndex + 1] = addSum[addIndex] + y; addIndex++; } if( op == 3 ){ int q; cin >> q; int res = a[q] + addSum[addIndex] - addSum[difIndex[q]]; cout << res << endl; } } }