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,M = list(map(int,input().split()))
l_n = input()
l_a = [0] * (N+1)
for i in range(N):
    l_a[i+1] = l_a[i] + (1 if l_n[i:i+2] == 'AC' else 0)
for i in range(M):
    l,r = map(int,input().split())
    print(l_a[r-1]-l_a[l-1])

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

INF = float('inf')

def solve():
    n, q = MI()
    S = input()
    ats = [0] * n
    cnt = 0
    for i in range(n-1):
        j = i + 2
        s = S[i:j]
        # print(s)
        if s == 'AC':
            cnt += 1
        ats[i+1] = cnt
    # print(ats)
    for _ in range(q):
        l, r = MI1()
        # print(S[l:r+1])
        print(ats[r] - ats[l])


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

INF = float('inf')

def solve():
    n, q = MI()
    S = input()
    ats = [0]
    cnt = 0
    for i in range(n-1):
        j = i + 2
        s = S[i:j]
        # print(s)
        if s == 'AC':
            cnt += 1
        ats.append(cnt)
    # print(ats)
    for _ in range(q):
        l, r = MI1()
        # print(S[l:r+1])
        print(ats[r] - ats[l])


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

INF = float('inf')

def solve():
    n, q = MI()
    S = input()
    ats = [0]
    cnt = 0
    for i in range(n-1):
        j = i + 2
        s = S[i:j]
        # print(s)
        if s == 'AC':
            cnt += 1
        ats.append(cnt)
    # print(ats)
    for _ in range(q):
        l, r = MI1()
        # print(S[l:r+1])
        print(ats[r] - ats[l])


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
N, Q = list(map(int, input().split()))
s = input()
lr = [list(map(int, input().split())) for i 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] = 1 + L[i]
  else:
      L[i + 1] = L[i]


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

Submission status: Accepted

Solution code:
# C - GeT AC

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

# ABCACAA = 0000100のようなリストを作る。ACが出てきたら1
L = [0]*(N)
for i in range(1, N):
    if S[i-1]=='A' and S[i]=='C':
        L[i] = 1

# 累積和を取る
Lsum = [0]*(N+1)
for i in range(N):
    Lsum[i+1] = Lsum[i]+L[i]

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

Submission status: Accepted

Solution code:
def get_ac(n, q, s, lrli):

    ans = []
    nli = [0]*(n+1)

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

    for i in lrli:
        ans.append(nli[i[1]]-nli[i[0]])

    return ans

def main():
    n, q = map(int, input().split())
    s = list(str(input()))
    lrli = [list(map(int, input().split()))for i in range(q)]
    ans = get_ac(n, q, s, lrli)
    for i in ans:
        print(i)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

for i in range(Q):
  l,r=map(int,input().split())
  l_li.append(l)
  r_li.append(r)

count=[0]*(N+1)#0桁目も入る
for i in range(N):#DPっぽく解いていく
  if i+1<N and S[i]=="A" and S[i+1]=="C":
    count[i+1]=count[i]+1
  else:
    count[i+1] = count[i]
for i in range(Q):
  print(count[r_li[i]-1]-count[l_li[i]-1])

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)

a = [0] * len(S)
for i, _ in enumerate(S[1:]):
    addition = 1 if S[i] + S[i+1] == 'AC' else 0
    a[i+1] = a[i] + addition

for l, r in zip(L, R):
    print(a[r-1] - a[l-1])

Submission status: Accepted

Solution code:
import math
# import itertools
# import statistics
# import numpy as np
#n = int(input())
n, q = list(map(int, input().split()))
#b = list(map(int, input().split()))
s = input()
lr = []
for i in range(q):
    x, y = list(map(int, input().split()))
    lr.append([x, y])

ac_count = [0]*int(len(s))
point = 0
for i in range(len(s)-1):
    if s[i] == "A" and s[i+1] == "C":
        ac_count[i] += point+0.5
        point += 0.5
        ac_count[i+1] += point+0.5
        point += 0.5
    else:
        ac_count[i] = point
ac_count[-1] = point
for i in range(q):
    print(math.floor(ac_count[lr[i][1]-1])-math.floor(ac_count[lr[i][0]-1]))

Submission status: Accepted

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

Submission status: Accepted

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

for i in range(n):
    if s[:i+1][-2:] == 'AC':
        cum_sum[i+1] += 1
    cum_sum[i+1] += cum_sum[i]

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

Submission status: Accepted

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

for _ in range(Q):
    l,r = map(int, input().split())
    L.append(l)
    R.append(r)
Query = list(zip(L, R))

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

S = [0]*(len(A)+1)
for i in range(len(A)):
    S[i+1] = S[i] + A[i]

for l,r in Query:
    print(S[r-1]-S[l-1])

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
s = input()
cum = [0] * n  # i文字目までに含まれるACの個数
for i in range(1, n):
    if s[i-1:i+1] == 'AC':
        cum[i] = cum[i-1] + 1
    else:
        cum[i] = cum[i-1]

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

Submission status: Accepted

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

reg = [0]*N
for i in range(N-1):
#     print(S[i:i+2])
    if S[i:i+2]=='AC':
        reg[i] += 1
        
regcum = [0] + list(itertools.accumulate(reg))

for l, r in LR:
    print(regcum[r-1] - regcum[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:
import sys
import math

N, Q = map(int, input().split())
S = input()
a = [0 for _ in range(N)]

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

for _ in range(Q):
    l, r = map(int, sys.stdin.readline().strip().split())
    print(a[r-1] - a[l-1])

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

Submission status: Accepted

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

Submission status: Accepted

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

s = input()

pre = [0]

for i,c in enumerate(s):
  last = pre[len(pre) -1 ]
  if i > 0 and c == 'C' and s[i-1] == 'A':
    pre.append(last+1)
  else:
    pre.append(last)
    
for _ in range(Q):
  l,r = map(int,input().split())
  ans = pre[r] - pre[l-1] + (0 if pre[l-1] == pre[l] else -1)
  print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import numpy as np

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

# 'AC'が登場した回数
A = [0] * (n + 1)
for i in range(n):
    if s[i:i + 2] == 'AC':
        A[i] = 1

S = [0] * (n + 2)
S[1:] = np.cumsum(A)

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

Submission status: Accepted

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

tmp = [0 for _ in range(n)]

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

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

Submission status: Accepted

Solution code:
import sys
from collections import deque

def main():
    N, Q = map(int, input().split())
    S = input()
    count = [0]
    for i in range(N-1):
        if S[i] == 'A' and S[i+1] == 'C':
            count.append(count[i]+1)
        else:
            count.append(count[i])
    for _ in range(Q):
        l, r = map(int, input().split())
        print(count[r-1] - count[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)]
S = [0]*(n+1)
for i in range(n):
    if s[i:i+2] == 'AC':
        S[i] = 1
A = [0]
for i in range(n):
    c = A[i] + S[i] 
    A.append(c)
for i in range(q):
    print(A[a[i][1]-1] - A[a[i][0]-1])

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = input()
count = [0]*N
for i in range(1, N): #i番目までに何個の'AC'があったかをリスト格納
    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:
#2問目
NQ = input().split()
N,Q = int(NQ[0]), int(NQ[1])
S = input()
P = [input().split() for i in range(Q)]
 
#累積和
ruiseki = [0]*N
for i in range(1,N):
    if(S[i] == "C" and S[i-1] == "A"):
        ruiseki[i] = ruiseki[i-1] + 1
    else:
        ruiseki[i] = ruiseki[i-1]
 
for j in range(Q):
    print(ruiseki[int(P[j][1]) - 1] - ruiseki[int(P[j][0]) - 1])

Submission status: Accepted

Solution code:
import sys
n,q=map(int,input().split())
s=input()
c=[0]*n
for i in range(2,n+1):
  if s[i-2:i]=='AC':
    c[i-1]=c[i-2]+1
  else:
    c[i-1]=c[i-2]
lr=sys.stdin.readlines()
for i in lr:
  l,r=map(int,i.split())
  print(c[r-1]-c[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)]
l=[0]*n
r=[0]*n
lcnt=0
rcnt=0
for i in range(n-1):
    if s[i]=="A" and s[i+1] == "C":
        # lcnt+=1
        rcnt+=1
        l[i+1]=1
    r[i+1]=rcnt
# print(l)
# print(r)
for i in lr:
    # print(max(0,r[i[1]-1]-r[i[0]-1]-l[i[0]-1]))
    # print(s[i[0]-1:i[1]])
    print(max(0,r[i[1]-1]-r[i[0]-1]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
import itertools


def sr():
    return sys.stdin.readline().rstrip()


def ir():
    return int(sr())


def lr():
    return list(map(int, sr().split()))


N, Q = lr()
S = sr()

ac = [0] * (N - 1)
for i, x in enumerate(zip(S[:], S[1:])):
    if x[0] == 'A' and x[1] == 'C':
        ac[i] = 1

cum = list(itertools.accumulate(ac))
ans_list = []
for _ in range(Q):
    l, r = lr()
    if (l - 2 < 0):
        result = cum[r - 2]
    else:
        result = cum[r - 2] - cum[l - 2]
    ans_list.append(result)
[print(ans) for ans in ans_list]

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n,q=map(int,input().split())
    s=input()
    lis=[0]*(n+1) 
    for i in range(n-1):
        if s[i:i+2]=="AC":
            lis[i+1]+=1
        lis[i+2]=lis[i+1]
    for i in range(q):
        l,r=map(int,input().split())
        print(lis[r-1]-lis[l-1])


if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys


def main():
    input = sys.stdin.readline
    n, q = map(int, input().split())
    s = input()
    li = [map(int, input().split()) for i in range(q)]
    count = [0]*len(s)

    for i in range(1, len(s)):
        if s[i] == "C" and s[i-1] == "A":
            count[i] = count[i-1] + 1
        else:
            count[i] = count[i-1]
   
    for i, j in li:
        print(count[j-1] - count[i-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# solution

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

Submission status: Accepted

Solution code:
import numpy as np
import sys
buf = sys.stdin.buffer
N,Q = map(int,buf.readline().split())
S = np.zeros(N+2, dtype='S1')
S[1:] = np.frombuffer(buf.read(N+1), dtype='S1')
A = (S == b'A')
C = (S == b'C')
AC = (A[:-1] & C[1:])
AC_cum = list(AC.cumsum())

for _ in range(Q):
  L,R = map(int,buf.readline().split())
  print(AC_cum[R-1] - AC_cum[L-1])

Submission status: Accepted

Solution code:
import numpy as np
N,Q = map(int,input().split())
S = np.array(list('_' + input()), dtype='U2')
A = (S == 'A')
C = (S == 'C')
AC = (A[:-1] & C[1:])
AC_cum = AC.cumsum()

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

Submission status: Accepted

Solution code:
# python3.4.2用
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from decimal import *
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') #無限大
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(sys.stdin.readline()) #整数読み込み
def ifn(): return float(sys.stdin.readline()) #浮動小数点読み込み
def isn(): return sys.stdin.readline().split() #文字列読み込み
def imn(): return map(int, sys.stdin.readline().split()) #整数map取得
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) #整数-1map取得
def fmn(): return map(float, sys.stdin.readline().split()) #浮動小数点map取得
def iln(): return list(map(int, sys.stdin.readline().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, sys.stdin.readline().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD
def lprint(l): print(*l, sep='\n')

N,Q = imn()
S = input()
L = []
R = []
for _ in range(Q):
    l,r = imn()
    L.append(l-1)
    R.append(r-1)

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

for i in range(Q):
    print(s[R[i]]-s[L[i]])

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
s = input()
ls = [0]
for i in range(n-1):
    if s[i] == 'A' and s[i+1] == 'C':
        ls.append(ls[i]+1)
    else:
        ls.append(ls[i])
for i 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())
holder = set()
for i in range(N-1):
    if S[i] == 'A' and S[i+1] == 'C':
        holder.add(i+1)

# 累積和でどうぞ
prefix = [0 for _ in range(N+1)]
for i in range(1, N+1):
    if i-1 in holder:
        prefix[i] = prefix[i-1] + 1
    else:
        prefix[i] = prefix[i-1]

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

Submission status: Accepted

Solution code:
from itertools import accumulate
N,Q = map(int,input().split())
S = str(input())
lr = [list(map(int,input().split())) for _ in range(Q)]
sl = [0]*N
for i in range(N):
  if S[i:i+2] == "AC":
    sl[i] = 1
slr = [0]+list(accumulate(sl))
ans = 0
for l,r in lr:
  ans = slr[r-1]-slr[l-1]
  print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
    N, Q = map(int, input().split())
    S = input().rstrip("\r\n")
    s = [0] * (N+1)
    s[0] = 0
    s[1] = 0
    for i in range(1, N):
        exists_AC = (S[i-1] == "A" and S[i] == "C")
        s[i+1] = s[i] + int(exists_AC)
    for _ in range(Q):
        l, r = map(int, input().split())
        print(s[r]-s[l])
if __name__ == "__main__":
    main()

Submission status: Accepted

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

number_of_AC_list = [0] * len(S)
total = 0
for i in range(1, len(S)):
    two_characters = S[i - 1] + S[i]
    if two_characters == 'AC':
        total += 1

    number_of_AC_list[i] = total
# print(number_of_AC_list)

for lri in lr:
    l_as_index = lri[0] - 1
    r_as_index = lri[1] - 1
    # print(lri, number_of_AC_list[l_as_index], number_of_AC_list[r_as_index])
    answer = number_of_AC_list[r_as_index] - number_of_AC_list[l_as_index]
    print(answer)

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = input()
List = [0 for _ in range(N)]
num = 0
for k in range(1,N):
  if S[k-1] == "A" and S[k] == "C":
    num += 1
  List[k] = num
  
for i in range(Q):
  l , r = map(int, input().split())
  print(List[r-1]-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())))
sa=[0,0]
c=0
for i in range(1,n):
  if s[i-1]+s[i]=='AC':
    c+=1
  sa.append(c)
for i in range(q):
  t=sa[lr[i][1]]-sa[lr[i][0]]
  print(t)

Submission status: Accepted

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

ac = [0] * n

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

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

    if l == 1:
        print(ac[r-2])
    else:
        print(ac[r-2] - ac[l-2])

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

Submission status: Accepted

Solution code:
import sys


input = sys.stdin.readline

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
n, q  = map(int, input().split())
l = list(input())
bef = ""
now = 0
stack = []

for i in range(n):
  if l[i] == "C" and (bef == "A"):
    now += 1
  stack.append(now)
  bef = l[i]
  
for _ in range(q):
  fr, to = map(int, input().split())
  print(stack[to-1] - stack[fr-1])

Submission status: Accepted

Solution code:
N, Q = [int(x) for x in input().split()]
S = 'X' + input()
lr = [[int(x) for x in input().split()] for _ in range(Q)]

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

for j in range(Q):
    print(cum[lr[j][1]] - cum[lr[j][0]])

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
import itertools

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, Q = lr()
S = sr()
ac = [0] * (N-1)
for i, x in enumerate(zip(S[:], S[1:])):
    if x[0] == 'A' and x[1] == 'C':
        ac[i] = 1

cum = list(itertools.accumulate(ac))
for _ in range(Q):
    l, r = lr()
    result = cum[r-2]
    if l > 1:
        result -= cum[l-2]
    print(result)

Submission status: Accepted

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

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

for _ in range(Q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    print(memo[y] - memo[x])

Submission status: Accepted

Solution code:
N,Q=map(int,input().split())
S=input()
A=[0]*(N+1)
C=[0]*(N+1)
for i in range(N-1):
  if S[i:i+2]=='AC':
    A[i+1]=1
    C[i+2]=1
import itertools
A=list(itertools.accumulate(A))
C=list(itertools.accumulate(C))
for q in range(Q):
  l,r=map(int,input().split())
  print(C[r]-A[l-1])

Submission status: Accepted

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list
#from itertools import combinations # (string,3) 3回
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    n,q = readInts()
    S = input()
    # A があって C がある、その次の場所を + 1してあげるよ。
    AC = [0] * n
    for i in range(1,n):
        if S[i - 1] == 'A' and S[i] == 'C':
            AC[i] = AC[i-1] + 1
        else:
            AC[i] = AC[i-1]
    #print(AC)
    for i in range(q):
        l,r = map(lambda x:int(x) - 1,input().split())
        print(AC[r] - AC[l])
if __name__ == '__main__':
  main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

cumulatives = [0] * (N + 1)

for i in range(N):
  # 右隣にCが来るAの数を数える
  if S[i:i + 2] == 'AC':
    cumulatives[i + 1] = cumulatives[i] + 1
  else:
    cumulatives[i + 1] = cumulatives[i]

for _ in range(Q):  
  l, r = map(lambda x: int(x) - 1, input().split())  # index 合わせる  
  print(cumulatives[r] - cumulatives[l])

Submission status: Accepted

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

cumulatives = [0] * (N + 1)

for i in range(N):
  if i == 0:
    cumulatives[1] = 0
  elif S[i - 1] == 'A' and S[i] == 'C':
    cumulatives[i + 1] = cumulatives[i] + 1
  else:
    cumulatives[i + 1] = cumulatives[i]
        
for _ in range(Q):
  l, r = map(lambda x: int(x) - 1, input().split())
  if l > 0 and S[l - 1] == 'A' and S[l] == 'C':
    # 右も閉区間なので+1
    print(cumulatives[r + 1] - cumulatives[l] - 1)
  else:
    print(cumulatives[r + 1] - cumulatives[l])

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
s_list = list(input())
l_r_list = [list(map(int, input().split())) for _ in range(q)]
c_sum = [0]
su = 0
for i in range(n - 1):
    if s_list[i] == "A" and s_list[i + 1] == "C":
        su += 1
    c_sum.append(su)
for l, r in l_r_list:
    print(c_sum[r - 1] - c_sum[l - 1])

Submission status: Accepted

Solution code:
#多分累積和?
n,q = list(map(int, input().split()))
s = input()
lr = [list(map(int, input().split())) for _ in range(q)]

sss = [0]
before = None
for i in s:
    if before=='A' and i=='C':
        sss.append(sss[-1] + 1)
    else: sss.append(sss[-1])
    before = i

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

Submission status: Accepted

Solution code:
import sys

n, m = map(int, sys.stdin.readline().split())
s = sys.stdin.readline().rstrip()
lr = zip(*[map(int, sys.stdin.read().split())] * 2)

def main():
    cnt = [0] * n
    for i in range(n - 1):
        cnt[i+1] = s[i:i+2] == 'AC'
    for i in range(n - 1): cnt[i+1] += cnt[i]
    for l, r in lr:
        print(cnt[r-1] - cnt[l-1])

if __name__ ==  '__main__':
    main()

Submission status: Accepted

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

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

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

Submission status: Accepted

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

for i in range(1, n):
    p = s[i-1:i+1]
    if p == 'AC':
        cnt += 1
    lst[i] = cnt
for _ in range(q):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    #print(l-1, lst[l-1])
    #print(r, lst[r])
    print(lst[r] - lst[l])

Submission status: Accepted

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

Submission status: Accepted

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

s = input()

t = [0]

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

    t.append(tmp)

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

Submission status: Accepted

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list
#from itertools import combinations # (string,3) 3回
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    n,q = readInts()
    s = input()
    nya = [0] * (n+1)# 累積和
    for i in range(n):
        if i+1 < n:
            if s[i] == 'A' and s[i+1] == 'C':
                nya[i+1] = nya[i] + 1
            else:
                nya[i+1] = nya[i]
    #print(nya)
    for q_ in range(q):
        l,r = readInts()
        l -=1
        r -=1
        print(nya[r] - nya[l])


if __name__ == '__main__':
  main()

Submission status: Accepted

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

ansl = [0]
a = 0
for i in range(n-1):
    if sl[i] == "A" and sl[i+1] == "C":
        a += 1
    ansl.append(a)

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

Submission status: Accepted

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

l = [0]*N
count = 0

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

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

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
s = input()
ans = [0 for _ in range(n)]
for i in range(len(s) - 1):
    if s[i:i+2] == "AC":
        ans[i+1] = ans[i]+1
    else:
        ans[i+1] = ans[i]
    #1indexの累積和

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