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

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter

sys.setrecursionlimit(10**9)
input = sys.stdin.readline

def ii(): return int(input())
def mi(): return map(int, input().split())
def lmi(): return list(map(int, input().split()))
def iif(n): return [int(input()) for _ in range(n)]
def lmif(n): return [list(map(int, input().split())) for _ in range(n)]
def ss(): return input().split()

def main():
    mod = 1000000007
    
    N, Q = mi()
    S = input()
    AC_cnt = [0] * len(S)
    cnt = 0
    for i in range(len(S)-1):
        if S[i] == "A" and S[i+1] == "C":
            cnt += 1
        AC_cnt[i+1] = cnt

    for i in range(Q):
        l, r = mi()
        print(AC_cnt[r-1] - AC_cnt[l-1])

    return

main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

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

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

for i in range(q):
    ll = lr[i][0] - 1
    rr = lr[i][1] - 1
    print(cnt[rr] - cnt[ll])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

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

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

for i in range(q):
    ll = lr[i][0] - 1
    rr = lr[i][1] - 1
    print(cnt[rr] - cnt[ll])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


def log(*args):
    print(*args, file=sys.stderr)


def main():
    n, q = map(int, input().split())
    s = input().rstrip()
    before = ''
    start_cumsum = []
    now_val = 0
    for (i, c) in enumerate(s):
        if c == 'A':
            before = 'A'
        elif c == 'C' and before == 'A':
            now_val += 1
            before = ''
        else:
            before = ''
        start_cumsum.append(now_val)
    for _ in range(q):
        l, r = map(int, input().split())
        print(start_cumsum[r - 1] - start_cumsum[l - 1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


def log(*args):
    print(*args, file=sys.stderr)


def main():
    n, q = map(int, input().split())
    s = input().rstrip()
    before = ''
    start_cumsum = []
    end_cumsum = []
    now_val = 0
    for (i, c) in enumerate(s):
        end_cumsum.append(now_val)
        if c == 'A':
            before = 'A'
        elif c == 'C' and before == 'A':
            now_val += 1
            before = ''
        else:
            before = ''
        start_cumsum.append(now_val)
    end_cumsum.append(now_val)
    # imos法を使う
    for _ in range(q):
        l, r = map(int, input().split())
        print(start_cumsum[r - 1] - start_cumsum[l - 1])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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()
dp=[0]*n
count=0
for i in range(n-1):
  if s[i]=="A" and s[i+1]=="C":
    dp[i]=1+count
    count+=1
  else:
    dp[i]=count

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)

n, q = map(int, input().split())
s = input()
readline = sys.stdin.readline
LR = [[int(i)-1 for i in readline().split()] for _ in range(q)] # 0-indexed

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

# 累積和を作る
tot = [0]*(len(nums)+1)
for i in range(len(nums)):
    tot[i+1] = tot[i]+nums[i]

for l,r in LR:
    print(tot[r]-tot[l])

Submission status: Accepted

Solution code:
N,Q = (int(X) for X in input().split())
S = input()
T = [0]*(N+1)
for I in range(0,N):
     T[I+1] = T[I] + (S[I:I+2]=='AC')
for J in range(0,Q):
    L,R = (int(X)-1 for X in input().split())
    print(T[R]-T[L])

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import copy




N,X=map(int,input().split())
S=input()
lenS=len(S)

RS=S[::-1]

goukei=0
G=[]
G.append(0)
Rgoukei=0
RG=[]
for i in range(1,lenS):
    if S[i]=="C":
        if S[i-1]=="A":
            goukei+=1
    G.append(goukei)


RG.append(0)
for i in range(1,lenS):
    if RS[i]=="A":
        if RS[i-1]=="C":
            Rgoukei+=1
    RG.append(Rgoukei)
RG.reverse()

#print(G)
#print(RG)

for i in range(X):
    A,B=map(int,input().split())
    print(goukei-G[A-1]-RG[B-1])

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
s = input()
inf = [0]*n
num = 0
for i in range(1,n):
    if s[i] == "C" and s[i-1] == "A":
        num += 1
    inf[i] += num
for i in range(q):
    a,b = map(int,input().split())
    print(inf[b-1] - inf[a-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 bisect
n, q = map(int, input().split())
s = input()
cnt = 0
apoint = []
cpoint = []
for i in range(len(s) - 1):
    if s[i] + s[i + 1] == 'AC':
        cnt += 1
        apoint.append(i)
        cpoint.append(i)
# print('cnt:', cnt)
# print('acpoint:', apoint)
for i in range(q):
    l, r = map(int, input().split())
    l, r = l - 1, r - 1
    left = bisect.bisect_left(apoint, l)
    right = bisect.bisect_left(cpoint, r)
    print(right - left)

Submission status: Accepted

Solution code:
def main():
    n, q = map(int, input().split())
    s = input()
    indic = {}
    for i in range(q):
        l, r = map(int, input().split())
        indic[i] = [l, r]
    
    ruisekidic = {}
    tmp = 0
    
    for i in range(n):
        if i == 0:
            mae = s[0]
            ruisekidic[i] = 0
        else:
            if mae == "A" and s[i] == "C":
                tmp += 1
                ruisekidic[i] = tmp
                mae = s[i]
            else:
                ruisekidic[i] = tmp
                mae = s[i]
    for i in range(q):
        [l, r] = indic[i]
        if l > 0:
            print(ruisekidic[r-1] - ruisekidic[l-1])
        else:
            print(ruisekidic[r-1])


    
if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

cum = [0]*(n+1)
pre = s[0]
cnt=0
for i in range(1,n):
    now = s[i]
    if pre=="A" and now=="C":
        cnt+=1
    cum[i+1] = cnt
    pre = now
for l,r in lr:
    print(cum[r]-cum[l])

Submission status: Accepted

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

import io
import sys
import math

def solve(ac_lst,l,r):
    # implement process
    #l=2,r=3
    if l == 1:
        return ac_lst[r-2]
    return ac_lst[r-2] - ac_lst[l-2]
    

def make_ac_lst(s):
    ac_lst = [0] * len(s)
    for i in range(len(s)-1):
        if i != 0:
            ac_lst[i] += ac_lst[i-1]
        if s[i] == "A" and s[i+1] == "C":
            ac_lst[i] += 1
    ac_lst[-1] = ac_lst[-2]

    if _DEB: logd(f"{ac_lst}")
    return ac_lst

def main():
    # input
    n,q = map(int, input().split())
    s = input()
    
    # process
    ans = ""
    ac_lst = make_ac_lst(s)

    for _ in range(q):
        l,r = map(int, input().split())
        ans += str( solve(ac_lst,l,r) ) + "\n"
         
    # output    
    print(ans)
    return ans
        
### DEBUG I/O ###
_DEB = 0   # 1:ON / 0:OFF

_INPUT = """\
8 3
ACACTAAC
7 8
2 3
1 8
"""
_EXPECTED = """\
2
0
3

"""

def logd(str):
    """usage:
    if _DEB: logd(f"{str}")
    """
    if _DEB: print(f"[deb] {str}")

### MAIN ###
if __name__ == "__main__":
    if _DEB:
        sys.stdin = io.StringIO(_INPUT)
        print("!! Debug Mode !!")

    ans = main()

    if _DEB:
        print()
        if _EXPECTED.strip() == ans.strip(): print("!! Success !!")
        else: print(f"!! Failed... !!\nANSWER:   {ans}\nExpected: {_EXPECTED}")

Submission status: Accepted

Solution code:
import copy

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 = str(input())
li = []
cnt = 0

for i in range(N-1):
  if S[i]=='A' and S[i+1]=='C':
    cnt += 1
    li.append(cnt)
  else:
    li.append(cnt)

for i in range(Q):
  l, r = map(int, input().split())
  if l > 1:
    ans = li[r-2] - li[l-2]
  else:
    ans = li[r-2]
  print(ans)

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:
import sys
read = sys.stdin.read
def main():
    n, q = map(int, input().split())
    s = input()
    acs = [0] * (n + 1)
    cnt = 0
    for i1 in range(1, n):
        if s[i1-1] =='A' and s[i1] == 'C':
            cnt += 1
        acs[i1+1] = cnt
    for _ in range(q):
        l, r = map(int, input().split())
        r = acs[r] - acs[l]
        print(r)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

def solve():
    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):
        print(t[lr[j][1]-1]-t[lr[j][0]-1])

if __name__ == "__main__":
    N,Q = list(map(int, input().split()))  
    S = input()
    lr = [list(map(int, input().split())) for _ in range(Q)]
    solve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect,copy,heapq,string
from collections import *
from math import *
from itertools import *
import sys
sys.setrecursionlimit(10 ** 6)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n, q = MAP()
s = input()
p = [LIST() for i in range(q)]
l = [0]*n
r = [0]*n

for i in range(n-1):
    if s[i] + s[i+1] == "AC":
        l[i] += 1
        r[i+1] += 1

for i in range(1,n):
    l[i] += l[i-1]
    r[i] += r[i-1]

for i in range(q):
    print( r[p[i][1]-1] - r[p[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)]

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

# クエリ
for q in LR:
    l = q[0] - 1
    r = q[1] - 1
    print(cumsum[r] - cumsum[l])

Submission status: Accepted

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

Submission status: Accepted

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

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

for _ in range(Q):
  l, r = map(int, input().split())
  if l == 1:
    print(cnt[r-1])
  else:
    if flag[l-1] == 0:
      print(cnt[r-1]-cnt[l-2])
    else:
      print(cnt[r-1]-cnt[l-2]-1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N,Q = list(map(int,input().split()))
s = input().rstrip()
lis=[0]*N
 
count = 0
for i in range(1,len(s)):
    if s[i-1] == 'A' and s[i] == 'C':
        count +=1
    lis[i]+=count
for i in range(Q):
    l,r = list(map(int,input().split()))
    print(lis[r-1]-lis[l-1])

Submission status: Accepted

Solution code:
def ss():
    N,Q = list(map(int,input().split()))
    s = input()
    lis=[0]*N
     
    count = 0
    for i in range(1,len(s)):
        if s[i-1] == 'A' and s[i] == 'C':
            count +=1
        lis[i]+=count
    for i in range(Q):
        l,r = list(map(int,input().split()))
        print(lis[r-1]-lis[l-1])

ss()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import re
 
N,Q = list(map(int,input().split()))
s = input()
lis=[0]*N
 
count = 0
for i in range(1,len(s)):
    if s[i-1] == 'A' and s[i] == 'C':
        count +=1
    lis[i]+=count
for i in range(Q):
    l,r = list(map(int,input().split()))
    print(lis[r-1]-lis[l-1])

Submission status: Accepted

Solution code:
import re
 
N,Q = list(map(int,input().split()))
s = input()
lis=[0]
 
count = 0
for i in range(1,len(s)):
    if s[i-1] == 'A' and s[i] == 'C':
        count +=1
    lis.append(count)
for i in range(Q):
    l,r = list(map(int,input().split()))
    print(lis[r-1]-lis[l-1])

Submission status: Accepted

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

cnt = [0]*N
i = 0
while i < N-1:
    if S[i:i+2] == "AC":
        cnt[i] += 1
        i += 1
    i += 1

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

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

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
s=input()
num=[0]
for i in range(n-1):
    if s[i+1]=="C" and s[i]=="A":
        num.append(num[-1]+1)
    else:
        num.append(num[-1])
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()
l = []
r = []
for q in range(Q):
    a,b = map(int, input().split())
    l.append(a)
    r.append(b)

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

for q in range(Q):
    print(s[r[q]] - s[l[q]])

Submission status: Accepted

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

Submission status: Accepted

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

a=[0]*n
from collections import defaultdict
tail=defaultdict(int)
for i in range(n-1):
    if t[i]=="A"and t[i+1]=="C":
        a[i+1]+=1
        tail[i]+=1
from itertools import accumulate
a=list(accumulate(a))
for _ in range(q):
    l,r=map(int,input().split())
    l,r=l-1,r-1
    if l==0:print(a[r])
    else:
        print(a[r]-a[l-1]-tail[l-1])

Submission status: Accepted

Solution code:
def resolve():
    import sys
    input = sys.stdin.readline
    N, Q = [int(i) for i in input().split()]
    S = input()
    pre = [0 for _ in range(N)]
    for i in range(N - 1):
        pre[i + 1] = pre[i] + (1 if S[i:i + 2] == "AC" else 0)
    for _ in range(Q):
        l, r = [int(i) for i in input().split()]
        print(pre[r - 1] - pre[l - 1])


resolve()

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

for k in range(Q):
  print(dp[R[k]-1]-dp[L[k]-1])

Submission status: Accepted

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

Submission status: Accepted

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

# 累積和
cumSum = [0] * (N + 1)

cnt = 0

for i in range(1, N):
    pre = S[i - 1]
    now = S[i]

    if pre == "A" and now == "C":
        cnt += 1

    cumSum[i + 1] = cnt
    pre = now

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

Submission status: Accepted

Solution code:
#ABC 122 C - GeT AC 18:47
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()
s += ' '
ruiseki = []
i = 0
while i<n:
    if s[i]+s[i+1]=='AC':
        ruiseki.append('')
        ruiseki.append('AC')
        i= i+1
    else:
        ruiseki.append(s[i])
    i+=1
t = [0] * (n+1)
for i in range(n):
    if ruiseki[i] == '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]-t[l])

Submission status: Accepted

Solution code:
import bisect
def main():
    N, Q = map(int, input().split())
    S = input()
    ll = []
    t = -1
    for i, v in enumerate(S):
        if v == 'A':
            t = i
        elif v == 'C':
            if t == i-1:
                ll.append(i)
                t = -1
    for _ in range(Q):
        l, r = map(int, input().split())
        l -= 1
        r -= 1
        li = bisect.bisect_right(ll, l)
        ri = bisect.bisect_right(ll, r)
        print(ri-li)
main()

Submission status: Accepted

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

ac_cnts = [0]*(n)
curr_cnt = 0
for i, (s1,s2) in enumerate(zip(s[:-1],s[1:])):
    if s1 == 'A' and s2 == 'C':
        curr_cnt += 1
    ac_cnts[i+1] = curr_cnt

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

# print(ac_cnts)
# print(ans)

for a in ans:
    print(a)

Submission status: Accepted

Solution code:
N,Q = map(int,input().split())
S = input()
ruisekiwa = [0]*(N+1)
mode = 0
now = 0
for i in range(N):
  if S[i:i+2] == "AC":
    now += 1
  ruisekiwa[i+1] = now
for i in range(Q):
  l,r = map(int,input().split())
  print(ruisekiwa[r-1]-ruisekiwa[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)]

cumSum = [0]*(n+1)
pre = s[0]
cnt = 0
for i in range(1,n):
    now = s[i]
    if pre=="A" and now=="C":
        cnt += 1
    cumSum[i+1] = cnt
    pre = now
for l,r in lr:
    print(cumSum[r]-cumSum[l])

Submission status: Accepted

Solution code:
N, Q = list(map(int,input().split()))
S = input()
A = []
B = []
for i in range(Q):
    in1, in2 = list(map(int,input().split()))
    A.append(in1)
    B.append(in2)
ac = [0]
for i in range(1, N):
    if S[i] == "C" and S[i - 1] == "A":
        ac.append(ac[-1] + 1)
    else:
        ac.append(ac[-1])
        
for i in range(Q):
    ans = ac[B[i] - 1] - ac[A[i] - 1]
    print(ans)

Submission status: Accepted

Solution code:

N, Q = map(int, input().split())
S = input().rstrip('\n')
count = [0]*(N+2)

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

#累積和
for i in range(1, N+1):
    count[i] += count[i-1]

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

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
s = input()
lst = [0] * (n + 1)
reach = False
for i in range(n):
  if s[i] == 'A':
    reach = True
    lst[i + 1] = lst[i]
  else:
    if reach and s[i] == 'C':
      lst[i + 1] = lst[i] + 1
    else:
      lst[i + 1] = lst[i]
    reach = False
lst.pop(0)
#print(lst)
for i in range(q):
  l, r = map(int, input().split())
  print(lst[r - 1] - lst[l - 1])

Submission status: Accepted

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

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

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def rangeI(it, l, r):
    for i, e in enumerate(it):
        if l <= i < r:
            yield e
        elif l >= r:
            break

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

INF = 999999999999999999999999
MOD = 10**9+7

n,q = get_nums_l()
s = input()

ruiseki_ac = [0] * (n+1)

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

log(ruiseki_ac)

for i in range(q):

    a,b = get_nums_l()
    print(ruiseki_ac[b-1] - ruiseki_ac[a-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]+[0]*(N-1)
i=1
while i<N:
    if S[i-1]=='A' and S[i]=='C':
        count[i]=count[i-1]+1
    else:
        count[i]=count[i-1]
    i+=1

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

Submission status: Accepted

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

A_ruiseki = [0 for i in range(N+1)]
C_ruiseki = [0 for i in range(N+1)]

for i in range(0,N,1):
    if S[i]=="A" and S[i+1]=="C":
        A_ruiseki[i]+=1
        C_ruiseki[i+1]+=1

for i in range(1,N+1,1):
    A_ruiseki[i]+=A_ruiseki[i-1]
    C_ruiseki[i]+=C_ruiseki[i-1]

ans = []
for i in range(Q):
    l,r = map(int,input().split())
    A = A_ruiseki[r]-A_ruiseki[l-1]
    C = C_ruiseki[r]-A_ruiseki[l-1]
    ans.append(min(A,C))

for i in range(Q):
    print(ans[i])

Submission status: Accepted

Solution code:
N,Q = map(int, input().split())
S = input().strip()
a = []
p = ""
c = 0
for i,v in enumerate(S):
    if p == 'A' and v == 'C':
        c += 1
    a.append(c)
    p = v

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

Submission status: Accepted

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

    count = [0 for i in range(N + 1)]
    c = 0
    for i in range(1, N):
        if S[i-1] == "A" and S[i] == "C":
            c += 1
        count[i + 1] = c
    
    Query = list()
    for q in range(Q):
        Query.append(input())

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
s=input()
a=[0]*(n+1)
for i in range(n-1):
  if s[i:i+2]=='AC':
    a[i+1]=1
for i in range(n):
  a[i+1]+=a[i]
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()

T = []
count = 0
idx = -1
for i,s in enumerate(S):
    if s =='C' and idx ==i-1:
        idx = -1
        count += 1
    elif s =='A':
        idx = i
    T.append(count)
q = []
for _ in range(Q):
    l,r = map(int,input().split())
    q.append([l,r])
for l,r in q:
    print(T[r-1]-T[l-1])

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

for i in range(n):
    m = 0
    if s[i:i+2] == 'AC':
        m = 1
    t[i + 1] = t[i] + m

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

Submission status: Accepted

Solution code:
import itertools

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

cnt = [0]*N

for i in range(N):
    if i >= N-1:
        continue
    if S[i] == "A":
        if S[i+1] == "C":
            cnt[i+1] = 1

acum = list(itertools.accumulate(cnt))

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

Submission status: Accepted

Solution code:
import re
import itertools

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

pos = [m.end() for m in re.finditer(r'AC', s)]

dp = [0] * (N+1)
for p in pos:
    dp[p] = 1
dp = list(itertools.accumulate(dp))

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

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

Submission status: Accepted

Solution code:
from re import finditer
from bisect import bisect_left
from bisect import bisect_right
a,b=map(int,input().split())
c=input()
d=[]
for _ in range(b):
    n,m=map(int,input().split())
    d.append([n-1,m-1])
n=len(d)
ac1=[m.start() for m in finditer('AC', c)]
ac2=[m.end()-1 for m in finditer('AC', c)]
for i in range(n):
    index1=bisect_left(ac1,d[i][0])
    index2=bisect_right(ac2,d[i][1])
    print(index2-index1)

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