AtCoder ABC 328 C - Consecutive (灰色, 300 点)

すごくよく似た過去問がある。これ → ABC 122 C - GeT AC

• 問題へのリンク

問題概要

英小文字からなる長さ の文字列 が与えられる。この文字列に対する次の 個のクエリに答えよ。

各クエリでは、文字列の区間 が与えられる。この区間を取り出した部分文字列において、同じ英小文字が隣接している箇所の個数を答えよ。

制約

• 

考えたこと

累積和を使う。次の記事の「問題 3：AtCoder ABC 122 C - GeT AC」がぴったりで、まったく同じように解ける。

qiita.com

計算量は となる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, Q;
    string S;
    cin >> N >> Q >> S;
    
    // 累積和を準備 - S[i] == S[i+1] であるような i に対して 1 をつけたものの累積和
    vector<int> sum(N, 0);
    for (int i = 0; i+1 < N; ++i) {
        sum[i+1] = sum[i] + (S[i] == S[i+1]);
    }
    
    // クエリ処理
    while (Q--) {
        int l, r;
        cin >> l >> r;
        --l;
        cout << sum[r-1] - sum[l] << endl;
    }
}