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 = list(input())
T = [0] * (N+1)
count = 0


for i in range(N-1):
    if S[i] == 'A':
        if S[i+1] == 'C':
            count += 1
    T[i+1] = count
    a = count



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

Submission status: Accepted

Solution code:
NN, QQ = map(int, input().split())
SS = input('')
ll = [0]*(QQ)
rr = [0]*(QQ)
for ii in range(QQ):
    ll[ii], rr[ii] = map(int, input().split())

AC_indices = [0]*(NN)
for jj in range(NN-1):
    if SS[jj] == 'A' and SS[jj+1] == 'C':
        AC_indices[jj] += 1
        
cum_AC = [0]*(NN+1)
cum_AC[0] = AC_indices[0]
for jj in range(NN):
    cum_AC[jj+1] = cum_AC[jj] + AC_indices[jj]

for ii in range(QQ):
    print(cum_AC[rr[ii]-1]-cum_AC[ll[ii]-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] = t[i-1] + (1 if S[i:i+2] == "AC" else 0)
for i in range(Q):
    l,r = map(int, input().split())
    print(t[r-2] - t[l-2])

Submission status: Accepted

Solution code:
# C - GeT AC
# https://abc122.contest.atcoder.jp/tasks/abc122_c

"""
累積和を用いて実装しないと時間が足りない
"""

import sys
n, q = list(map(int, sys.stdin.readline().split()))
s = list(sys.stdin.readline())

cnt = [0] * (len(s)+1)

"""
ACを数えるために受けた文字列ｓを展開して数えていく
"""

for i in range(1, len(s)):
    """
    s = ACACTACG
    cnt = [0,0,1,1,2,2,2,3,3]
    i == 1, 2, 3……len(s)
    
    i == 1
    s[i] == C s[i-1] == A
    ここで代入されるべきなのはcntのindex2番である　
        なぜならば、cntは最初に0を代入するので、s[i]の位置に当たるのはcnt[i]+1であるため
    """

    if s[i] == "C" and s[i-1] == "A":
        cnt[i+1] = cnt[i] + 1
    else:
        cnt[i+1] = cnt[i]


r_and_l = [list(map(int, sys.stdin.readline().split())) for _ in range(q)]

for e in r_and_l:
    num = e[0]
    print(cnt[e[1]] - cnt[num] )

Submission status: Accepted

Solution code:
def main(N, Q, S, lr_list):
    chars = list(S)

    s_list = [0]
    for i in range(N):
        if i+1 < N and chars[i] == 'A' and chars[i+1] == 'C':
            s_list.append(s_list[i] + 1)
        else:
            s_list.append(s_list[i])

    res_list = []
    for lr in lr_list:
        l, r = lr
        l -= 1
        r -= 1
        res_list.append(s_list[r] - s_list[l])

    return res_list


if __name__ == "__main__":
    N, Q = list(map(int, input().split()))
    S = input()
    lr_list = []
    for _ in range(Q):
        lr_list.append(tuple(map(int, input().split())))
    res = main(N, Q, S, lr_list)
    for r in res:
        print(r)

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()
A = [0, 0]
c = 0
for i in range(1,N):
    if S[i-1:i+1] == "AC":
        c += 1
    A.append(c)
for _ in range(Q):
    l, r = map(int, input().split())
    print(A[r]-A[l])

Submission status: Accepted

Solution code:
n,q = map(int, input().split())
s = list(input())
lr_list = [list(map(int,input().split())) for _ in range(q)]
tmp_list = [0]*(n+1)

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

for l,r in lr_list:
    print(tmp_list[r-1]-tmp_list[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())
str = input()
ac_list = [0]
for i in range(1,N):
  if str[i-1:i+1] == "AC":
    ac_list.append(ac_list[-1]+1)
  else:
    ac_list.append(ac_list[-1])
    
for i in range(Q):
  l,r = map(int,input().split())
  print(ac_list[r-1]-ac_list[l-1])

Submission status: Accepted

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

cum_sum = [0] * n
for i in range(1, n):
    cum_sum[i] = cum_sum[i - 1]
    if s[i - 1: i + 1] == "AC":
        cum_sum[i] += 1

for i in range(q):
    print(cum_sum[q_list[i][1] - 1] - cum_sum[q_list[i][0] - 1])

Submission status: Accepted

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

S = input()
d = [0] * N

for i in range(N-1):
    if S[i:i+2] == 'AC':
        d[i+1] += 1
for i in range(1,N):
    d[i] += d[i-1]

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:

N, Q = map(int, input().split())
Str = input()
l_list = [0] * Q
s_list = [0] * Q
for i in range(0, Q):
    l_list[i], s_list[i] = map(int, input().split())

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

for i in range(0, Q):
    print(Mem[s_list[i]-1] - Mem[l_list[i]-1])

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = input()
t = [0]*(N)
for i in range(N-1):
  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 = [ int(it) for it in input().split() ]
S = input()

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

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

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
s = input()
b = [0]
for t in range(1, n):
	if s[t-1] == "A" and s[t] == "C":
		b.append(b[t-1] + 1)
	else:
		b.append(b[t-1])
for u in range(q):
	l, r = map(int, input().split())
	print(b[r-1] - b[l-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_list = [0] * (n+1)
for i in range(n):
    ac_list[i+1] = ac_list[i] + (1 if s[i:i+2] == 'AC' else 0)
# print(ac_list)
for i in range(q):
    print(ac_list[lr[i][1]-1] - ac_list[lr[i][0]-1])

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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()

accum = [0]
cnt = 0
for i in range(1,N):
    if S[i-1:i+1] == "AC":
        cnt += 1
    accum.append(cnt)


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

Submission status: Accepted

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

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

index_list = []
#index_list = [0] * N
start = 0
for i in range(N):
    if S[i-1] == 'A' and S[i] == 'C':
        start += 1
        #index_list[i] = index_list[i-1] + 1
    #else:
    index_list.append(start)
        #index_list[i] = index_list[i-1]

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

Submission status: Accepted

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

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

#index_list = []
index_list = [0] * N
start = 0
for i in range(1,N):
    if S[i-1] == 'A' and S[i] == 'C':
        index_list[i] = index_list[i-1] + 1
    else:
        index_list[i] = index_list[i-1]

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

Submission status: Accepted

Solution code:
import time


def main():

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

    sum = [0] * (N + 100)

    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]

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


if __name__ == '__main__':
    start = time.perf_counter()

    main()

    end = time.perf_counter()
    # print(end - start)

Submission status: Accepted

Solution code:
import time


def main():

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

    sum = [0] * (N + 1)

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

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


if __name__ == '__main__':
    start = time.perf_counter()

    main()

    end = time.perf_counter()
    # print(end - start)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import sys
def input():
	return sys.stdin.readline()

N, Q = map(int, input().split())
S = input()
p = []
for _ in range(Q):
	p.append(tuple([int(_)-1 for _ in input().split()]))

L = [0] * N
l = 0

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

for i in range(Q):
	print(L[p[i][1]-1] - L[p[i][0]-1])

Submission status: Accepted

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


if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
#coding-utf:8

def main():
    n, q = map(int, input().split())
    s = input()
    t = [0] * (n+1)
    for i in range(n):
        if s[i : i+2] == 'AC':
            x = 1
        else:
            x = 0
        t[i+1] = t[i] + x
        x = 0

    for j 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:
#!/usr/bin/env python3


def main():
    n, q = map(int, input().split())
    s = input()
    x = [0] * n
    if s[0:2] == 'AC':
        x[0] = 1
    for i in range(n - 1):
        if s[i+1:i+3] == 'AC':
            x[i+1] = x[i] + 1
        else:
            x[i+1] = x[i]

    for _ in range(q):
        li, ri = map(int, input().split())
        li -= 1
        ri -= 1
        lsum = 0 if li == 0 else x[li-1]
        rsum = x[ri-1]
        print(rsum - lsum)

if __name__ == '__main__':
    main()

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()
LRs = [list(map(int, input().split())) for i in range(Q)]

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

rev_counts = [0]
for i in reversed(range(len(S)-1)):
    rev_counts.append(rev_counts[-1] + counts[i])
rev_counts = list(reversed(rev_counts))
# print(counts)
# print(rev_counts)


for LR in LRs:
    start = LR[0] - 1
    end = LR[1]  -1
    print(rev_counts[start] - rev_counts[end])

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
# print(N, Q)
S = input()
lr_array = [list(map(int, input().split())) for i in range(Q)]
AC_array = []
AC_count = 0

# print(S)
for i, s in enumerate(S):
    if i == 0:
        s_old = s
        continue
    if s_old == "A" and s == "C":
        AC_count += 1
    AC_array.append(AC_count)
    s_old = s

# print(lr_array)
# print(AC_array)
ans = ""
for lr in lr_array:
    print(AC_array[lr[1] - 2] - (AC_array[lr[0] - 2] if lr[0] > 1 else 0))

Submission status: Accepted

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

a = [0]*n
for i in range(1,n):
  a[i] = a[i-1] + (s[i-1:i+1] == "AC")
#print(a)

for _ 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()
L, R = [0] * Q, [0] * Q
for q in range(Q):
    L[q], R[q] = map(int, input().split())

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

for q in range(Q):
    l, r = L[q], R[q]
    print(t[r - 1] - t[l - 1])

Submission status: Accepted

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


accs = [0] * N
begins = [False] * N
for c in range(N):
    if c != 0:
        accs[c] = accs[c-1]
    if c == N-1:
        break
    if S[c] == 'A' and S[c+1] == 'C':
        accs[c] += 1
        begins[c] = True

for lr in LRs:
    l, r = lr
    count = accs[r - 1] - accs[l - 1]
    if begins[l - 1]:
        count += 1
    if begins[r - 1]:
        count -= 1

    print(count)

Submission status: Accepted

Solution code:
from itertools import accumulate

N, Q = map(int, input().split())
S = input()
List = [list(map(int, input().split())) for _ 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)

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

for j in range(Q):
    print(flg_2[List[j][1]-1]-flg_2[List[j][0]-1])

Submission status: Accepted

Solution code:
l, n = [int(x) for x in input().split()]
s = input()
up = [0]
for i in range(l-1):
  if s[i:i+2] == 'AC':
    up.append(up[-1] + 1)
  else:
    up.append(up[-1])
ans = []
for i in range(n):
  d, u = map(int, input().split())
  ans.append(up[u-1] - up[d-1])
for i in range(n):
  print(ans[i])

Submission status: Accepted

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

while index<N:
    acindex=S.find("AC",index)
    if acindex==-1:
        break
    else:
        isAC[acindex+1]=1
        index=acindex+1

cumsum=[0]*(N+1)
for i in range(1,N+1):
    cumsum[i]=cumsum[i-1]+isAC[i-1]

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

Submission status: Accepted

Solution code:
###############################################################################

from bisect import bisect_left as binl

def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * sy) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


###############################################################################


def main():
    n, q = intin()
    s = input()
    lrlist = intinl(q)

    prev = None
    pos_i_list = []
    for i, c in enumerate(s):
        if prev == 'A' and c == 'C':
            pos_i_list.append(i)
        prev = c

    for l, r in lrlist:
        start = binl(pos_i_list, l)
        end = binl(pos_i_list, r)
        print(end - start)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
###############################################################################

from bisect import bisect_left as binl

def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return map(int, input_tuple)


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


###############################################################################


def main():
    n, q = intin()
    s = input()
    lrlist = intinl(q)
    lrlist = [(l, r) for l, r in lrlist]

    prev = None
    pos_i_list = []
    for i, c in enumerate(s):
        if prev == 'A' and c == 'C':
            pos_i_list.append(i)
        prev = c

    for l, r in lrlist:
        start = binl(pos_i_list, l)
        end = binl(pos_i_list, r)
        print(end - start)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, Q = (int(i) for i in input().split())
S = input()
l = []
r = []
for i in range(Q):
    a, b = (int(i) for i in input().split())
    l.append(a)
    r.append(b)

t = [0] * (N+1)
for i in range(N):
    #pre_str = S[l[i]-1:r[i]]
    #print(pre_str.count('AC'))
    t[i+1] = t[i] + (1 if S[i:i+2] == 'AC' else 0)

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

Submission status: Accepted

Solution code:
import bisect

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

# Sの中で、ACという部分文字列が含まれるときの（Aの）index
index = []
for i in range(N-1):
  if S[i]+S[i+1] == "AC":
    index.append(i)

# i番目の文字以降に存在するACという部分文字列の数
sum_index = [0]*N
sum_ac = 0
for i in range(N-1):
  if S[N-(i+2)]+S[N-(i+1)] == "AC":
    sum_ac += 1
  sum_index[N-(i+2)] = sum_ac

for i, q in enumerate(question):
  ans = sum_index[q[0]-1] - sum_index[q[1]-1]
  print(ans)

Submission status: Accepted

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

cs = [0] * N

r = 0
for i in range(1, N):
    if S[i-1:i+1] == "AC":
        r += 1
    cs[i] = r

for l, r in LR:
    result = cs[r - 1] - cs[l -1]
    print(result)

Submission status: Accepted

Solution code:
num = list(map(int,input().split()))
string = input()
s_key=[]
count=[]
for i in range(num[1]):
    s_key.append(list(map(int,input().split())))
for i in range(num[0]):
    if i==0:
        count.append(0)
    else:
        if (string[i-1]=='A' and string [i]=='C'):
            count.append(count[i-1]+1)
        else:
            count.append(count[i-1])
for k in range(num[1]):
    result=count[s_key[k][1]-1]-count[s_key[k][0]-1]
    print(result)

Submission status: Accepted

Solution code:
N, Q = [int(a) for a in input().split(" ")]
S = str(input())
LRs = [[int(s) for s in input().split(" ")] for i in range(Q)]
left = [0]*len(S)
for i in range(1,len(S)):
    left[i] = left[i-1]+1 if S[i-1:i+1]=="AC" else left[i-1]
for l, r in LRs:
    l, r = l-1, r-1
    print(left[r]-left[l])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
# print(N, Q)
S = input()
lr_array = [list(map(int, input().split())) for i in range(Q)]
AC_array = []
AC_count = 0

# print(S)
for i, s in enumerate(S):
    if i == 0:
        s_old = s
        continue
    if s_old == "A" and s == "C":
        AC_count += 1
    AC_array.append(AC_count)
    s_old = s

# print(lr_array)
# print(AC_array)
ans = ""
for lr in lr_array:
    ans += str(AC_array[lr[1] - 2] -
               (AC_array[lr[0] - 2] if lr[0] > 1 else 0)) + "\n"
print(ans[:-1])

Submission status: Accepted

Solution code:
N,Q=(int(i) for i in input().split())
x=input()
a=[]

j=0
s=[0]
t=0
while (j<N-1):
  if (x[j]=="A") and (x[j+1]=="C"):
    t+=1
    s.append(t)
  else:s.append(t)
  j+=1
for i in range(0,Q):
  a.append([int(j) for j in input().split()])
  p=s[a[i][1]-1]-s[a[i][0]-1]
  print(p)

Submission status: Accepted

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

Submission status: Accepted

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

dict_cnt_ac = {}
flag_a = False

cnt_ac = 0
cnt_loop = 0
for s in S:
    cnt_loop += 1
    if flag_a == True and s == "C":
        cnt_ac += 1
        flag_a = False
    elif s == "A":
        flag_a = True
    else:
        flag_a = False
    dict_cnt_ac[cnt_loop] = cnt_ac
    
for q in range(Q):
    l, r = list(map(int, input().split()))
    print(dict_cnt_ac[r] - dict_cnt_ac[l])

Submission status: Accepted

Solution code:
N,Q = map(int,input().split())
S = input()
ACs = [0] * N #i文字目までの"AC"の数
number = 0
for i in range(N-1):
    if S[i] == "A" and S[i+1] == "C":
        number += 1
    ACs[i+1] = number
for j in range(Q):
    l,r = map(int,input().split())
    print(ACs[r-1]-ACs[l-1])

Submission status: Accepted

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

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

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

s = list(S)
ac = [0] * N

for i in range(N-1):
    if s[i] == 'A':
        if s[i+1] == 'C':
            s[i] = "AC"
            ac[i] += 1

ans = list(accumulate(ac))
ans = [0] + ans


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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,Q = map(int,input().split())
S = input()
r = [0 for n in range(N)]
l = [0 for n in range(N)]
cnt = 0
for s in range(N - 1):
	if S[s] == 'A':
		if S[s + 1] == 'C':
			cnt += 1
	l[s + 1] = cnt
cnt = 0
for s in range(1,N):
	if S[-s] == 'C':
		if S[-s - 1] == 'A':
			cnt += 1
	r[-s - 1] = cnt
for q in range(Q):
	L,R = map(int,input().split())
	print(cnt - l[L - 1] - r[R - 1])

Submission status: Accepted

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

a_list = []
for i in range(len(S)):
    if S[i] == "A" and i != len(S) - 1:
        if S[i + 1] == "C":
            S[i]="a"

ti=[0]*N

for i in range(1,N):
    if S[i-1]=="a":
        ti[i]=ti[i-1]+1
    else:
        ti[i]=ti[i-1]

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

Submission status: Accepted

Solution code:
import re
n,q=map(int,input().split())
s=input()
a=[0]*n
b=[0]*n
i=[p.span()[0]for p in re.finditer('(AC){1,1}',s)]
c=0
for m in range(n):
  if c>=len(i):
    if m<n-1:a[m+1]=a[m]
    b[m]=b[m-1]
    continue
  if m==i[c]:
    if m>0:
      if m<n-1:a[m+1]=a[m]+1
      b[m]=b[m-1]+1
    else:
      a[m]=0
      a[m+1]=1
      b[m]+=1
    c+=1
  else:
    a[m+1]=a[m]
    b[m]=b[m-1]
for _ in range(q):
  l,r=map(int,input().split())
  if l>=2:
    print(a[r-1]-b[l-2])
  else:
    print(a[r-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)

for i in range(N):
  t[i + 1] = t[i] + S[i:i + 2].count('AC')

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

Submission status: Accepted

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


def solve(N: int, Q: int, S: str, l: "List[int]", r: "List[int]"):
    cumrative_AC_count = [0]
    count = 0
    for i, s in enumerate(S):
        if i == 0:
            continue
        else:
            if S[i-1]=='A' and S[i]=='C':
                count += 1
        cumrative_AC_count.append(count)
    l = [x-1 for x in l]
    r = [x-1 for x in r]

    for left, right in zip(l, r):
        result = cumrative_AC_count[right]  - cumrative_AC_count[left]
        print(result)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    l = [int()] * (Q)  # type: "List[int]" 
    r = [int()] * (Q)  # type: "List[int]" 
    for i in range(Q):
        l[i] = int(next(tokens))
        r[i] = int(next(tokens))
    solve(N, Q, S, l, r)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, q = [int(i) for i in input().split()]
s = input()
l =[]
r =[]
for i in range(q):
    l1, r1 = [int(i) for i in input().split()]
    l.append(l1)
    r.append(r1)

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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


cnt = [0] * (N)

for i in range(1, N):
	if S[i-1:i+1] == "AC":
		cnt[i] = cnt[i-1] + 1
	else:
		cnt[i] = 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:
import numpy as np

N,Q=list(map(int,input().split()))
S=input()
l=np.zeros(Q)
r=np.zeros(Q)
for i in range(Q):
    l[i],r[i]=list(map(int,input().split()))
l-=1
r-=1
    
acc=np.zeros(N)
count=0
for i in range(1,N):
    if S[i-1]=="A" and S[i]=="C":
        count+=1
    acc[i]=count
    
for i in range(Q):
    print(int(acc[int(r[i])]-acc[int(l[i])]))

Submission status: Accepted

Solution code:
N,Q = map(int,input().split())
S = input()
t = [0]*(N)
for i in range(N-1):
    t[i+1] = t[i]+1 if S[i:i+2] == 'AC' else 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:
# AtCoder Beginner Contest 122
# https://atcoder.jp/contests/abc122
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N, Q = i2nn()
    S = i2s()
    LR = ii2nnn(Q)
    rsw = [0] * (N+1)
    for i in range(N-1):
        rsw[i+1] = rsw[i]
        if S[i] == 'A' and S[i+1] == 'C':
            rsw[i+1] += 1
    rsw[N] = rsw[N-1]
    # 0 1 2 3 4 5
    # 0 1 1 1 2 2
    #  a c c a c
    #  1 2 3 4 5
    for l, r in LR:
        n = rsw[r-1] - rsw[l-1]
        print(n)

main()

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())

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

for i in range(Q):
    print(s[r[i]-1] - s[l[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)]
x=[0]
j=False
t=0
for i in range(n):
    if i==0:
        if s[i]=="A":
            j=True
    elif j==True:
        if s[i]=="C":
            t+=1
            j=False
        if s[i]=="A":
            j=True
        else:
            j=False
    elif s[i]=="A":
        j=True
    x.append(t)
for l,r in lr:
    print(x[r]-x[l])

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
s = input()
ans =[0]
j = 0
for i in range(n-1):#どこにACという連続文字列があるかを調べる
    if s[i] == "A" and s[i+1] == "C":
        j += 1
        ans.append(j)
    else:
        ans.append(j)
# print(ans)
for i in range(q):
    l,r = map(int, input().split())
    print(ans[r-1]-ans[l-1])

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-

def solve():
    N, Q = list(map(int, input().split()))
    S = input()

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


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
_ = input()
S = input().strip()

ps = [0]*(len(S)+1)
for i in range(2, len(S)+1):
  ps[i] = ps[i-1]+int(S[i-2:i] == 'AC')

for line in sys.stdin:
  l,r = map(int, line.strip().split(' '))
  print(ps[r]-ps[l])