WARush

SRMの結果とか、解けた問題のコードを書いていきます

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;
        }
    }
}