ABC122 C - GeT AC(300点)

問題概要

問題のリンク

$A$, $C$, $G$, $T$ からなる長さ $N$ の文字列 $S$ が与えられます。
文字列$S$に以下の操作を$Q$回行え。

整数 $l_i,r_i (1≤l_i $S$の先頭から $l_i$ 文字目から $r_i$ 文字目までの (両端含む) 部分文字列を考える。この文字列に ACは部分文字列として何回現れるか出力せよ。

制約条件

• $2 \leqq N \leqq 10^5$
• $1 \leqq Q \leqq 10^5$
• $S$は長さ$N$の文字列である。
• $S$の各文字は $A$, $C$, $G$, $T$ のいずれかである。
• $1 \leqq l_i < r_i \leqq N$

考えたこと

文字列$S$から、$S[l-1]$から$S[r-1]$までを切り取り、判定していこうと思ったがこの場合計算量が$0(N^2)$で最大$O(10^{10})$になってしまう。圧倒的TLE。

なので$O(N)$に収めないといけない。

文字列$S$が与えられた時点で、$AC$の数が決まっているため、文字列$S$において、0~N文字目までのACの出現回数の累積和$t[i]$をとっていく。
あとは$t[r]-t[l]$が答えとなる。

解答

c.cs

using System;
using System.Linq;

class Program
{
    static void Main(string[] args) {
        int[] a = Console.ReadLine().Split().Select(int.Parse).ToArray();
        int n = a[0];
        int q = a[1];
        char[] s = Console.ReadLine().ToCharArray();
        for (int i = 0; i < n-1; i ++) {
            if (s[i]=='A' && s[i+1]=='C') s[i] = 'a';
        }
        int[] t = new int[n];
        t[0] = 0;
        for (int i = 0; i < n-1; i ++) {
            if (s[i]=='a') t[i+1] = t[i]+1;
            else t[i+1] = t[i];
        }
        for(int i = 0; i < q; i ++) {
            int[] b = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int l = b[0]-1;
            int r = b[1]-1;
            Console.WriteLine(t[r]-t[l]);
        }
    }
}