Edited at

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]);
}
}
}