Codeforces #186, B : Ilya and Queries

問題文

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

概要

'.' と '#' からなる文字列 s が与えられる。
次のようなクエリ l, r を m 個処理せよ。

• [ l, r ] に含まれる i の内、 を満たすものの個数を答える

解法

そのまま処理すると間に合わないので、適当に前処理をしてクエリを高速に処理できるようにします。

まず文字列を走査して、隣り合う文字が異なる場所は 1 、それ以外は 0 となるような配列を作ります。
こうすると、クエリの答えはこの配列中に於ける [ l, r ) の総和になります。
列の総和に帰着できたので、累積和を用いて [ l, r ) の和を求めることで各クエリを で処理できます。

コード

typedef vector<int> VI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define ALL( c ) (c).begin(), (c).end()

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

	string str;
	cin >> str;

	const int N = str.size();
	VI ary( N - 1 );
	REP( i, 0, N - 1 )
	{
		ary[i] = str[i] == str[ i + 1 ];
	}

	VI csum( 1, 0 );
	partial_sum( ALL( ary ), back_inserter( csum ) );

	int m;
	cin >> m;
	REP( i, 0, m )
	{
		int l, r;
		cin >> l >> r;

		cout << csum[ r - 1 ] - csum[ l - 1 ] << endl;
	}

	return 0;
}