Problem:


Score : 300 points

Problem Statement

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 occurs as a substring?

Notes

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.

Constraints

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

Input

Input is given from Standard Input in the following format:

N Q
S
l_1 r_1
:
l_Q r_Q

Output

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

Sample Input 1

8 3
ACACTACG
3 7
2 3
1 8

Sample Output 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.



Sample input:
8 3
ACACTACG
3 7
2 3
1 8


Sample output:
2
0
3

Submission status: Accepted

Solution code:
N, Q = list(map(int, input().split()))
S = input()

n = [0]
for i in range(1,len(S)):
    n.append(n[-1])
    if S[i-1:i+1]=='AC': n[-1] += 1

for q in range(Q):
    l, r = list(map(int, input().split()))
    print(n[r-1]-n[l-1])

Submission status: Accepted

Solution code:
n , q = list(map(int, input().split()))
s = input()
data = []
for i in range(q):
    data.append(list(map(int, input().split())))
ans = [0 for i in range(n)]
count = 0
for i in range(1,n):
    if s[i - 1] == 'A' and s[i] == 'C':
        count += 1
    ans[i] = count
for i in range(q):
    l = data[i][0]
    r = data[i][1]
    print(ans[r - 1] - ans[l - 1])

Submission status: Accepted

Solution code:
n,q = map(int, input().split())
s = input()
tmp=[0]*n
cnt=0
for i in range(n-1):
  if 'AC' == s[i:i+2]:
    cnt+=1  
  tmp[i+1]=cnt
for i in range(q):
  l,r = map(int,input().split())
  print(tmp[r-1]-tmp[l-1])

Submission status: Accepted

Solution code:
n,q = map(int, input().split())
s = input()
tmp=[0]
l,cnt=0,0
r=2
while r<=n:
  if 'AC' == s[l:r]:
    cnt+=1
    l=r
    tmp.append(cnt)
    tmp.append(cnt)
    r+=2
  else:
    tmp.append(cnt)
    l+=1
    r+=1
for i in range(q):
  l,r = map(int,input().split())
  print(tmp[r-1]-tmp[l-1])

Submission status: Accepted

Solution code:
a, b = map(int, input().split())
c = input()
d = [0] * len(c)
e = 0
for i in range(1, len(c)):
    if c[i] == "C" and c[i-1] == "A":
        e += 1
    d[i] = e
for i in range(b):
    f, g = map(int, input().split())
    print(d[g-1] - d[f-1])

Submission status: Accepted

Solution code:
n, q = (int(i) for i in input().split())  
s = input()
t = [0] * (n+1)

for i in range(n):
  if s[i:i+2] == "AC":
    t[i+1] = t[i] + 1
  else:
    t[i+1] = t[i]
    
for i in range(q):
  l, r = (int(i) for i in input().split())
  print(t[r-1] - t[l-1])

Submission status: Accepted

Solution code:
print("".join([[["{0}\n".format(A[2][B[1]-1]-A[2][B[0]-1]) for B in [list(map(int,input().split())) for i in range(A[0][1])]] for x in [[A[2].append(A[2][i-1]+1) if A[1][0][i-1]=='A' and A[1][0][i]=='C' else A[2].append(A[2][i-1]) for i in range(1,len(A[1][0]))]]] for A in [[[int(x) for x in input().split()],[str(x) for x in input().split()],[0]]]][0][0])[:-1])

Submission status: Accepted

Solution code:
print("".join([ [ [ "{0}\n".format(NQ_S[2][LR[1]-1]-NQ_S[2][LR[0]-1]) for LR in  [list(map(int, input().split())) for i in range(NQ_S[0][1])]] for x in [[NQ_S[2].append(NQ_S[2][i-1]+1) if NQ_S[1][0][i-1]=='A' and NQ_S[1][0][i]=='C' else NQ_S[2].append(NQ_S[2][i-1]) for i in range(1,len(NQ_S[1][0]))]]] for NQ_S in [[[int(x) for x in input().split()],[str(x) for x in input().split()],[0]]] ][0][0])[:-1])

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
s = input()
lr = [list(map(int,input().split())) for _ in range(q)]

ac = [0]*(n+1)

for i in range(1,n+1):
  if s[i-1:i+2-1]=='AC':  
    ac[i]=ac[i-1] + 1
  else:
    ac[i]=ac[i-1]
    
for l,r in lr:
  print(ac[r-1]-ac[l-1])

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = input()
AC = []
ans = []
AC.append(0)
for i in range(1,N):
    if S[i - 1] == "A" and S[i] == "C":
        AC.append(AC[i - 1] + 1)
    else:
        AC.append(AC[i - 1])
for _ in range(Q):
    l, r = map(int, input().split())
    ans.append(AC[r - 1] - AC[l - 1])
print("\n".join(map(str,ans)))

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = input()
lr = [list(map(int, input().split())) for _ in range(Q)]

cnt = [0] * (N + 1)
for i in range(N):
    if S[i:i+2] == 'AC':
        cnt[i+1] = cnt[i] + 1 
    else:
        cnt[i+1] = cnt[i]

for i in range(Q):
    print(cnt[lr[i][1]-1]-cnt[lr[i][0]-1])

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = input()

ac_counts = [0] * N
last = ''
n_count = 0
for idx, current in enumerate(S):
    if last == 'A' and current == 'C':
        n_count += 1
        ac_counts[idx] = n_count
    elif idx != 0:
        ac_counts[idx] = ac_counts[idx - 1]
    last = current

for _ in range(Q):
    l, r = map(int, input().split())
    print(ac_counts[r - 1] - ac_counts[l - 1])

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
s=input()
v=[list(map(int,input().split())) for i in range(q)]
r=[0]*n
count=0
a=0
for i in range(n-1):
    r[i]=a
    if s[i]=='A':
        if s[i+1]=='C':
            a+=1
        else:
            pass
r[n-1]=a
for i in range(q):
    print(r[v[i][1]-1]-r[v[i][0]-1])

Submission status: Accepted

Solution code:
N,Q = map(int,input().split())
S = input()
qlist = [map(int,input().split()) for _ in range(Q)]
tarstr = "AC"
dp = []
maxnum = 0
flg = False
for c in S:
    if(c=="A"):
        flg = True
    elif(c=="C" and flg):
        maxnum += 1
        flg = False
    else:
        flg = False
    dp.append(maxnum)

for l,r in qlist:
    print(dp[r-1]-dp[l-1])

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
s = input()
a = [0] * n
ac = 0

for i in range(1, n):
    if s[i - 1] == 'A' and s[i] == 'C':
        ac += 1
    a[i] = ac

for i in range(q):
    l, r = map(int, input().split())
    print(a[r - 1] - a[l - 1])

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
S = input()
T = [0] * (n - 1)
for i in range(n - 1):
    if S[i : i + 2] == "AC":
        T[i] = 1
for i in range(1, n - 1):
    T[i] += T[i - 1]
T = [0] + T
for _ in range(q):
    l, r = map(int, input().split())
    print(T[r - 1] - T[l - 1])

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
s = input()
l = [0]*q
r = [0]*q

c = [0]
a = 0
for j in range(n) :
  if s[j:j+2] == 'AC' :
    a += 1
  c.append(a)

for i in range(q) :
  l[i], r[i] = map(int,input().split())
  print(c[r[i]-1] - c[l[i]-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys

sys.setrecursionlimit(10**7)

input = sys.stdin.readline


def read_h(typ=int):
    return list(map(typ, input().split()))


def read_v(n, m=1, typ=int):
    return [read_h(typ) if m > 1 else typ(input()) for _ in range(n)]


def main():
    n, q = read_h()
    s, = read_h(typ=str)
    rng = read_v(q, m=2)

    cnts = [0] * (n + 1)
    for i in range(len(s)):
        cnts[i + 1] = cnts[i] + (1 if s[i:i + 2] == 'AC' else 0)

    for l, r in rng:
        print(cnts[r - 1] - cnts[l - 1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def solve(inputs):
    S = inputs[0]
    questions = []
    for i in range(1, len(inputs)):
        questions.append(string_to_int(inputs[i]))

    cumulative_sum = [0]
    for i in range(0, len(S)-1):
        if S[i] == "A" and S[i+1] == "C":
            cumulative_sum.append(cumulative_sum[-1] + 1)
        else:
            cumulative_sum.append(cumulative_sum[-1])

    results = []
    for [start, end] in questions:
        results.append(cumulative_sum[end-1] - cumulative_sum[start-1])

    return results


def string_to_int(string):
    return list(map(lambda x: int(x), string.split()))


if __name__ == "__main__":
    [_, N] = string_to_int(input())
    ret = solve(inputs(N+1))
    for r in ret:
        print(r)
    # print(ret)

Submission status: Accepted

Solution code:
tmp = [int(i) for i in input().split()]
N,Q = tmp[0],tmp[1]
S = [str(i) for i in input().split()][0]

cnt=0
num=[0]
for i in range(len(S)):
  if S[i-1]=='A':
    if S[i]=='C':
      cnt+=1
  num.append(cnt)

for i in range(Q):
  L = [int(i) for i in input().split()]
  print(num[L[1]]-num[L[0]])

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
s = input()
c = [0]
flg = False
cnt = 0
for ss in s:
    if ss == 'C' and flg:
        cnt += 1
    flg = (ss == 'A')
    c.append(cnt)
# print(c)
for _ in range(q):
    l, r = map(int, input().split())
    # [l,r]

    res = c[r] - c[l - 1]
    if l >= 2 and s[l - 2:l] == 'AC':
        res -= 1
    print(res)

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
s=input()
l=[0,0]
cnt=0
for i in range(1,n):
    if "AC" == s[i-1]+s[i]:
        cnt+=1
    l.append(cnt)
for i in range(q):
    a,b=map(int,input().split())
    print(l[b]-l[a])

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
s = str(input())

cum = [0]*n
current = 0

flag = 0

for i in range(1, len(s)):
  if s[i-1] == 'A' and s[i] =='C':
    current += 1
  cum[i] = current

for i in range(q):
  l, r = map(int, input().split())
  print(cum[r-1]-cum[l-1])

Submission status: Accepted

Solution code:
def main():
    N, Q = map(int, input().split())
    S = input()

    t = [0] * (N + 1)
    for i in range(N):
        t[i + 1] = t[i] + (1 if S[i:i + 2] == "AC" else 0)
    for i in range(Q):
        l, r = map(int, input().split())
        print(t[r - 1] - t[l - 1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
s = input()

acs = [0]
pre_a = False
for c in s:
  acs.append(acs[-1])
  if pre_a:
    if c == 'C':
      acs[-1] += 1
    pre_a = False
    if c == 'A':
      pre_a = True
  else:
    if c == 'A':
      pre_a = True

for _ in range(q):
  l, r = map(int, input().split())
  print(acs[r] - acs[l])

Submission status: Accepted

Solution code:
# ABC122 C-GetAC

N, Q = map(int, input().split())
S = input()
lr = []
for _ in range(Q):
    lr.append(list(map(int, input().split())))
    
ArrayAC = [0]*(N)
for j, i in enumerate(S):
    if j == N-1:
        break
    
    if S[j:j+2] == "AC":
        ArrayAC[j+1] = ArrayAC[j] + 1
    else:
        ArrayAC[j+1] = ArrayAC[j]
        
        
for i, j in lr:
    print(ArrayAC[j-1] - ArrayAC[i-1])

Submission status: Accepted

Solution code:
a, b = map(int, input().split())
c = input()
d = [0] * a
e = 0
for i in range(1, a):
    if c[i] == "C" and c[i-1] == "A":
        e += 1
    d[i] = e
for i in range(b):
    f, g = map(int, input().split())
    print(d[g-1]-d[f-1])

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = input()
countlist = [0]
for i in range(1, N):
	if S[i-1] == 'A' and S[i] == 'C':
		countlist.append(countlist[-1]+1)
	else:
		countlist.append(countlist[-1])
for i in range(0, Q):
	L, R = map(lambda v: int(v)-1, input().split())
	ans = countlist[R]
	if L != 0:
		ans -= countlist[L-1]
		if S[L-1] == 'A' and S[L] == 'C':
			ans -= 1
	print(ans)

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = input()
LR = [list(map(int, input().split())) for i in range(Q)]

P = [0] * (N)
before_a = False
cnt = 0
for i in range(N):
  if before_a and S[i] == 'C':
    cnt += 1
    before_a = False
  elif S[i] == 'A':
    before_a = True
  else:
    before_a = False
  P[i] = cnt
for i in range(Q):
  print(P[LR[i][1]-1] - P[LR[i][0]-1])

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
S = input()

flag = False

ATList = [0]*n

for i in range(n):
    if (S[i] == "A"):
        ATList[i] = ATList[i-1]
        flag = True
    elif (S[i] == "C") and flag:
        ATList[i] = ATList[i-1] + 1
        flag = False
    else:
        ATList[i] = ATList[i-1]
        flag = False

for i in range(q):
    l,r = map(int, input().split())
    print(ATList[r-1]-ATList[l-1])

Submission status: Accepted

Solution code:
N,Q = map(int,input().split())
S = input()
T = [0] * N
for i in range(1,N):
    T[i] = T[i-1] + (1 if S[i-1:i+1] == 'AC' else 0)
for i in range(Q):
    l,r = map(int,input().split())
    print(T[r-1]-T[l-1])

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = input()

cnt = [0 for _ in range(N)]

for i in range(1, N):
    if i == 0:
        continue

    cnt[i] = cnt[i - 1]

    if S[i - 1] == 'A' and S[i] == 'C':
        cnt[i] += 1

for _ in range(Q):
    l, r = map(int, input().split())
    print(cnt[r - 1] - cnt[l - 1])

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())

S = input()

t = [0] * (N+1)

for i in range(N):
    t[i+1] = t[i] + (1 if S[i:i+2] == 'AC' else 0)

for i in range(Q):
    l,r = map(int, input().split())
    print(t[r-1] - t[l-1])

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
s=input()
lr=[]
for _ in range(q):
  l,r=map(int,input().split())
  lr.append([l,r])

t=[0]*n
for i in range(n-1):
  if s[i:i+2]=='AC':
    t[i+1]=t[i]+1
  else:
    t[i+1]=t[i]
for i in range(q):
  l=lr[i][0]
  r=lr[i][1]
  print(t[r-1]-t[l-1])

Submission status: Accepted

Solution code:
def main():
    n, q = map(int, input().split())
    s = list(input())
    pos = [[int(i)-1 for i in input().split()] for _ in range(q)]

    s = ['a' if s[i] == 'A' and s[i+1] == 'C' else s[i]
         for i in range(n-1)] + [s[n-1]]
    dp = [0] * n
    for i in range(n-1)[::-1]:
        dp[i] = dp[i+1]
        if s[i] == 'a':
            dp[i] += 1
    for l, r in pos:
        print(dp[l] - dp[r])


main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC122 C

n,q = map(int,input().split())
s = input()
t = [0 for _ in range(n+1)]

for i in range(n):
    t[i+1] = t[i] + (1 if s[i:i+2] =='AC' else 0)

for _ in range(q):
    l,r = map(int,input().split())
    print(t[r-1] - t[l-1])

Submission status: Accepted

Solution code:
def main():

    """ convenient functions
    # for i, a in enumerate(iterable)
    # q, mod = divmod(a, b)
    # divmod(x, y) returns the tuple (x//y, x%y)
    # Higher-order function: reduce(operator.mul, xyz_count, 1)
    # manage median(s) using two heapq https://atcoder.jp/contests/abc127/tasks/abc127_f
    """

    # import numpy as np
    import sys
    sys.setrecursionlimit(10**7)
    from itertools import accumulate, combinations, permutations, product # https://docs.python.org/ja/3/library/itertools.html
    # accumulate() returns iterator! to get list: list(accumulate())
    from math import factorial, ceil, floor
    def factorize(n):
        """return the factors of the Arg and count of each factor
        
        Args:
            n (long): number to be resolved into factors
        
        Returns:
            list of tuples: factorize(220) returns [(2, 2), (5, 1), (11, 1)]
        """
        fct = []  # prime factor
        b, e = 2, 0  # base, exponent
        while b * b <= n:
            while n % b == 0:
                n = n // b
                e = e + 1
            if e > 0:
                fct.append((b, e))
            b, e = b + 1, 0
        if n > 1:
            fct.append((n, 1))
        return fct
    def combinations_count(n, r):
        """Return the number of selecting r pieces of items from n kinds of items.
        
        Args:
            n (long): number
            r (long): number
        
        Raises:
            Exception: not defined when n or r is negative
        
        Returns:
            long: number
        """
        # TODO: How should I do when n - r is negative?
        if n < 0 or r < 0:
            raise Exception('combinations_count(n, r) not defined when n or r is negative')
        if n - r < r: r = n - r
        if r < 0: return 0
        if r == 0: return 1
        if r == 1: return n
        numerator = [n - r + k + 1 for k in range(r)]
        denominator = [k + 1 for k in range(r)]
        for p in range(2,r+1):
            pivot = denominator[p - 1]
            if pivot > 1:
                offset = (n - r) % p
                for k in range(p-1,r,p):
                    numerator[k - offset] /= pivot
                    denominator[k] /= pivot
        result = 1
        for k in range(r):
            if numerator[k] > 1:
                result *= int(numerator[k])
        return result
    def combinations_with_replacement_count(n, r):
        """Return the number of selecting r pieces of items from n kinds of items allowing individual elements to be repeated more than once.
        
        Args:
            n (long): number
            r (long): number
        
        Raises:
            Exception: not defined when n or r is negative
        
        Returns:
            long: number
        """
        if n < 0 or r < 0:
            raise Exception('combinations_with_replacement_count(n, r) not defined when n or r is negative')
        elif n == 0:
            return 1
        else:
            return combinations_count(n + r - 1, r)
    from bisect import bisect_left, bisect_right
    from collections import deque, Counter, defaultdict # https://docs.python.org/ja/3/library/collections.html#collections.deque
    from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest # https://docs.python.org/ja/3/library/heapq.html
    from copy import deepcopy, copy # https://docs.python.org/ja/3/library/copy.html
    import operator
    from operator import itemgetter
    # ex1: List.sort(key=itemgetter(1))
    # ex2: sorted(tuples, key=itemgetter(1,2))
    from functools import reduce
    def chmin(x, y):
        """change minimum
        if x > y, x = y and return (x, True).
        convenient when solving problems of dp[i]
        
        Args:
            x (long): current minimum value
            y (long): potential minimum value
        
        Returns:
            (x, bool): (x, True) when updated, else (x, False)
        """
        if x > y:
            x = y
            return (x, True)
        else:
            return (x, False)
    def chmax(x, y):
        """change maximum
        if x < y, x = y and return (x, True).
        convenient when solving problems of dp[i]
        
        Args:
            x (long): current maximum value
            y (long): potential maximum value
        
        Returns:
            (x, bool): (x, True) when updated, else (x, False)
        """
        if x < y:
            x = y
            return (x, True)
        else:
            return (x, False)

    from fractions import gcd # Deprecated since version 3.5: Use math.gcd() instead.
    def gcds(numbers):
        return reduce(gcd, numbers)
    def lcm(x, y):
        return (x * y) // gcd(x, y)
    def lcms(numbers):
        return reduce(lcm, numbers, 1)

    # first create factorial_list
    # fac_list = mod_factorial_list(n)
    INF = 10 ** 18
    MOD = 10 ** 9 + 7
    modpow = lambda a, n, p = MOD: pow(a, n, p) # Recursive function in python is slow!
    def modinv(a, p = MOD):
        # evaluate reciprocal using Fermat's little theorem:
        # a**(p-1) is identical to 1 (mod p) when a and p is coprime
        return modpow(a, p-2, p)
    def modinv_list(n, p = MOD):
        if n <= 1:
            return [0,1][:n+1]
        else:
            inv_t = [0,1]
            for i in range(2, n+1):
                inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
            return inv_t
    def modfactorial_list(n, p = MOD):
        if n == 0:
            return [1]
        else:
            l = [0] * (n+1)
            tmp = 1
            for i in range(1, n+1):
                tmp = tmp * i % p
                l[i] = tmp
            return l
    def modcomb(n, k, fac_list = [], p = MOD):
        # fac_list = modfactorial_list(100)
        # print(modcomb(100, 5, modfactorial_list(100)))
        from math import factorial
        if n < 0 or k < 0 or n < k: return 0
        if n == 0 or k == 0: return 1
        if len(fac_list) <= n:
            a = factorial(n) % p
            b = factorial(k) % p
            c = factorial(n-k) % p
        else:
            a = fac_list[n]
            b = fac_list[k]
            c = fac_list[n-k]
        return (a * modpow(b, p-2, p) * modpow(c, p-2, p)) % p
    def modadd(a, b, p = MOD):
        return (a + b) % MOD
    def modsub(a, b, p = MOD):
        return (a - b) % p
    def modmul(a, b, p = MOD):
        return ((a % p) * (b % p)) % p
    def moddiv(a, b, p = MOD):
        return modmul(a, modpow(b, p-2, p))

    """ initialize variables and set inputs
    # initialize variables
        # to initialize list, use [0] * n
        # to initialize two dimentional array, use [[0] * N for _ in range(N)]
    # set inputs
        # open(0).read() is a convenient method:
        # ex) n, m, *x = map(int, open(0).read().split())
        #     min(x[::2]) - max(x[1::2])
        # ex2) *x, = map(int, open(0).read().split())
        #     don't forget to add comma after *x if only one variable is used
    # preprocessing
        # transpose = [x for x in zip(*data)]
        # ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] => [(1, 4, 7), (2, 5, 8), (3, 6, 9)]
        # flat = [flatten for inner in data for flatten in inner]
        # ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] => [1, 2, 3, 4, 5, 6, 7, 8, 9]
    # calculate and output
        # output pattern
        # ex1) print(*l) => when l = [2, 5, 6], printed 2 5 6
    """

    # functions used
    r = lambda: sys.stdin.readline().strip()
    r_int = lambda: int(r())
    R = lambda: list(map(int, r().split()))
    Rmap = lambda: map(int, r().split())
    Rfloat = lambda: list(map(float, r().split()))
    Rtuple = lambda: tuple(map(int, r().split()))

    """ how to treat input
    # single int: int(r())
    # single string: r()
    # single float: float(r())
    # line int: R()
    # line string: r().split()
    # line (str, int, int): [j if i == 0 else int(j) for i, j in enumerate(r().split())]
    # lines int: [R() for _ in range(n)]
    """

    if __name__ != '__main__':
        # for test
        sys.stdin = open('sample.txt')

    # ----------------------------------
    # main

    N, Q = R()
    S = r()
    LR = [R() for _ in range(Q)]
    tmp = ""
    A = [0] * N
    for i in range(N):
        if tmp == "A" and S[i] == "C":
            A[i] = 1
        tmp = S[i]
            
    acA = list(accumulate(A))
    for l, r in LR:
        print(acA[r-1] - acA[l-1])
    # end of main
    # ----------------------------------

    """memo: how to use defaultdict of list
    # initialize
    Dic = defaultdict(list)
    # append / extend
    Dic[x].append(y)
    # for
    for k, v in Dic.items():
    """

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,Q=map(int,input().split())
S=input()
listS=list(S)
ans=0
listAC=[ans]
for k in range(1,N):
  if listS[k-1]=="A" and listS[k]=="C":
    ans+=1
  listAC+=[ans]  
for i in range(Q):
  l,r=map(int,input().split())
  ans=listAC[r-1]-listAC[l-1] 
  print(ans)

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
s = input()
l = [list(map(int,input().split())) for i in range(q)]
#print(n,q,s,l)

ac = []
for i in range(n-1):
    if s[i] == "A" and s[i+1] == "C":
        ac.append(i)
#print(ac)
cum = [0]*n
for i in range(1,n):
    if s[i-1] == "A" and s[i] == "C":
        cum[i] = cum[i-1] + 1
    else:
        cum[i] = cum[i-1]
#print(cum)
ans = 0 
for i in range(q):
    left = l[i][0]-1
    right = l[i][1]-1
    ans = cum[right] - cum[left]
    print(ans)

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = input()
l, r = [], []
t = [0] * (N+1)
for i in range(N):
    t[i + 1] = t[i] +(1 if S[i:i+2] == 'AC' else 0)
for i in range(Q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])

Submission status: Accepted

Solution code:
n, q = map(int, raw_input().split())
S = raw_input()
appearance = [0] * n
for i in range(1, n):
    appearance[i] = appearance[i-1]
    if S[i-1] == "A" and S[i] == "C":
        appearance[i] += 1
for _ in range(q):
    l, r = map(int, raw_input().split())
    print appearance[r-1] - appearance[l-1]

Submission status: Accepted

Solution code:
import sys

def input(): return sys.stdin.readline()[:-1]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def MATINT(h): return [list(map(int, input().split())) for _ in range(h)]
def MATSTR(h): return [input() for _ in range(h)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
inf = float('inf')
mod = 10 ** 9 + 7

def main():
    N, Q = MAP()
    S = input() + 'E'
    t = [0] * (N + 1)
    for i in range(N):
        if S[i:i+2] == 'AC':
            t[i + 1] = t[i] + 1
        else:
            t[i + 1] = t[i]
    ans = []
    for i in range(Q):
        l, r = MAP()
        ans.append(t[r - 1] - t[l - 1])
    for i in range(Q):
        print(ans[i])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

def input(): return sys.stdin.readline()[:-1]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def MATINT(h): return [list(map(int, input().split())) for _ in range(h)]
def MATSTR(h): return [input() for _ in range(h)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
inf = float('inf')
mod = 10 ** 9 + 7

def main():
    N, Q = MAP()
    S = input()
    t = [0] * (N + 1)
    for i in range(N - 1):
        if S[i:i+2] == 'AC':
            t[i + 1] = t[i] + 1
        else:
            t[i + 1] = t[i]
    ans = []
    for i in range(Q):
        l, r = MAP()
        ans.append(t[r - 1] - t[l - 1])
    for i in range(Q):
        print(ans[i])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import accumulate
n, q = map(int, input().split())
st = input()
lr = [list(map(int, input().split())) for i in range(q)]

lst = [0]*n
for i in range(n-1):
    if st[i] == "A" and st[i+1] == "C":
        lst[i+1] = 1
ans = list(accumulate(lst))
for i in lr:
    print(ans[i[1]-1]-ans[i[0]-1])

Submission status: Accepted

Solution code:
# ABC122C - GeT AC
import sys
input = sys.stdin.readline


def main():
    n, q = list(map(int, input().rstrip().split()))
    s = input().rstrip()
    arr = tuple(tuple(map(int, input().split())) for _ in range(q))
    cnt = [0] * (n + 1)
    for i in range(n):
        if s[i : i + 2] == "AC":
            cnt[i + 1] = cnt[i] + 1
        else:
            cnt[i + 1] = cnt[i]
    for i, j in arr:
        print(cnt[j - 1] - cnt[i - 1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def resolve():
	n,q=map(int,input().split())
	s=input()
	lr=[list(map(int,input().split())) for i in range(q)]

	t=[0]*(n+1)
	for i in range(n):
		t[i+1]=t[i]+(s[i:i+2]=='AC')
	
	for i in range(q):
		l=lr[i][0]
		r=lr[i][1]

		print(t[r-1]-t[l-1])
resolve()

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
s = input()
lr = [list(map(int, input().split())) for i in range(q)]

ans = [0] * n
for i in range(n - 1):
    if s[i] == "A" and s[i + 1] == "C":
        ans[i + 1] = ans[i] + 1
    else:
        ans[i + 1] = ans[i]

for i in lr:
    print(ans[i[1]-1]-ans[i[0]-1])

Submission status: Accepted

Solution code:
from itertools import accumulate

n, q = map(int, input().split())
s = input()
lr = [list(map(int, input().split())) for i in range(q)]

ans = [0] * n
for i in range(n - 1):
    if s[i] == "A" and s[i + 1] == "C":
        ans[i + 1] = 1
        
ans = list(accumulate(ans))
for i in lr:
    print(ans[i[1]-1]-ans[i[0]-1])

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = input()

t = [0] * (N+2)
t[0] = 1 if S[:2] == 'AC' else 0

for i in range(N-1):
    t[i+1] = t[i] + (1 if S[i:i + 2] == 'AC' else 0)

for _ in range(Q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = list(input())
LR = [list(map(int, input().split())) for _ in range(Q)]

AC = 0
flagA = 0
cumAC = []

for n in range(N):
    if flagA==1 and S[n]=='C':
        flagA = 0
        AC += 1
    elif S[n] == 'A':
        flagA = 1
    else:
        flagA = 0
    cumAC.append(AC)
    
for i in range(Q):
    print(cumAC[LR[i][1]-1] - cumAC[LR[i][0]-1])

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
s = input()
t = [0]*(n+1)

for i in range(n):
	t[i+1] = t[i] + (1 if s[i:i+2]=='AC' else 0)

for i in range(q):
	l, r = map(int, input().split())
	print(t[r-1] - t[l-1])

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
s = input()
t = [0] * (n + 1)

count = 0
for i in range(n - 1):
    if s[i:i+2] == 'AC':
        t[i + 1] = t[i] + 1
    else:
        t[i + 1] = t[i]

for i in range(q):
    l, r = map(int, input().split())
    print(t[r - 1] - t[l - 1])

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = input()
Sum = [0]*(N+1)
for i in range(N-1):
	if S[i] == 'A' and S[i+1] == 'C':
		Sum[i+1] = Sum[i] + 1
	else:
		Sum[i+1] = Sum[i]
Sum[-1] = Sum[-2]

for i in range(Q):
	l, r = map(int, input().split())
	print(Sum[r-1] - Sum[l-1])

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
s = input()
a = [0 for i in range(n)]
for i in range(1, n):
    if s[i] == "C" and s[i - 1] == "A":
        a[i] = a[i - 1] + 1
    else:
        a[i] = a[i - 1]
for i in range([q][0]):
    l, r = map(int, input().split())
    print(a[r - 1] - a[l - 1])

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
s=input()
ac=[0]*(n)
for i in range(len(s)-1):
    if s[i]=="A" and s[i+1]=="C":
        ac[i+1]=ac[i]+1
    else:
        ac[i+1]=ac[i]
#print(ac)
# 01122233
# ACACTACG
for i in range(q):
    l,r=map(int,input().split())
    #print(ac[l:r])
    print(ac[r-1]-ac[l-1])

Submission status: Accepted

Solution code:
# AまででのＡＣの数を0からＮまで保存して、毎回引き算すればいい？
N, Q = map(int, input().split())
S = input()
numofAC = [0] * N
for j in range(1, N):
    numofAC[j] = numofAC[j-1]
    if S[j-1: j + 1] == "AC":
        numofAC[j] += 1
for i in range(Q):
    l, r = map(int, input().split())
    print(numofAC[r-1]-numofAC[l-1])

Submission status: Accepted

Solution code:
N,Q =map(int,input().split())
S = input()

t = [0]
for i in range(N):
    t.append(t[-1]+1 if S[i:i+2] == "AC" else t[-1])
for i in range(Q):
    l,r = map(int,input().split())
    print(t[r-1]-t[l-1])