AtCoder题解｜ABC 122C GeT AC

题目信息 📚

【题目描述】

You are given a string $S$ of length $N$ consisting of A, C, G, and T. Answer the following $Q$ queries:

Query $i$ $(1 \leq i \leq Q)$: You will be given integers $l_i$ and $r_i$ $(1 \leq l_i < r_i \leq N)$. Consider the substring of $S$ starting at index $l_i$ and ending at index $r_i$ (both inclusive). In this string, how many times does AC occur as a substring?

A substring of a string $T$ is a string obtained by removing zero or more characters from the beginning and the end of $T$.

For example, the substrings of ATCODER include TCO, AT, CODER, ATCODER, and the empty string, but not AC.

【输入】

Input is given from Standard Input in the following format:

$N$ $Q$

$S$

$l_1$ $r_1$

$\vdots$

$l_Q$ $r_Q$

【输出】

Print $Q$ lines. The $i$-th line should contain the answer to the $i$-th query.

【数据范围】

$2 \leq N \leq 10^5$
$1 \leq Q \leq 10^5$
$S$ is a string of length $N$.
Each character in $S$ is A, C, G, or T.
$1 \leq l_i < r_i \leq N$

【输入样例1】

8 3
ACACTACG
3 7
2 3
1 8

【输出样例1】

2
0
3

Query 1: The substring of $S$ starting at index 3 and ending at index 7 is ACTAC. In this string, AC occurs twice as a substring.
Query 2: The substring of $S$ starting at index 2 and ending at index 3 is CA. In this string, AC occurs zero times as a substring.
Query 3: The substring of $S$ starting at index 1 and ending at index 8 is ACACTACG. In this string, AC occurs three times as a substring.

【输入样例2】

14 2
11101010110011

【输出样例2】

【输入样例3】

1 1
1

【输出样例3】

【题目来源】

https://atcoder.jp/contests/abc122/tasks/abc122_c

题目解析 🍉

【题目分析】

采用类似于前缀和的思想进行预处理，使得之后能够在 $O(1)$ 的时间内查询。

【C++代码】

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n, q, l, r, cnt, pre[N];
string s;

int main() {
    cin >> n >> q >> s;

    // 预处理
    // pre[i]表示s[0]~s[i-1]有多少个"AC"出现
    pre[1] = 0;
    for (int i = 1; i < s.size(); i++) {
        if (s[i - 1] == 'A' && s[i] == 'C')
            cnt++;
        pre[i + 1] = cnt;
    }

    // O(1)查询，输出答案
    for (int i = 1; i <= q; i++) {
        cin >> l >> r;
        cout << pre[r] - pre[l] << endl;
    }
    return 0;
}