Codeforces #197, D : Xenia and Bit Operations

問題文

http://codeforces.com/contest/339/problem/D

概要

要素数が の数列 a が与えられる。
この数列に対し、次の手順により求まる値を v とする。

• 数列の項数が 2 以上の間、次の処理によって得られる数列を新しい a とする
  • 奇数回目の処理のとき、偶数である i について、a[ i ] OR a[ i + 1 ] を a[ i / 2 ] とする。
  • 偶数回目の処理のとき、偶数である i について　a[ i ] XOR a[ i + 1 ] を a[ i / 2 ] とする。
• の値を v とする

整数 n 及び数列 a が与えられたあと、m 個のクエリ ( p, b ) が来る。
クエリの内容は として数列を更新するものである。
各クエリについて、更新後の数列から求まる v を出力せよ。

解法

Segment Tree を使って解きました。
Segment Tree の各接点には、対応する区間に対する計算の（途中）経過を記憶させます。
木の更新では、深さの奇偶によって演算を切り替えるようにすればよいです。

※もっと楽に解けるらしい

コード

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

struct SegmentTree
{
	const int N, depth;
	VI data;

	SegmentTree( int n, const VI &src ) : N( src.size() ), depth( n ), data( N * 4, 0 )
	{
		REP( i, 0, src.size() )
		{
			update( i, src[i] );
		}
		return;
	}

	void update( const int p, const int b )
	{
		return update( p, b, depth, 0, 0, N );
	}

	void update( int p, int b, int d, int k, int l, int r )
	{
		if ( !( l <= p && p < r ) )
		{
			return;
		}

		if ( l + 1 == r )
		{
			if ( p == l )
			{
				data[k] = b;
			}
			return;
		}

		update( p, b, d - 1, chl( k ), l, mid( l, r ) );
		update( p, b, d - 1, chr( k ), mid( l, r ), r );
		if ( d % 2 )
		{
			data[k] = data[ chl( k ) ] | data[ chr( k ) ];
		}
		else
		{
			data[k] = data[ chl( k ) ] ^ data[ chr( k ) ];
		}

		return;
	}
};

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

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

	VI as( 1 << n );
	FOR( a, as )
	{
		cin >> a;
	}

	SegmentTree st( n, as );

	REP( i, 0, m )
	{
		int p, b;
		cin >> p >> b;

		st.update( p - 1, b );
		cout << st.data[0] << endl;
	}	

	return 0;
}