313-B, *1100

Problem - 313B - Codeforces

문제

• 문자열 $s = s_{1}s_{2}\cdot \cdot \cdot s_{n},\ (2 \leq n \leq 10^{5})$에 대해
• $s_{i}=s_{i+1}$인 $i \in [l,\ r)$의 개수를 $m(1 \leq m \leq 10^{5})$번 출력
• $O(nlog\ n)$ 알고리즘은 통과할 수 있다

 

$O(n)$

prefix sum 을 이용한다

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
 
string s;
int prefix_sum[100001] {};
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    getline(cin, s);
    for(int i = 1; i <= s.length(); i++) prefix_sum[i] = prefix_sum[i-1] + (int)(s[i-1] == s[i]);
 
    int m;
    cin >> m;
    int l, r;
    while(m--){
        cin >> l >> r;
        cout << prefix_sum[r-1] - prefix_sum[l-1] << endl;
    }
 
    return 0;
}cs