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()
flag = False
L = [0 for _ in range(n)]
cnt = 0
for i, s in enumerate(S):
    if flag:
        if s == "C":
            cnt += 1
        flag = False
    if s == "A":
        flag = True
    L[i] = cnt

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

Submission status: Accepted

Solution code:
from sys import stdin

n,q = map(int,stdin.readline().split())
s = input()
lr = [list(map(int,stdin.readline().split())) for i in [0]*q]

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

idx = 0
loc = 0
numac = [0 for i in [0]*n]
for i in range(n):
    if posac[idx]==i:
        loc += 1
        idx += 1
    numac[i] = loc
numac.append(loc)

#print(numac)
for i in lr:
    l,r = i[0]-1,i[1]-1
    print(numac[r]-numac[l])

Submission status: Accepted

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

s = input()

v = [0] * n

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

m = [0] * (n + 1)
for i in range(n):
    m[i + 1] = m[i] + v[i]


for i in range(q):
    l, r = map(int, input().split())
    l -= 1
    ans = 0
    if r - l < 2:
        ans = 1
    else:
        ans = m[r] - m[l]
        if v[r - 1] == 1:
            ans -= 1
    print(ans)

Submission status: Accepted

Solution code:
import sys

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

cnt = [0]*(N+1)
wasA = False

for i in range(0,N):
  if wasA and S[i] == "C":
    cnt[i+1] = cnt[i] + 1
    wasA = False
  elif S[i] == "A":
    cnt[i+1] = cnt[i]
    wasA = True
  else:
    cnt[i+1] = cnt[i]
    wasA = False

#print(cnt)    

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

Submission status: Accepted

Solution code:
a,b=map(int,input().split())
n = input()
m = [0]*a
for i in range(1,a):
  if n[i-1:i+1]=="AC":
    m[i]=m[i-1]+1
  else:
    m[i]=m[i-1]
for j in range(b):
  s,t=map(int,input().split())
  print(m[t-1]-m[s-1])

Submission status: Accepted

Solution code:
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
# from decorator import stop_watch
# 
# 
# @stop_watch
def solve(N, Q, S, LRi):
    cumulative_sum = [0, 0]
    for i in range(1, N):
        tmp = cumulative_sum[-1]
        if S[i - 1:i + 1] == 'AC':
            tmp += 1
        cumulative_sum.append(tmp)

    for l, r in LRi:
        print(cumulative_sum[r] - cumulative_sum[l])


if __name__ == '__main__':
    N, Q = map(int, input().split())
    S = input()
    LRi = [[int(i) for i in input().split()] for _ in range(Q)]
    solve(N, Q, S, LRi)

    # # test
    # from random import randint
    # from func import random_str
    # N, Q = 10 ** 5, 10 ** 5
    # S = random_str(N, 'ACGT')
    # LRi = [sorted([randint(1, N) for _ in range(2)]) for _ in range(Q)]
    # solve(N, Q, S, LRi)

Submission status: Accepted

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

cum = [0]*(N+1)

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

ans = []
for l, r in LR:
    result = cum[r-1] - cum[l-1]
    ans.append(result)

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

Submission status: Accepted

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

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

lsAC = [0,0]
AC = 0
for i in range(N-1):
    if S[i]=='A' and S[i+1]=='C':
        AC += 1
    lsAC.append(AC)
for i in range(Q):
    print(lsAC[lsline[i][1]]-lsAC[lsline[i][0]])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
s=input()
con=[0]
c=False
for i in range(n):
    if s[i]=='A':
        c=True
        con.append(con[-1])
        continue
    if c:
        if s[i]=='C':
            con.append(con[-1]+1)
            c=False
            continue
        else:
            con.append(con[-1])
            c=False
            continue
    con.append(con[-1])    
for j in range(q):
    l,r=map(int,input().split())
    print(max(0,con[r]-con[l]))

Submission status: Accepted

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

Submission status: Accepted

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

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

for l,r in lr:
  print(rui[r-1] - rui[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)]

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

for i in range(q):
  print(rui[lr[i][1]-1] - rui[lr[i][0]-1])

Submission status: Accepted

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


t = [0] * (N+1)

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

for j 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()
R = [0]*(N+1)
A = False
C = False
for i in range(0,N):
  char = S[i]
  if char == 'A':
    A = True
  elif char == 'C' and A:
    R[i+1]+=1
    A = False
  else:
    A = False
  R[i+1]+=R[i]
for _ in range(Q):
  l, r = map(int,input().split())
  print(R[r]-R[l])

Submission status: Accepted

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

# 累積和 s を計算
c = [0 for _ in range(N + 1)]
for i in range(1, N):
    a = 0
    if S[i-1:i+1] == 'AC':
        a = 1
    c[i + 1] = c[i] + a

# 各クエリに答える
for _ in range(Q):
    l, r = map(int, input().split())
    l -= 1
    result = c[r] - c[l]
    if l > 0 and S[l-1:l+1] == 'AC':
        result -= 1
    print(result)

Submission status: Accepted

Solution code:
N,Q=map(int,input().split())
S=input()
li=[0]
A=False
ans=0
import copy
for i in range(N):
    if A==True:
        if S[i]=="C":
            ans+=1
        A=False
    if S[i]=="A":
        A=True
    li.append(copy.copy(ans))
for j in range(Q):
    a,b=map(int,input().split())
    print(li[b]-li[a])

Submission status: Accepted

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


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

for i in range(q):
    l,r=[int(i) for i in input().split()]
    print(dp[r-1]-dp[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)]

F=[0]*len(S)
for i in range(N-1):
    F[i+1]+=F[i]+(1 if S[i:i+2]=='AC' else 0)
    #print(i,F,S[i:i+2])
for l,r in LR:
    print(F[r-1]-F[l-1])

Submission status: Accepted

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

old=S[0]
cnt=0
rui = [0]*N
for i in range(1,N):
    now = S[i]
    if old=="A" and now=="C":
        cnt+=1
    old=now
    rui[i]=cnt    

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

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
s = input()
L = [0]*len(s)
for i in range(len(s)-1):
    if s[i] == "A" and s[i+1] =="C":
        L[i+1] = 1
L = [0]+L
for i in range(1,len(s)+1):
    L[i]+=L[i-1]
#print(L)
for i in range(k):
    a,b = map(int,input().split())
    print(L[b]-L[a])

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
s = input()
sl = [0]
for i in range(1, n):
    if s[i-1:i+1] == 'AC':
        sl.append(sl[i-1]+1)
    else:
        sl.append(sl[i-1])

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = input()
A = []
for i in range(N - 1):
  if S[i] == "A" and S[i+1] == "C":
    A.append(i+1)
lA = len(A)
for i in range(Q):
  l, r = map(int, input().split())
  L1 = -1
  R1 = lA
  while L1 + 1 < R1:
    C1 = (L1 + R1) // 2
    if A[C1] < l:
      L1 = C1
    else:
      R1 = C1
  L2 = -1
  R2 = lA
  while L2 + 1 < R2:
    C2 = (L2 + R2) // 2
    if A[C2] < r:
      L2 = C2
    else:
      R2 = C2
  print(L2 - L1)

Submission status: Accepted

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

a = [0] * N
c = 0

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

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

Submission status: Accepted

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

nums = [0]*n
for i in range(1,n):
  if s[i] == "C":
    if s[i-1] == "A": nums[i] += 1
  nums[i] += nums[i-1]
  
for _ in range(q):
  l,r = map(lambda x: int(x)-1, input().split())
  print(nums[r]-nums[l])

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
s = input()
ans = []
a = [0]*(10**5+1)
add = 0
check = False
for i in range(n):
    if check and s[i] == 'C':
        add +=1
    if s[i] == 'A':
        check = True
    else:
        check = False
    
    a[i] += add
for i in range(q):
    b,c = map(int,input().split())
    ans.append(a[c-1]-a[b-1])
for i in range(q):
    print(ans[i])

Submission status: Accepted

Solution code:
def examA():
    N = DI()/dec(7)
    ans = N
    print(N)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    N, Q = LI()
    S = SI()
    SS = [0]*N
    SSS = [0]*N
    for i in range(N-1):
        if S[i]=="A" and S[i+1]=="C":
            SS[i] = 1
    for i in range(N-1):
        SSS[i+1] += SSS[i]+SS[i]
    ans = [0]*Q

    for q in range(Q):
        l,r = LI()
        l -= 1; r -= 1
        ans[q] = SSS[r] - SSS[l]

    for v in ans:
        print(v)
    return

def examD():
    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examC()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Accepted

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


cum_sum = [0] * N
count_AC = [0] * N

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

        count_AC[i+1] = 2
        cum_sum[i+1] = 2
    cum_sum[i+1] = cum_sum[i] + cum_sum[i+1]


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

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())
  print(t[r-1] - t[l-1])

Submission status: Accepted

Solution code:
#入力:N,M(int:整数)
def input2():
	return map(int,input().split())

#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))
  
n,q=input2()
B=str(input())
LR=[input_array() for _ in range(q)]

# E=["A","C","G","T"]
T=[0]*(n+1) #1文字目〜n文字目までに出現する"AC"数の累積和

for i in range(n):
	if B[i:i+2] == "AC":	
		T[i+1] = T[i]+1
	else:
		T[i+1]=T[i]
for lr in LR:
	st=lr[0]-1
	fi=lr[1]-1
	print(T[fi]-T[st])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from bisect import bisect_left
n, q = map(int, input().split())
s = list(input())
L = []
for i in range(n - 1):
    if s[i] == "A" and s[i + 1] == "C":
        L.append(i)
ans = []
for i in range(q):
    l, r = map(int, input().split())
    l, r = l - 1, r - 1
    st = bisect_left(L, l)
    fi = bisect_left(L, r)
    ans.append(fi - st)

for i in ans:
    print(i)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
s = list(input())
num = [0] * n
count = 0
for i in range(n - 1):
    if s[i] == 'A' and s[i + 1] == 'C':
        count += 1
    num[i + 1] = count
for i in range(q):
    l, r = map(int, input().split())
    ans = num[r - 1] - num[l - 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)]

cnt = 0
lst = []
for i in range(n):
    if s[i-1:i+1] == 'AC':
        cnt += 1
    lst.append(cnt)

for i in range(q):
    print(lst[lr[i][1] - 1] - lst[lr[i][0] - 1])

Submission status: Accepted

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

import sys


def input():
    return sys.stdin.readline().strip()


n, q = [int(i) for i in input().split()]
S = input()

ac_table = [0] * (n + 1)  # その位置までにACが何個含まれているかを算出する。

prev = ""
for i in range(1, n + 1):
    if prev == "A" and S[i - 1] == "C":
        ac_table[i] = ac_table[i - 1] + 1
    else:
        ac_table[i] = ac_table[i - 1]
    prev = S[i - 1]

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

Submission status: Accepted

Solution code:
N,Q = map(int,input().split())
S = input()
lr = [list(map(int,input().split()))for _ in range(Q)]
l = [lr[i][0] for i in range(Q)]
r = [lr[i][1] for i in range(Q)]
#print(lr)
#print(l)
#print(r)

c = [0] * N
cnt = 0

for i in range(N-1):
    if S[i:i+2] == 'AC':
        c[i+1]=c[i]+1
    else:
        c[i+1]=c[i]
    #c[i] = S[:i].count('AC')
    #countを使わずにiまでの合計値をリスト化

#print(c)

for i,j in zip(l,r):
    #print(sum(c[:j])-sum(c[:i]))
    #l,r = map(int,input().split())
    print(c[j-1]-c[i-1])
    #合計値を利用してsumを使わずに差を表示して計算減させる
    #リストを要素ごとに分けるのは初めにやっておいて大丈夫

Submission status: Accepted

Solution code:
N,Q = map(int,input().split())
S = input()
lr = [list(map(int,input().split()))for _ in range(Q)]
l = [lr[i][0] for i in range(Q)]
r = [lr[i][1] for i in range(Q)]
#print(lr)
#print(l)
#print(r)

c = [0] * N
cnt = 0

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

#print(c)

for i,j in zip(l,r):
    #print(sum(c[:j])-sum(c[:i]))
    #l,r = map(int,input().split())
    print(c[j-1]-c[i-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    n,q = LI()
    s = "$" + S()

    lst = [0 for _ in range(n+1)]
    for i in range(n):
        before = s[i]
        after = s[i+1]
        if before == "A" and after == "C":
            lst[i+1] = lst[i] + 1
        else:
            lst[i+1] = lst[i]
    for _ in range(q):
        l,r = LI()
        ans = lst[r] - lst[l]
        print(ans)
main()

Submission status: Accepted

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

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

Submission status: Accepted

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

dp=[[0]*2 for _ in range(N)]
if S[0]=='A':
    dp[0][1]=1

for i in range(1,N):
    if S[i]=='C':
        dp[i][0]=dp[i-1][0]+dp[i-1][1]
    elif S[i]=='A':
        dp[i][0]=dp[i-1][0]
        dp[i][1]=1
    else:
        dp[i][0]=dp[i-1][0]
# print(dp)

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

Submission status: Accepted

Solution code:

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

n = len(S)
ctr = [0] * n
for i in range(n):
    if i > 0 and S[i - 1] == "A" and S[i] == "C":
        ctr[i] = 1

cumsum = [0] * (n + 1)
for i in range(n):
    cumsum[i + 1] = cumsum[i] + ctr[i]

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

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=input()
l=[0]
c=0
for i in range(1,n):
    if(s[i]=='C'):
        if(s[i-1]=='A'):
            c+=1
    l.append(c)
for q in range(k):
    x,y=map(int,input().split())
    print(l[y-1]-l[x-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from bisect import bisect_left
from bisect import bisect_right
n, q = map(int, input().split())
s = input()
lr = [tuple(map(int, input().split())) for _ in range(q)]

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

if ac == []:
    for i in range(q):
        print(0)
    exit()

for l, r in lr:
    l -= 1
    r -= 1
    li = bisect_left(ac, l)
    ri = bisect_right(ac, r)
    if li == ri:
        print(0)
    elif r > ac[ri-1]:
        print(ri-li)
    else:
        print(ri-li-1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, q = list(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().rstrip()
cnt = 0
tmp = 0
res = [0]*N
for i, s in enumerate(S):
    if s == "A":
        tmp = 1
    elif s=="C" and tmp == 1:
        tmp = 0
        cnt += 1
    else:
        tmp = 0
    res[i] = cnt
for _ in range(Q):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    print(res[r] - res[l])

Submission status: Accepted

Solution code:
import math
from math import gcd
INF = float("inf")

import sys
input=sys.stdin.readline
sys.setrecursionlimit(500*500)
import itertools
from collections import Counter,deque

def main():
    n,q = map(int, input().split())
    s = input().rstrip()
    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])

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, Q = map(int, readline().split())
    S = readline().strip()
    (*LR,) = map(int, read().split())

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

    ans = [0] * Q
    for i, (l, r) in enumerate(zip(*[iter(LR)] * 2)):
        l -= 1
        r -= 1
        ans[i] = vec[r] - vec[l]

    print('\n'.join(map(str, ans)))
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

ans = []
for i in range(Q):
  l, r = [int(x) for x in input().split(" ")]
  right = min([AinAC[r], CinAC[r]])
  left = max([AinAC[l - 1], CinAC[l - 1]])
  ans.append(str(right - left))

print("\n".join(ans))

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = " " + input()
l = []
r = []
for _ in range(Q):
    _l, _r = map(int, input().split())
    l.append(_l)
    r.append(_r)
dp = [0] * (N + 2) #i文字目から何個ACがあるか
cnt = 0
for i in range(1, N):
    if S[-i] == "C" and S[-i-1] == "A":
            cnt += 1
    dp[N-i] = cnt
#print(dp)
ans = 0
for q in range(Q):
    ans = dp[l[q]] - dp[r[q] + 1]
    if r[q] < N:
        if S[r[q]] == "A" and S[r[q] + 1] == "C":
            ans -= 1
    print(ans)

Submission status: Accepted

Solution code:
N,Q=map(int,input().split())
S=input()
L=[]
R=[]
C=[0]*N
c=0
for i in range(Q):
    A=list(map(int,input().split()))
    L.append(A[0])
    R.append(A[1])
for i in range(N-1):
    if S[i]=="A" and S[i+1]=="C":
        c+=1
        C[i]=c
    else:
        C[i]=c
C[N-1]=c
S+="X"
for i in range(Q):
    p=0
    if S[R[i]-1]=="A" and S[R[i]]=="C":
        p=C[R[i]-1]-C[L[i]-1]-1
    else:
        p=C[R[i]-1]-C[L[i]-1]
    if S[L[i]-1]=="A" and S[L[i]]=="C":
        p+=1
    print(p)

Submission status: Accepted

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

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

    cnt[i] = ac

for i in range(q):
    l, r = list(map(int, input().split()))

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:

n,q = list(map(int, input().split()))
s = input()
ans = [0]*(n+1)
lr=[list(map(int, input().split())) for _ in range(q)]
for i in range(1,n):
    
    if s[i-1]=='A' and s[i]=='C':
        ans[i+1] = ans[i] + 1
    else:
        ans[i+1]= ans[i]
#print(ans)
for i in range(q):
    print(ans[lr[i][1]]-ans[lr[i][0]])

Submission status: Accepted

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

    for q in range(Q):
        ans = Cumsum[lr[q][1]] - Cumsum[lr[q][0]]
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
s=input()
num=[0]
be=""

for i in range(n):
  if be=="A" and s[i]=="C":
    num.append(num[-1]+1)
    
  else:
    num.append(num[-1])
    
  be=s[i]
    
for i in range(q):
  l,r=map(int,input().split())
  
  print(abs(num[l]-num[r]))

Submission status: Accepted

Solution code:
import itertools

n,q=map(int,input().split())
s=input()
lst=[0]*(n-1)

for i in range(n-1):
  if s[i:i+2]=='AC':
    lst[i]+=1
    
lst=list(itertools.accumulate(lst))
lst=[0]+lst

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
N,Q=map(int,input().split())
S=input()
A=[]
C=[]
for i in range(N-1):
  if S[i]=='A' and S[i+1]=='C':
    A.append(i+1)
    C.append(i+2)
import bisect
for i in range(Q):
  l,r=map(int,input().split())
  a=bisect.bisect_left(A,l)
  c=bisect.bisect_right(C,r)
  print(c-a)

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)

#print (t)

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

Submission status: Accepted

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

s = list(input())

a = [0] * (n+1)

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

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

Submission status: Accepted

Solution code:
import sys
import math
 
 
def input():
    return sys.stdin.readline().rstrip()
 
 
def main():
    N, Q = map(int, input().split())
    S = list(input())
    t = [0] * N
    count =0
    for i in range(1,N):
        if S[i-1]=="A" and S[i] =="C":
            count +=1
        t[i] =count
 
    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:
n,q = map(int,input().split())
s=input()
LR=[]
for i in range(q):
    l,r = map(int,input().split())
    LR.append([l,r])

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

for i in range(q):
    l=LR[i][0]
    r=LR[i][1]
    ans = C[r-1]-C[l-1]
    print(ans)

Submission status: Accepted

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

def main(n,q,s,lr):
    count=[0]*n
    i=0
    nac=0
    while(i+1<n):
        count[i]=nac
        if s[i:i+2]=='AC':
            nac+=1
        i+=1
    count[i]=nac
    ans=[]
    for l,r in lr:
        ans.append(count[r-1]-count[l-1])
    return ans

if __name__=='__main__':
    n,q,s,lr=readinput()
    ans=main(n,q,s,lr)
    for a in ans:
        print(a)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    from itertools import accumulate
    N, Q = (int(i) for i in input().split())
    S = [s for s in input()]
    A = [0]*N
    for i in range(1, N):
        if S[i-1] == "A" and S[i] == "C":
            A[i] += 1
    acc = list(accumulate([0] + A))

    for _ in range(Q):
        le, ri = (int(i) for i in input().split())
        ans = acc[ri] - acc[le-1]
        if 0 < le and S[le-2] == "A" and S[le-1] == "C":
            ans -= 1
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

acum=[0]*(n+1)

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

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