WARush

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

Codeforces #186 Div2 B "Ilya and Queries"

問題

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

イリヤは友達全員を試験に受かるよう助けたいと思っている。彼らはIT試験に受かるために下記の課題をクリアする必要がある。

-- 課題 --
あなたは " . "と" # "のみで構成された、文字列s = s1s2... sn(nは文字列の長さ)とm個のクエリを持っている。各クエリは整数のペア li, ri (1 <= li < ri <= n )である。クエリ li, riに対する返答はsi = si+1 である i (li <= i < ri )の数である。
----------
ライオンであるイリヤは友達を助けたいが、イリヤを助けてくれる者は誰かいるだろうか?課題を解いて欲しい。

制約

2 <= n <= 10^5
1 <= m <= 10^5


考えた事

まあBIT使えば解けそうだが・・・なんか大げさなような・・・
あ!BITの考えと同じだけど、クエリ( li, ri ) = クエリ( 1, ri ) - クエリ( 1, li )だから、クエリ( 1, x )を一通り出しておけば一発や!


ソースコード

int sum[100050];

int main() {
    string line;
    cin >> line;
    int n = line.length();

    // クエリ( 1, x )を一通り出す
    sum[0] = sum[1] = 0;
    for( int i = 2; i <= n; i++ ){
        char cu = line[i - 2];
        char ne = line[i - 1];
        sum[i] = cu == ne ? 1 : 0;
    }
    for( int i = 3; i <= n; i++ ){
        sum[i] += sum[i-1];
    }

    // クエリに応答する
    int m;
    cin >> m;
    for( int i = 0; i < m; i++ ){
        int l, r;
        cin >> l >> r;
        int s = sum[r] - sum[l];
        cout << s << endl;
    }
}