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:
import numpy as np

N, Q = map(int, input().split())
S = input()
t = np.zeros(N+1)
for i in range(N):
    t[i+1] = t[i]+(1 if S[i-1:i+1]=='AC' else 0)

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

Submission status: Accepted

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

for i in range(1,N):
  v = 1 if S[i-1]+S[i] == 'AC' else 0
  k[i] = k[i-1] + v
k[-1]=k[-2]
for _ in range(Q):
  f,l = map(int,input().split())
  print(k[l-1] - k[f-1])

Submission status: Accepted

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

t=[0]

for i in range(1,N):
  if (S[i-1]=='A')&(S[i]=='C'):
    t.append(t[i-1]+1)
  else:
    t.append(t[i-1])

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

Submission status: Accepted

Solution code:
# coding: utf-8

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

num = [0] * (N+1)

for i in range(N):
    #if S[i]=='A' and S[i+1]=='C':
    if S[i:i+2] =='AC':
        num[i + 1] = num[i] + 1
    else:
        num[i + 1] = num[i]

        

for i in range(Q):
    l, r = map(int, input().split())
    print( num[r-1] - num[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 = list(input())
S.append(0)
par = [0]*(N+1)#par[0]は無視
Ans = []
for i in range(N):
        par [i+1]=par[i]+(1 if (S[i]=='A') & (S[i+1]=='C') else 0)
for i in range(Q):
        x,y = map(int,input().split())
        print(par[y-1]-par[x-1])

Submission status: Accepted

Solution code:
def get_answer(a, start, end):
    return a[end] - a[start]

def create_answer_array(s):
    result = []
    result.append(0)

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

    return result

n, q = map(int, input().split())
s = str(input())
questions = []
for _ in range(q):
    a, b = map(int, input().split())
    questions.append((a - 1, b - 1))

a = create_answer_array(s)

for question in questions:
    print(get_answer(a, question[0], question[1]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#encoding: 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 = list(map(int, input().split()))

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

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
s = input()
x = [list(map(int,input().split())) for i in range(q)]
cnt = 0
res = [0]
for i in range(1,len(s)):
    if s[i-1]=="A" and s[i]=="C":
        cnt += 1
    res.append(cnt)
for j in range(q):
    print(res[x[j][1]-1]-res[x[j][0]-1])

Submission status: Accepted

Solution code:
#-*- coding: utf-8 -*-
"""
oj dl https://atcoder.jp/contests/abc116/tasks/abc116_b -d test-b
oj test -d test-c -c "python abc116c.py"
oj test -d test-b -c "python abc116b.py" test-b/sample-3.in
"""

from collections import defaultdict
import sys
import math
import time
import itertools

#累積和
def deco(func):
    def wrapper(*args, **kwargs):
        s = time.time()
        #print('--start--')
        ret = func(*args, **kwargs)
        logging.debug('--end in %f --' % (time.time() - s) )
        return ret
    return wrapper


@deco
def sol(N, Q, S, LR):
    M = [0] * N
    logging.debug("%s, %s, %s, %s, %s" % (N, Q, S, LR, M))
    for i in range(1, N):
        logging.debug("i:%s" % i)
        if S[i-1] + S[i] == "AC":
            M[i] = M[i-1] + 1
        else:
            M[i] = M[i-1]

    A = [0]*Q
    for j in range(Q):
        l, r = int(LR[j][0])-1, int(LR[j][1])-1
        A[j] = M[r] - M[l]

    return A





import logging

do_submit = False
do_submit = True

if do_submit:
    logging.basicConfig(level=logging.ERROR, format="%(message)s")
else:
    logging.basicConfig(level=logging.DEBUG, format="%(message)s")
def input_parse(input_str):
    lines = [x.strip() for x in input_str.split("\n") if x.strip()]
    parsed_lines = [list(line.split()) for line in lines]
    (N, Q) = parsed_lines[0]
    N = int(N)
    Q = int(Q)
    S = parsed_lines[1][0]
    # return (n, S)
    LR = []
    for i in range(2, 2+Q):
        l , r = int(parsed_lines[i][0]), int(parsed_lines[i][1])
        LR.append((l, r))
    return (N, Q, S, LR)



if not do_submit:
    # n, S= input_parse("""
    # 4
    # 1 2 2 1
    # """)
    (N, Q, S, LR) = input_parse("""
    8 3
    ACACTACG
    3 7
    2 3
    1 8
    """)
    for a in sol(N, Q, S, LR):
        print (a)

    (N, Q, S, LR) = input_parse("""
    20 6
    AGCTAATTTACACGTAATCC
    3 7
    2 3
    1 8
    1 20
    9 18
    14 18
    """)
    for a in sol(N, Q, S, LR):
        print (a)

else:
    str = ""
    NQ = input().strip()
    N, Q= list(map(int, NQ.split()))
    str += NQ + "\n"
    str += input().strip() + "\n"# S
    for i in range(Q):
        str += input().strip() + "\n" # l, r
    (N, Q, S, LR) = input_parse(str)
    #print(sol(N, Q, S, LR))
    for a in sol(N, Q, S, LR):
        print (a)

Submission status: Accepted

Solution code:
N,Q = map(int,input().split())
S = input()
point = [list(map(int,input().split())) for i in range(Q)]
ac_list = [0]*(N+1)

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


for i in range(Q):
  print(ac_list[point[i][1]-1] - ac_list[point[i][0]-1])

Submission status: Accepted

Solution code:
N, Q = map(int, raw_input().split())
S = raw_input()
countlist = []
flag = False
cnt = 0
for i in range(0, len(S)):
	if flag:
		if S[i] == 'C':
			cnt += 1
		flag = False
	if S[i] == 'A':
		flag = True
	countlist.append(cnt)

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

Submission status: Accepted

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

for i in range(Q):
    a.append(list(map(int, input().split())))

for i in range(len(S)):
    an[i+1]=an[i]
    if S[i:i + 2] == "AC":
        an[i+1] += 1
# print(an)

for i in range(Q):
    print(an[a[i][1]-1] - an[a[i][0] - 1])

Submission status: Accepted

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

total_list = []
total = 0
for i in range(N-1):
  if S[i] == 'A' and S[i+1] == 'C':
    total += 1
  total_list.append(total)

for i in range(Q):
  l, r = T[i][0], T[i][1]
  if l != 1:
    print(total_list[r-2]-total_list[l-2])
  else:
    print(total_list[r-2])

Submission status: Accepted

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

t = [0] * N
a = [0] * N

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

a[0] = 0
for i in range(N - 1):
    a[i + 1] = a[i] + t[i]

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

Submission status: Accepted

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

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

for q in range(Q):
    l, r = lrList[q][0], lrList[q][1]
    ans = ACList[r - 1] - ACList[l - 1]
    print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

c=0
s=[0]
for i in range(1,N):
    if S[i-1]=='A' and S[i]=='C':
        c+=1
    s.append(c)
    
for i in range(Q):
    l,r=map(int,input().split())
    out=s[r-1]-s[l-1]

    print(out)

Submission status: Accepted

Solution code:
N,Q = (int(x) for x in input().split())
S = list(input())
count = [0 for i in range(N)]
c = 0
for i in range(N-1):
    if S[i] == 'A':
        if S[i+1] == 'C':
            count[i] = c
            c += 1
            i += 1
        elif S[i+1] != 'A':
            count[i] = c
            i += 1 
    count[i] = c
if count[-2] > count[-1]:
    count[-1] = count[-2]

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

Submission status: Accepted

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

cumu = [0]*(N+1)

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

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

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = input()
a = []
an = [0] * (N + 1)
for i in range(Q):
    a.append(list(map(int, input().split())))

for i in range(len(S) - 1):
    an[i + 1] = an[i]
    if S[i:i + 2] == "AC":
        an[i + 1] += 1
for i in range(Q):
    print(an[a[i][1] - 1] - an[a[i][0] - 1])

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
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 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

N,Q=MAP()
S=input()

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

for i in range(Q):
    l,r=MAP()
    print(sm[r]-sm[l])

Submission status: Accepted

Solution code:
from bisect import bisect_left as b_l
n,q=map(int,input().split())
s=input()
pi=0
aci=[]
while 1:
    ni=s[pi:].find("AC")
    if ni==-1:
        break
    aci+=[ni+pi]
    pi+=ni+1
for i in range(q):
    si,ei=map(int,input().split())
    print(b_l(aci,ei-1)-b_l(aci,si-1))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

ACList = list()
prevA = False
accum = 0
for i in range(N):
    if prevA and S[i] =='C':
        accum += 1
    if S[i] == 'A':
        prevA = True
    else:
        prevA = False
    ACList.append(accum)

for i in range(Q):
    print( ACList[li[i][1]-1] - ACList[li[i][0]-1] )

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
str = input()
q = int(q)
dic = {}

for j in range(len(str)):
  if (j > 0):
    if (str[j-1] == 'A' and str[j] == 'C'):
      dic[j] = dic[j-1] + 1
    else:
      dic[j] = dic[j-1]
  else:
    dic[j] = 0

for i in range(q):
  s,e = map(int,input().split())
  ans = dic[e-1] - dic[s-1]
  print(ans)

Submission status: Accepted

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

total_list = []
total = 0
try:
  for i in range(N-1):
    if S[i] == 'A' and S[i+1] == 'C':
      total += 1
    total_list.append(total)

  for i in range(Q):
    l, r = T[i][0], T[i][1]
    if l != 1:
      print(total_list[r-2]-total_list[l-2])
    else:
      print(total_list[r-2])
except IndexError:
  print(0)

Submission status: Accepted

Solution code:
n, q = list(map(int, input().split(" ")))
s = input()
s = s.replace("AC", "ZC")
num = 0
ac_index = []
for _s in s:
    if _s == "Z":
        ac_index.append(num)
        num += 1
    else:
        ac_index.append(num)
i = 0

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

Submission status: Accepted

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

for i in range(1, n):
  if s[i] == "C" and s[i-1] == "A":
    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])

Submission status: Accepted

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

numAC = 0
noAs, noCs = [0]*N, [0]*N
for i in range(N-1):
    if Ss[i:i+2] == 'AC':
        numAC += 1
        noAs[i] = numAC
        noCs[i+1] = numAC

noAs[-1] = numAC+1
for i in reversed(range(N-1)):
    if noAs[i] == 0:
        noAs[i] = noAs[i+1]
for i in range(1, N):
    if noCs[i] == 0:
        noCs[i] = noCs[i-1]

anss = []
for L, R in LRs:
    L, R = L-1, R-1
    anss.append(max(0, noCs[R]-noAs[L]+1))

print('\n'.join(map(str, anss)))

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
st = input()
questions = [tuple(map(int, input().split())) for i in range(q)]
lis = []
cnt = 0
for i in range(len(st)-1):
    if st[i-1:i+1] == 'AC':
        cnt += 1
    lis.append(cnt)
if st[-2:] == 'AC':
    cnt += 1
lis.append(cnt)
for l, r in questions:
    print(lis[r-1] - lis[l-1])

Submission status: Accepted

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

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

for i in range(q):
    print(cum[a[i][1]-1]-cum[a[i][0]-1])

Submission status: Accepted

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

    # 累積出現数を格納: 指定される番号が1始まりなのでズラして格納
    p = [0] * (n+1)
    for i in range(n):
        p[i+1] = p[i] + (1 if s[i:i+2] == "AC" else 0)

    for i in range(q):
        l, r = map(int, input().split())
        # 終端(=l-1)から始端-1(=r-1)の累積出現数を引いた数が指定区間内での出現回数
        print(p[r-1] - p[l-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,q = [int(i) for i in input().split()]
s = input()
l = []
r = []
memo = [0] * 100001
for i in range(q):
    x,y=[int(i) for i in input().split()]
    l.append(x)
    r.append(y)
#カウントの処理は1回
for i in range(len(s)):
    if i==0:
        continue
    else:
        memo[i] = memo[i-1] + s[i-1:i+1].count("AC")

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

Submission status: Accepted

Solution code:
nq = input().split()
n, q = int(nq[0]), int(nq[1])
s = list(input())
r_li = []
l_li = []
t_li = []
for i in range(q):
    rl = input().split()
    l_li.append(int(rl[0]))
    r_li.append(int(rl[1]))
count = 0
i = 0
while True:
    if i == n:
        break
    else:
        if s[i] == "A":
            if i == n - 1:
                i += 1
                t_li.append(count)
            else:
                if s[i + 1] == "C":
                    t_li.append(count)
                    count += 1
                    t_li.append(count)
                    i += 2
                else:
                    t_li.append(count)
                    i += 1
        else:
            i += 1
            t_li.append(count)
for i in range(q):
    print(t_li[r_li[i] - 1] - t_li[l_li[i] - 1])

Submission status: Accepted

Solution code:
N,Q = map(int,input().split(' '))
S = input()
#文字列のパターン
pattern = 'AC'
X = [0] * (N+1)

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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

list=[0]*(N+1)

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

    return


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 = map(int, input().split())
S = input()

c = [0] * N

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

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

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

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

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

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

for a in ans:
    print(a)

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)

for i in range(Q):
    l, r = LR[i][0], LR[i][1]
    cnt = t[r - 1] - t[l -1]
    print(cnt)

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
s = input()
ans =[0]*n
for i in range(1,n):
    if s[i-1] == 'A' and s[i] == 'C':
        ans[i] = 1
    ans[i] += ans[i-1]

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

Submission status: Accepted

Solution code:
# 入力
N,Q = map(int,input().split())
S = input()
# 0-indexed
query = [[int(e)-1 for e in input().split()] for _ in range(Q)]

# 開区間で持つ
acc = [0]*(N+1)
# [0,0)は何も含まない 更新は1から
for i in range(1,N):
    # 累積和 とりあえず前の値と同じにする
    # 開区間なのでS[i]を見るときはacc[i+1]を見る
    acc[i+1] = acc[i]
    if S[i-1] == "A" and S[i] == "C":
        # 条件を満たすなら+1
        acc[i+1] += 1

for l,r in query:
    # 開区間だからr+1,lになる
    # 閉区間と比べてl==0の場合分けが不必要
    ans = acc[r+1] - acc[l]
    # ただし、S[l-1]がAかつS[l]がCとなる場合は帳尻合わせに-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()
query = [[int(e)-1 for e in input().split()] for _ in range(Q)]
acc = [0]*(N+1)
for i in range(1,N):
    acc[i+1] = acc[i]
    if S[i-1] == "A" and S[i] == "C":
        acc[i+1] += 1
for l,r in query:
    ans = acc[r+1] - acc[l]
    if S[l-1] == "A" and S[l] == "C":
        ans -= 1
    print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

def io_generator():
	return input()

#+++++++++++++++++++

def main(io):
	n,q=map(int, io().split())
	s=list(io())
	
	ss=[0 for _ in s]
	sss=ss.copy()
	for i, c in enumerate(s[1:],1):
		if s[i-1]=='A' and s[i]=='C':
			ss[i]=1
		sss[i] = ss[i] + sss[i-1]
	
	for i in range(q):
		r, l=map(int, io().split())
		#rr=sum(ss[r-1:l])-ss[l-1]
		rr=sss[l-1]-sss[r-1]
		#ret.append(str(rr))
		print(rr)
	
#++++++++++++++++++++

if __name__ == "__main__":
	io= lambda : io_generator()
	#print (main(io))
	main(io)

Submission status: Accepted

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

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]
    
#print(cnt)

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

Submission status: Accepted

Solution code:
first_input = input().split(' ')

s_length = int(first_input[0])
num_of_Q = int(first_input[1])

input_string = input()

seq = [0]*s_length
count = 0

for s in range(s_length):
    if s > 0 and input_string[s-1:s+1] == 'AC':
        count += 1
    seq[s] = count

for q in range(num_of_Q):
    l_r = input().split(' ')
    l = int(l_r[0])
    r = int(l_r[1])

    print(seq[r-1] - seq[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]"):
    ac = [0]*N
    for i in range(1,N):
        if(S[i-1:i+1] == 'AC'):
            ac[i] = ac[i-1]+1
        else:
            ac[i] = ac[i-1]

    ans = [0]*Q
    for i in range(Q):
        ans[i] = ac[r[i]-1] - ac[l[i]-1]

    for i in ans:
        print(i)
    return


# Generated by 1.1.3 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 = map(int, input().split())
string = input()
 
counter = [0]*(N+1)

for i in range(N):
    counter[i+1] = counter[i] + (1 if string[i:i+2] == "AC" else 0)

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

Submission status: Accepted

Solution code:
from itertools import accumulate

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

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

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

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()
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()
acl=[]
for i in range(n-1):
    if s[i:i+2]=='AC':acl.append(i)
import bisect
for i in range(q):
    l,r=map(int, input().split())
    #print(bisect.bisect_left(acl,l-1))
    #print(bisect.bisect_right(acl,r-2))
    print(bisect.bisect_right(acl,r-2)-bisect.bisect_left(acl,l-1))

Submission status: Accepted

Solution code:
from sys import stdin
N,Q=[int(x) for x in stdin.readline().rstrip().split()]
S=(stdin.readline().rstrip())
acc=[0]*N
cnt=0
flag=0
for index,i in enumerate(list(S)):
    if i == "C" and flag == 1:
        cnt+=1
        flag=0
    if i != "C":
        flag=0
    if i == "A":
        flag=1
    acc[index]=cnt
for j in range(Q):
    n1,n2=[int(x) for x in stdin.readline().rstrip().split()]
    print(acc[n2-1]-acc[n1-1])

Submission status: Accepted

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

t=[0]*n

s=s.replace("AC", "Ac")
#s=s.translate(str.maketrans({'AC':'aC'})) maketransは置換元一文字じゃないといけんみたい
for i in range(n):
  if s[i] == "c":
    if i !=0:
      t[i]=1+t[i-1]
    else:
      t[i]=1
  else:
    t[i]=t[i-1]

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

Submission status: Accepted

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

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

for _ in range(Q):
    left, right = map(int, input().split())
    QS.append((left, right))

# print(l)
for left, right in QS:
    ans = l[right] - l[left]
    print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc122/tasks/abc122_c

import itertools
import collections
import bisect

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

    counter = [0] * N
    for i in range(N-1):
        if "{}{}".format(S[i], S[i+1]) == 'AC':
            counter[i] = 1 + (counter[i - 1] if i > 0 else 0)
        else:
            counter[i] = counter[i - 1] if i > 0 else 0
    # print(counter)

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

m = []
total = 0
b = False

for c in s:
    if c == 'A':
        b = True
    elif c == 'C' and b:
        total += 1
        b = False
    else:
        b = False
    m.append(total)

for _ in range(q):
    l, r = map(int, input().split())
    print(m[r-1] - m[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 j in range(q):
    l, r = map(int, input().split())
    ans = t[r-1] - t[l-1]
    print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

list = [0]*(N+1)

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

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

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

n, q = map(int, input().split(" "))
s = input()
cnt = 0
place_of_AC = [0] * n

for i in range(len(s) - 1):
  place_of_AC[i]=cnt
  if s[i:i+2] == "AC":
    cnt += 1


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

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
s = input()
flag = False
count = 0
li = []

for i in range(n):
    if s[i] == "A":
        flag = True
    elif s[i] == "C" and flag is True:
        count += 1
        flag = False
    else:
        flag = False
    li.append(count)

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()
b = [0]*(n+10)
for i in range(1,n):
	if S[i-1] == 'A' and S[i] == 'C':
		b[i] = 1
for i in range(1,n):
	b[i] += b[i-1]
for i in range(q):
	l,r = map(int,input().split())
	print(b[r-1]-b[l-1])

Submission status: Accepted

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


if __name__ == "__main__":
    main()