Codeforces #187, Division 2, B : Sereja and Array

問題文

http://codeforces.com/contest/315/problem/B

概要

n 項の数列 a が与えられる。
この数列に対する三種類のクエリが m 個来るので、これを処理せよ。

1. の要素を x にする
2. の要素に y を加算する
3. の要素を印字する

解法

個々の値と、全体に加算された値を別に管理すると考えます。
全体に加算された値を added すると、タイプ２のクエリは added に加算し、タイプ３のクエリは と added の和を印字すればよいことになります。
タイプ１のクエリは、全体が added 分のゲタを履いていると考え、 = x - added とするとうまく調整されます。

まとめると、各クエリの処理は次のようになります。

1. の値を x - added とする
2. added の値に y を加える
3. + added を印字する

別解

区間加算のセグメント木を貼り付ける
（本番はこっちで通しましたが、この場に於いてはもはや冗談ですね……）

コード（別解もまとめて）

typedef long long LL;
typedef vector<int> VI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )

// セグメント木のユーティリティ
inline const int chl( const int k )
{
	return k * 2 + 1;
}

inline const int chr( const int k )
{
	return k * 2 + 2;
}

inline const int mid( const int l, const int r )
{
	return ( l + r ) / 2;
}

// segment tree, range add, sum
class SegmentTreeRAS
{
private:
	const int N;
	vector<LL> data_overall, data_partial;

public:
	SegmentTreeRAS( const vector<LL> &src ) : N( src.size() ), data_overall( N * 4, 0 ), data_partial( N * 4, 0 )
	{
		REP( i, 0, N )
		{
			add( i, i + 1, src[i] );
		}

		return;
	}

	void add( const int a, const int b, const int x )
	{
		return add( a, b, x, 0, 0, N );
	}

	LL sum( const int a, const int b )
	{
		return sum( a, b, 0, 0, N );
	}

private:
	void add( const int a, const int b, const int x, const int k, const int l, const int r )
	{
		if ( b <= l || r <= a )
		{
			return;
		}
		else if ( a <= l && r <= b )
		{
			data_overall[k] += x;
		}
		else
		{
			data_partial[k] += (LL)( min( r, b ) - max( l, a ) ) * x;
			add( a, b, x, chl( k ), l, mid( l, r ) );
			add( a, b, x, chr( k ), mid( l, r ), r );
		}
	}

	LL sum( const int a, const int b, const int k, const int l, const int r )
	{
		if ( b <= l || r <= a )
		{
			return 0;
		}
		else if ( a <= l && r <= b )
		{
			return data_partial[k] + (LL)( r - l ) * data_overall[k];
		}
		else
		{
			LL res = (LL)( min( r, b ) - max( l, a ) ) * data_overall[k];
			res += sum( a, b, chl( k ), l, mid( l, r ) );
			res += sum( a, b, chr( k ), mid( l, r ), r );
			return res;
		}
	}
};
// SegmentTreeRAS( VI src )
// add( [ a, b ), x )
// sum( [ a, b ) )

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n, m;
	cin >> n >> m;

	vector<LL> as( n );
	FOR( a, as )
	{
		cin >> a;
	}

	SegmentTreeRAS st( as );

	LL added = 0;
	REP( i, 0, m )
	{
		int t, v, x, y, q;
		cin >> t;

		switch ( t )
		{
			case 1:
				cin >> v >> x;
				as[ v - 1 ] = x - added;
				st.add( v - 1, v, x - st.sum( v - 1, v ) );
				break;
			case 2:
				cin >> y;
				added += y;
				st.add( 0, n, y );
				break;
			case 3:
				cin >> q;
				cout << as[ q - 1 ] + added << endl;
				//cout << st.sum( q - 1, q ) << endl;
				break;
		}
	}

	return 0;
}