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=map(int,input().split())
s=input()
ans=[0]*n
cnt=0
for i in range(len(s)-1):
    if s[i:i+2]=='AC': cnt+=1
    ans[i]=cnt
for _ in range(q):
    l,r=map(int,input().split())
    print(ans[r-2]-ans[l-2])

Submission status: Accepted

Solution code:
n,q = map(int, input().split())
s = input()
li = [0]*(n+1)
for i in range(n):
    if s[i:i+2] == "AC":
        li[i+1] = li[i] + 1
    else:
        li[i+1] = li[i]

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

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
s = input()
count = [0]*n
for i in range(1,n):
    count[i] += count[i-1]
    if s[i-1:i+1] == "AC":count[i] += 1
for i in range(q):
    l,r = map(int,input().split())
    print(count[r-1]-count[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]=="A" and S[i+1]=="C":
        t[i+1] = t[i] + 1
        i += 2
    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()
cs = [0] * N
for i in range(1, N):
  if S[i - 1:i + 1] == 'AC':
    cs[i] = 1
for i in range(1, N):
  cs[i] += cs[i - 1]
for _ in range(Q):
  l, r = map(int, input().split())
  t = cs[r - 1]
  if l != 1:
    t -= cs[l - 2]
    if S[l - 2:l] == 'AC':
      t -= 1
  print(t)

Submission status: Accepted

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

Submission status: Accepted

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

for index,value in enumerate(s):
    if index != 0:
        if s[index-1]+s[index] == 'AC':
            ruiseki[index] = ruiseki[index-1] + 1
        else:
            ruiseki[index] = ruiseki[index-1]

for _ in range(q):
    question = list(map(int,input().split()))
    print(ruiseki[question[1]-1] -ruiseki[question[0]-1] )

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
input = sys.stdin.readline

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

count = [0]
for i in range(0,n-1):
    if s[i] == 'A' and s[i+1] == "C":
        count.append(1)
    else:
        count.append(0)
count.append(0)

flag = list(accumulate(count))

for slr in lr:
    l = slr[0]
    r = slr[1]
    print(flag[r-1] - flag[l-1])

Submission status: Accepted

Solution code:
N, Q =map(int,input().split())
S =input()
LR = [list(map(int,input().split())) for i in range(Q)]
ACnum =[0]*(N+1)
Sofar = 0
for i in range(N-1):
    if S[i]=="A" and S[i+1]=="C":
        Sofar+=1
    ACnum[i+1] = Sofar
ACnum[N]=Sofar
#print(ACnum)
for i in range(Q):
    print(ACnum[LR[i][1]-1]-ACnum[LR[i][0]-1])

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
some=input()
lists=[]
for _ in range(q):
    add=list(map(int,input().split()))
    lists.append(add)

emptylists=[0]

for _ in range(n-1):
    numbers=emptylists[-1]
    if some[_ : _+2]=="AC":
        numbers=1+emptylists[-1]        
        emptylists.append(numbers)
    else:
        emptylists.append(numbers)

for j in range(q):
    print(emptylists[lists[j][1]-1]-emptylists[lists[j][0]-1])

Submission status: Accepted

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

li=[]
for i in range(n-1):
    if s[i]+s[i+1]=='AC':
        li+=[i]
ans=0
for l,r in lr:
    left=bisect.bisect_left(li,l-1)
    right=bisect.bisect_right(li,r-2)
    print(right-left)

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
raw = input()
acu = [0]
for i in range(1,n):
  if raw[i-1:i+1] == 'AC':
    acu.append(acu[-1]+1)
  else:
    acu.append(acu[-1])
acu.append(0)
for _ in range(q):
  l,r = map(int,input().split())
  l -= 1
  r -= 1
  print(acu[r] - acu[l])

Submission status: Accepted

Solution code:
n, q = map(int, 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 = map(int, input().split())
    print(t[r - 1] - t[l - 1])

Submission status: Accepted

Solution code:
def slove():
    import sys
    input = sys.stdin.readline
    n, q = list(map(int, input().rstrip('\n').split()))
    s = str(input().rstrip('\n'))
    lr = [list(map(int, input().rstrip('\n').split())) for _ in range(q)]
    l = [0] * n
    cnt = 0
    for i in range(1, n):
        if s[i] == "C" and s[i-1] == "A":
            cnt += 1
        l[i] = cnt
    for ln, rn in lr:
        print(l[rn-1] - l[ln-1])


if __name__ == '__main__':
    slove()

Submission status: Accepted

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

count_list = [0]*N
count = 0
s_1 = S[0]
s_2 = ''
for i in range(1, N):
    s_2 = S[i]
    if s_1 == 'A' and s_2 == 'C':
        count += 1
    count_list[i] = count
    s_1 = s_2
# print(count_list)

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

Submission status: Accepted

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

ss = [0] * (n+1)

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

sss = [0] * (n+1)
cnt = 0
for i in range(n+1):
    cnt += ss[i]
    sss[i] = cnt


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

Submission status: Accepted

Solution code:
def test():
    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__":
    test()

Submission status: Accepted

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

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

Submission status: Accepted

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

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

    for l, r in lr:
        print((ruiseki[r] - ruiseki[l]))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from bisect import bisect, bisect_left

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

bi = []

for i in range(n - 1):
    if s[i:i+2] == "AC":
        bi.append(i)

for _ in range(q):
    l, r = map(int, input().split())
    answer = bisect(bi, r - 1) - bisect_left(bi, l - 1)
    if r < n and s[r - 1:r + 1] == "AC":
        answer -= 1
    print(answer)

Submission status: Accepted

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

Submission status: Accepted

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

L = [0 for _ in range(N)]
R = [0 for _ in range(N)]

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

for i in range(Q):
    Li = LR[i][0]
    Ri = LR[i][1]

    print(L[Ri] - L[Li])

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = input()
S_list = list(S)
count_list = [0]*N

for i in range(1, N):
    count_list[i] += count_list[i-1] 
    if S_list[i-1] == "A" and S_list[i] == "C":
        count_list[i] += 1

for i in range(Q):
    start, end = map(int, input().split())
    count = count_list[end-1] - count_list[start-1]
    print(count)

Submission status: Accepted

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

ac_count=[]
ac=0

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################


N, Q = map(int, input().split())
S = input().rstrip()

# Sの累積和
rui = [0] * N
for i in range(1, N):
    rui[i] = rui[i-1]
    if S[i-1] == 'A' and S[i] == 'C':
        rui[i] = rui[i-1] + 1

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

    print( rui[r] -rui[l] )

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
S=input()
L=[0]
c=0
for i in range(n-1):
    if S[i:i+2]=='AC':
        c+=1    
    L.append(c)
for j in range(q):
    s,e=map(int,input().split())
    print(L[e-1]-L[s-1])

Submission status: Accepted

Solution code:
N,Q=map(int,input().split())
S=[i for i in input()]
t=[0]*(N+1)
for i in range(N-1):
  t[i+1]=t[i]+(1 if S[i]=='A' and S[i+1]=='C' 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:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

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

score = [0]*n
for i in range(n-1):
    score[i+1] = score[i]
    if s[i]+s[i+1] == 'AC':
        score[i+1] += 1

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

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
s=input()
hantei=[0]
for i in range(1,len(s)):
  if s[i-1]=="A" and s[i]=="C":
    hantei.append(hantei[i-1]+1)
  else:
    hantei.append(hantei[i-1])
#print(hantei)
#ここまではあってる

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,q= map(int,input().split())
s = input()
lr = [list(map(int, input().split())) for i in range(q)]
import numpy as np
sn = list(np.cumsum([0] + [s[i:i++2]=="AC" for i in range(n-1)]))

for i,j in lr:
  i -= 1
  j -= 1
  print(sn[j] - sn[i])

Submission status: Accepted

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

Submission status: Accepted

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

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

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

for temp in lr:
    l, r = temp
    print(t[r-1] - t[l-1])

Submission status: Accepted

Solution code:
N,Q = map(int,input().split())
S = list(input())
S.insert(0,0)
C = [0 for _ in range(N+1)]
cnt = 0
for i in range(2,N+1):
    if S[i-1]=="A" and S[i]=="C":
        cnt += 1
        C[i] = cnt
    else:
        C[i] = cnt
for _ in range(Q):
    l,r = map(int,input().split())
    print(C[r]-C[l])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,Q=map(int,input().split())
S=input()
l=[0]*Q
r=[0]*Q
for i in range(Q):
  l[i],r[i]=map(int,input().split())

Sac=[0]*N
num=0
for i in range(1,N):
  if S[i]=="C" and S[i-1]=="A":
    num+=1
  Sac[i]=num
#print(Sac)

for i in range(Q):
  print(Sac[r[i]-1]-Sac[l[i]-1])

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = input()
l = [0]*Q
r = [0]*Q

sum_arr = [0, 0]

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

for i in range(N-1):
    if S[i:i+2] == "AC":
        sum_arr.append(sum_arr[-1] + 1)
    else:
        sum_arr.append(sum_arr[-1])
for i in range(Q):
    print(sum_arr[r[i]] - sum_arr[l[i]])

Submission status: Accepted

Solution code:
import numpy as np
def find_AC(S):
  ret = [0]*len(S)
  for i in range(len(S)-1):
    if S[i] == 'A' and S[i+1] == 'C':
      ret[i+1] = 1
  return ret

N, Q = [int(x) for x in input().split()]
S = input()

cum = np.cumsum(find_AC(S))

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

Submission status: Accepted

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

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

acc = [0] * n
for i in range(n-1):
  acc[i+1] = acc[i] + ac[i]

lr = [tuple(map(int,input().split())) for _ in range(q)]
for i in range(q):
  l = lr[i][0] - 1
  r = lr[i][1] - 1
  print(acc[r] - acc[l])

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 for _ in range(N)]

for i in range(N-1):
    if S[i] == 'A' and S[i+1] == 'C':
        ac[i] = 1
#print(ac)

acsum = [0 for _ in range(N+1)]
for i in range(N):
    acsum[i+1] = acsum[i] + ac[i]
#print(acsum)

for i in range(Q):
    left = lr[i][0] - 1
    right = lr[i][1] - 1
    tmp = acsum[right] - acsum[left]
    print(tmp)

Submission status: Accepted

Solution code:
N,Q=map(int,input().split())
S=input()
t=[0]*N
for i in range(0,N-1):
  t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(0,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()
S_nums = [0 for _ in range(N+2)]
for idx in range(N):
  if S[idx-1:idx+1] == 'AC': S_nums[idx+1] = S_nums[idx] + 1
  else: S_nums[idx+1] = S_nums[idx]

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

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = input()
t = [0] * (N+1)
ans = []

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())
    ans.append(t[r-1] - t[l-1])
    
for i in range(Q):
    print(ans[i])

Submission status: Accepted

Solution code:
from sys import stdin
from itertools import accumulate


def fin(f):
    """
    INput with Function
    f(input())と同じ。書きやすさのために作成した。
    :param f: 入力に対して呼び出す関数
    :return: 関数の処理結果
    """
    return f(stdin.readline().rstrip())


def gin(f, nl=1):
    """
    INput with function and Generator
    空白区切りの入力の各値に対して関数fを用いて初期化を行う。
    複数行にも対応。
    使い方:
      一行の入力例 -> next(gin(int))
      複数行の入力をリストに格納する例 -> list(gin(int, n))
      forループで使う例 -> for l, r in gin(int, n):
    :param f: 各値に適応する関数
    :param nl: 行数(デフォルトは1)
    :returns: 空白区切りのリストたち
    """
    for _ in range(nl):
        yield list(map(f, stdin.readline().split()))


n, q = next(gin(int))

s = input()


def count(total, i):
    return total + 1 if s[i-1:i+1] == 'AC' else total


cumsum = list(accumulate([0] + list(range(n)), count))[1:]

for l, r in gin(int, q):
    print(cumsum[r-1] - cumsum[l-1])

Submission status: Accepted

Solution code:
import math

def makelist(n, m):
    return [[0 for i in range(m)] for j in range(n)]


N, Q = map(int, input().split())
S = "0" + input() + "0"

memo = [0]*(N+1)
flags = [False]*(N+1)
for i in range(1, N+1):
    if S[i] == "A" and S[i+1] == "C":
        memo[i+1] = 1
        flags[i+1] = True
for i in range(2, N+1):
    memo[i] += memo[i-1]

for _ in range(Q):
    l, r = map(int, input().split())
    ans = math.floor(memo[r] - memo[l-1])
    if flags[l]:
        ans -= 1
    print(ans)

Submission status: Accepted

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

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

res = []
for lr in LR:
    l, r = lr
    res.append(acc[r - 1] - acc[l - 1])

print(*res, sep='\n')

Submission status: Accepted

Solution code:
import bisect
n,q=map(int,input().split())
s=input()
data=[]
for i in range(n-1):
    if s[i]=='A' and s[i+1]=='C':
        data.append(i)
query = [tuple(map(int,input().split())) for i in range(q)]
for qe in query:
    l=bisect.bisect_left(data,qe[0]-1)
    r=bisect.bisect_right(data,qe[1]-2)
    print(r-l)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,q = (int(x) for x in input().split())
s = input()
l = []
r = []
for i in range(q):
    temp1,temp2 = (int(x) for x in input().split())
    l.append(temp1-1)
    r.append(temp2-1)

bb = []
bb.append(0)
# print(l)
for i in range(1,n):
    if s[i-1] == 'A' and s[i] == 'C':
        bb.append(bb[i-1] + 1)
    else:
        bb.append(bb[i-1])

for i in range(q):
    print(bb[r[i]] - bb[l[i]])

Submission status: Accepted

Solution code:
N,Q = map(int,input().split())
S = list(input())
l=[]
r=[]
for i in range(Q):
    L,R = map(int,input().split())
    l.append(L)
    r.append(R)

#累積和
count = [0]*(N+1)
for i in range(N):
    if i+1 < N and S[i] == 'A' and S[i+1] == 'C':
        count[i+1] = count[i] + 1
    else:
        count[i+1] = count[i]

#クエリ
for i in range(Q):
    print(count[r[i]-1] - count[l[i]-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
dp = [0 for _ in range(n+1)]
S = input()
a = [0 for _ in range(m)]
for i in range(1,n):
    if S[i-1:i+1] == "AC":
        dp[i] = dp[i-1]+1
    else:dp[i] = dp[i-1]
for i in range(m):
    x, y = map(int,input().split())
    a[i] = dp[y-1] - dp[x-1]
print(*a,sep="\n")

Submission status: Accepted

Solution code:
#import pysnooper
#import os,re,sys,operator,math,heapq,string
from collections import Counter,deque
#from operator import itemgetter
#from itertools import accumulate,combinations,groupby,combinations_with_replacement
from sys import stdin,setrecursionlimit
#from copy import deepcopy

setrecursionlimit(10**6)
input=stdin.readline

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

Submission status: Accepted

Solution code:
from itertools import accumulate

n, q = map(int, input().split())

s = input()

problems = [list(map(int, input().split())) for _ in range(q)]


def count(total, i):
    return total + 1 if s[i-1:i+1] == 'AC' else total


cumsum = list(accumulate(range(n), count))

for l, r in problems:
    print(cumsum[r-1] - cumsum[l-1])

Submission status: Accepted

Solution code:
from itertools import accumulate

n, q = map(int, input().split())

s = input()

problems = [list(map(int, input().split())) for _ in range(q)]


def count(total, i):
    return total + 1 if s[i-1:i+1] == 'AC' else total


cumsum = list(accumulate([0] + list(range(1, n)), count))

for l, r in problems:
    print(cumsum[r-1] - cumsum[l-1])

Submission status: Accepted

Solution code:
from itertools import accumulate

n, q = map(int, input().split())

s = input()

problems = [list(map(int, input().split())) for _ in range(q)]


def count(total, i):
    return total + 1 if s[i:i+2] == 'AC' else total


cumsum = list(accumulate([0] + list(range(n)), count))

for l, r in problems:
    print(cumsum[r-1] - cumsum[l-1])

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    N, Q= map(int, input().split())
    S = str(input())
    L = [list(map(int, input().split())) for _ in range(Q)]
    
    nums = [0]*(N-1)
    
    for i in range(N-1):
        if S[i] == 'A' and S[i+1] == 'C':
            nums[i] += 1

    for i in range(1, len(nums)):
        nums[i] = nums[i] + nums[i-1]
    
    nums = [0] + nums
    
    for l, r in L:
        print(nums[r-1] - nums[l-1])

Submission status: Accepted

Solution code:
N,Q = map(int, input().split())
S = input()
acCount = [0]*len(S)

count = 0
for i in range(len(S)-1):
  if S[i]=='A' and S[i+1]=='C':
    count += 1
  acCount[i+1] = count

  
for i in range(Q):
  L,R = map(int, input().split())
  print(acCount[R-1]-acCount[L-1])

Submission status: Accepted

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

c = [0]
cum = 0
for i in range(1, len(s)):
  if s[i-1:i+1] == 'AC':
    cum += 1
    c.append(cum)
  else:
    c.append(cum)

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

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = input()
AC = [0] * N

for i in range(1, len(S)):
    if S[i-1] == 'A' and S[i] == 'C':
        AC[i] = AC[i-1] + 1
    else:
        AC[i] = AC[i-1]


for i in range(Q):
    start, end = map(lambda x:int(x)-1, input().split())
    print(AC[end] - AC[start])

Submission status: Accepted

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

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

Submission status: Accepted

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

lr = []
for i in range(Q):
    _ = list(map(int,input().split()))
    lr.append(_)

AC = [0]
counter = 0

for j in range(1,N):
    if S[j-1] == 'A' and S[j] == 'C':
        counter += 1
    AC.append(counter)

for j in range(Q):
    right = lr[j][1]-1
    left = lr[j][0]-1
    print(AC[right]-AC[left])

Submission status: Accepted

Solution code:
import numpy as np

N, Q = map(int, input().split())
S = np.array(list('_' + input()), dtype='U')

A = (S == 'A')
C = (S == 'C')
AC = A[:-1] & C[1:]
AC_cum = AC.cumsum()

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

Submission status: Accepted

Solution code:
import sys

input=sys.stdin.readline

N,Q=map(int,input().split())
S=input()
A=[]
B=[]
l=[0]

for _ in range(Q):
    a,b=map(int,input().split())
    A.append(a)
    B.append(b)

count=0
for i in range(1,N):
    if S[i-1]=="A" and S[i]=="C":
        count+=1
    l.append(count)

for i in range(Q):
    print(l[B[i]-1]-l[A[i]-1])

Submission status: Accepted

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

lr = [list(map(int,input().split())) for _ in range(Q)]

#print(N,Q,S)
#print(lr)

#print(S[0:5])

CC=[0]
for _ in range(1,N):
    if (S[_-1:_+1] == 'AC'):
        CC.append(CC[_-1]+1)
    else:
        CC.append(CC[_-1])

    #CC.append(S[0:_].count('AC'))

#print(CC)

for _ in range(Q):
    l = lr[_][0]
    r = lr[_][1]

    print(CC[r-1]-CC[l-1])

#for _ in range(Q):
#    l = lr[_][0]
#    r = lr[_][1]
    #print(_,S[0:r],S[0:(l-1)])
    #print(S[0:r].count('AC')-S[0:l].count('AC'))
    #print(_,S[l-1:r])
#    print(S[l-1:r].count('AC'))

Submission status: Accepted

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

l = []
r = []
for i in range(q):
    li, ri = map(int, input().split())
    l.append(li)
    r.append(ri)

acs = [0]
count = 0
idx = 1
while True:
    if idx == n:
        break
    if s[idx-1] == 'A' and s[idx] == 'C':
        count += 1
    acs.append(count)
    idx += 1

for i in range(q):
    print(acs[r[i]-1] - acs[l[i]-1])

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
s = input()
a = [0]*2
for i in range(2,n+1):
    a += [a[i-1]+s[i-2:i].count('AC')]
ans = []
for _ in range(q):
    l,r = map(int,input().split())
    ans.append(a[r]-a[l])
print(*ans, sep='\n')

Submission status: Accepted

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


lis = [0]*(l+1)
for i in range(1,l+1):
  lis[i] = lis[i-1]+(1 if s[i-1]=="a" else 0)


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

Submission status: Accepted

Solution code:
from itertools import accumulate


N,Q = list(map(int,input().split()))
S = input()
A = [list(map(int,input().split())) for i in range(Q)]

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

flg2 = [0] + flg
flg2 = list(accumulate(flg2))

for a in A:
    print(flg2[a[1]-1] - flg2[a[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)]

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

print(*ans, sep='\n')

Submission status: Accepted

Solution code:
NQ = input().split()
N = int(NQ[0])
Q = int(NQ[1])

S = input()


t = [0]

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

Submission status: Accepted

Solution code:
import bisect

n, q = map(int, input().split())
s = input().strip()
lrs = [list(map(int, input().split())) for _ in range(q)]

indices = []
for i, (c0, c1) in enumerate(zip(s, s[1:])):
    if c0 == 'A' and c1 == 'C':
        indices.append(i)

indices_c = [i + 1 for i in indices]
for (l, r) in lrs:
    li = bisect.bisect_left(indices, l - 1)
    ri = bisect.bisect_left(indices_c, r)
    print(ri - li)

Submission status: Accepted

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

Submission status: Accepted

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

AC_li = [0]
cnt = 0

for i in range(N-1):
    if S[i] + S[i+1] == "AC":
        cnt += 1
    AC_li.append(cnt)
    
for r,l in li:
    print(AC_li[l-1]-AC_li[r-1])

Submission status: Accepted

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

acc = [0] * N
for i in range(1, N):
    if S[i] == "C" and S[i-1] == "A":
        acc[i] += 1
from itertools import accumulate
acc = list(accumulate(acc))

for l, r in items:
    print(acc[r-1]-acc[l-1])

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate
import sys
import re


def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007


def main():
    n, q = LI()
    li = [0] * n
    s = S()
    for i in re.finditer('AC', s):
        li[i.end()-1] += 1

    li = list(accumulate(li))


    for l, r in LIR(q):
        print(li[r-1] - li[l-1])




main()

Submission status: Accepted

Solution code:
import numpy as np

N, Q = map(int, input().split())
S = np.array(list('_' + input()), dtype='U2')

A = (S == 'A')
C = (S == 'C')
AC = (A[:-1] & C[1:])
AC_cum = AC.cumsum()

for _ in range(Q):
    l, r = map(int, input().split())
    print(AC_cum[r-1] - AC_cum[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:
def slove():
    import sys
    input = sys.stdin.readline
    n, q = list(map(int, input().rstrip('\n').split()))
    s = str(input().rstrip('\n'))
    sc = [0] * n
    cnt = 0
    for i in range(1, n):
        if s[i] == "C" and s[i-1] == "A":
            cnt += 1
        sc[i] = cnt
    for i in range(q):
        l, r = list(map(int, input().rstrip('\n').split()))
        print(sc[r-1] - sc[l-1])


if __name__ == '__main__':
    slove()