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:
#!/usr/bin/env python3
# n,m = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(sys.stdin.readline() for _ in range(n)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# n = int(sys.stdin.readline())
# INF = float("inf")
import sys,collections
N,Q = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
S = sys.stdin.readline().rstrip()
se = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(Q)) # multi line with multi param

INF = float("inf")
com = [0]*(N+1)

for i in range(N):
    com[i+1] = com[i]
    if S[i] == "A" and S[min(i+1,N-1)] == "C":
        com[i+1] += 1

for s,e in se:
    print(com[e-1] - com[s-1])

Submission status: Accepted

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

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, Q = map(int, readline().split())
S = readline().decode("utf-8").rstrip()
qs = []
for i in range(Q):
    l, r = map(int, readline().split())
    qs.append((l - 1, r - 1))


def solve():
    acc = [0] * (N + 1)
    for i in range(1, N + 1):
        acc[i] = acc[i - 1]
        if S[i - 1 : i + 1] == "AC":
            acc[i] += 1
    for l, r in qs:
        print(acc[r] - acc[l])


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce
from fractions import gcd
import sys
import re
def input(): return sys.stdin.readline().rstrip()
def I(): return int(input())
def Is(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(input())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = float('inf')
# ----------------------------------------------------------- #

n, q = Is()
s = S()
LR = TIR(q)
acc = [0]*(n+1)
tmp = 0
for i in range(1, n):
    if s[i-1] == "A" and s[i] == "C":
        tmp += 1
    acc[i] = tmp
for l, r in LR:
    l -= 1
    r -= 1
    print(acc[r]-acc[l])

Submission status: Accepted

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

Submission status: Accepted

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


def main():
    N, Q = map(int, input().split())
    S = input()
    appear = [0] * N # appear[i] = (0からi文字目までにACの出現した回数)

    prev = False
    if S[0] == 'A': prev = True
    for i in range(1, N):
        c = S[i]
        if c == 'A':
            prev = True
            appear[i] = appear[i - 1]
        elif prev and c == 'C':
            prev = False
            appear[i] = appear[i - 1] + 1
        else:
            prev = False
            appear[i] = appear[i - 1]
    #print(appear)
    
    for _ in range(Q):
        l, r = map(int, input().split())
        l, r = l - 1, r - 1
        if l == 0:
            print(appear[r])
        elif S[l-1:l+1] == "AC":
            print(max(0, appear[r] - appear[l - 1] - 1))
        else:
            print(appear[r] - appear[l - 1])


if __name__ == "__main__":
    main()

Submission status: Accepted

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

#n = int(input())
#l = list(map(int, input().split()))

'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''

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

cnt=[0]
c=0
for i in range(n-1):
    if s[i:i+2]=="AC":
        c+=1
    cnt.append(c)
#print(cnt)
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 = input()
ac = [0] * n
c = 0
for i in range(1, n):
    if s[i - 1] == 'A' and s[i] == 'C':
        c += 1
    ac[i] = c
for i in range(q):
    l, r = map(int, input().split())
    print(ac[r - 1] - ac[l - 1])

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, q = na()
s = input()
ct = [0] * n
for i in range(n-1):
    if s[i:i+2] == 'AC':
        ct[i+1] = 1
for i in range(n-1):
    ct[i+1] += ct[i]
for i in range(q):
    l, r = na()
    l -= 1
    r -= 1
    print(ct[r] - ct[l])

Submission status: Accepted

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

acsum = [0]*(n+1)
for i in range(len(s) - 1):
    if s[i:i+2] == "AC":
        acsum[i+2] = acsum[i+1] + 1
    else:
        acsum[i+2] = acsum[i+1]

for le, re in zip(l, r):
    print(acsum[re] - acsum[le])

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

cnts = [0] * (n)
cnt = 0
for i in range(1, n):
    if s[i-1:i+1] == "AC":
        cnt += 1
    cnts[i] = cnt
     
for i in range(q):
    l, r = lr[i]
    print(cnts[r-1] - cnts[l-1])

Submission status: Accepted

Solution code:
def resolve():
	n, q = map(int, input().split())
	s = input()
	seq = [0]*(n+1)
	for i in range(1, n):
		seq[i+1] = seq[i] + s[i-1:i+1].count('AC')
	for _ in range(q):
		l, r = map(int, input().split())
		print(seq[r] - seq[l])
resolve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import sys
from collections import Counter
from itertools import permutations, combinations
from fractions import gcd
#from math import gcd
from math import ceil, floor
import bisect
sys.setrecursionlimit(10 ** 6)
inf = float("inf")

def input():
    return sys.stdin.readline()[:-1]

def main():
    N, Q = map(int, input().split())
    S = input()
    L = [None] * Q
    R = [None] * Q
    for i in range(Q):
        L[i], R[i] = map(int, input().split())

    s = [0] * (N+1)
    for i in range(N):
        if i+1 < N and S[i] == 'A' and S[i+1] == 'C':
            s[i+1] = s[i] + 1
        else:
            s[i+1] = s[i]
        
    for i in range(Q):
        print(s[R[i]-1] - s[L[i]-1])

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
s = input()
l = []
for i in range(q):
    l.append(tuple(map(int,input().split())))
x = [0]*n
a = 0
flag = False
for i in range(n):
    if s[i] == 'A':
        flag = True
    elif s[i] == 'C' and flag:
        a += 1
        flag = False
    else:
        flag = False
    x[i] = a
for i in range(q):
    print(x[l[i][1]-1]-x[l[i][0]-1])

Submission status: Accepted

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

q = []

pref = [0] * (len(S))

c=0
for i in range(2, len(S)+1):
    if (S[i-2:i] == "AC"):
        c += 1
    pref[i-1] = c


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

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
s=input()
a=[0]*n
ac=0
for i in range(1,n):
    if s[i-1]=="A" and s[i]=="C":
        ac+=1
    a[i]=ac
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 = [0] * N
for i in range(N-1):
    t[i+1] = t[i] + (1 if S[i : i+2] == "AC" else 0)

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

Submission status: Accepted

Solution code:
#ABC122C
def main():
    import sys, re
    N, Q = map(int, sys.stdin.readline().split())
    S = sys.stdin.readline().rstrip()
    L = [tuple(map(int, sys.stdin.readline().split())) for _ in range(Q)]
    #print(S)
    #累積和
    W = [0 for _ in range(N+1)]
    for m in re.finditer('AC', S):
        W[m.span()[1]] = 1
    for i in range(N):
        W[i+1] += W[i]
    #print(W)
    for i in range(Q):
        print(W[L[i][1]]-W[L[i][0]])

if __name__ == '__main__':
    main()

Submission status: Accepted

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

S = input()

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

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

Submission status: Accepted

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

def resolve():
    from itertools import accumulate

    N,Q= map(int, input().split())  # N=len(A)
    S=input()
    l=[list(map(int,input().split())) for i in range(Q)]
    A = []
    for i in range(N-1):
        if S[i:i+2]=='AC':
            A.append(1)
        else:
            A.append(0)

    B = [0] + A
    B = list(accumulate(B))  # 累積和を格納したリスト作成

 
    for a,b in l:
        ans = B[b-1]-B[a-1]
        print(ans)

resolve()

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)
for i in range(N-1):
    if S[i] == 'A' and S[i+1] == 'C':
        dp[i+1] = dp[i] + 1
    else:
        dp[i+1] = dp[i]

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

Submission status: Accepted

Solution code:
from itertools import accumulate
n,q=list(map(int,input().split()))
s=input()
l=[0]*q
r=[0]*q
for i in range(q):
    l[i],r[i]=list(map(int,input().split()))
L=min(l)
R=max(r)
#前処理
A=[]
for i in range(L,R):
    if s[i-1]=="A"and s[i]=="C":
        A.append(1)
    else:
        A.append(0)
A.append(0)
s=[0]+A
S=list(accumulate(s))
#累積和
for i in range(q):
    print(S[r[i]-L]-S[l[i]-L])

Submission status: Accepted

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

count = [0]*n

num = 0
for i in range(n-1):
    if s[i] == "A" and s[i+1] == "C":
        num += 1
    count[i] = num
count.insert(0,0)
count[-1] = count[-2]

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

Submission status: Accepted

Solution code:
import itertools


def main():
    N, Q = list(map(int, input().split(' ')))
    S = input()
    ac_flag = [0 for _ in range(N + 1)]
    before_c = None
    for i, c in enumerate(S):
        if (before_c, c) == ('A', 'C'):
            ac_flag[i + 1] = 1
        before_c = c
    ac_count = list(itertools.accumulate(ac_flag))
    answer = list()
    for _ in range(Q):
        L, R = list(map(int, input().split(' ')))
        answer.append(ac_count[R] - ac_count[L])
    for a in answer:
        print(a)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,Q = map(int, input().split())
S   = input()
Query = []
for _ in range(Q):
    l,r = map(int, input().split())
    Query.append([l, r])

A = [0]*N
for i in range(N-1):
    if S[i]=="A" and S[i+1]=="C":
        A[i] = 1
s = [0]*(N+1)
for i in range(N):
    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()
cumsum = [0]*(N+1)
for i in range(1, N):
    if S[i-1:i+1] == 'AC':
        cumsum[i+1] = cumsum[i] + 1
    else:
        cumsum[i+1] = cumsum[i]

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

Submission status: Accepted

Solution code:
import itertools
import math

n, q = map(int, input().split())
s = input()
lr = []
for i in range(q):
    li , ri = list(map(int, input().split()))
    lr.append([li-1,ri-1])

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import accumulate
N,Q = list(map(int,input().split()))
S = list(input())
cnt = [0]*(N)
for i in range(N-1):
    if S[i] == 'A' and S[i+1] == 'C':
        cnt[i] = 1
R = [0]+list(accumulate(cnt))
for k in range(Q):
    x,y = list(map(int,input().split()))
    print(R[y-1]-R[x-1])

Submission status: Accepted

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

len=len(s)
L=[0]*len
R=[0]*len
res=s.count("AC")

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

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

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

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
s = list(input())
lrs = [list(map(int, input().split())) for _ in range(q)]
d = [0] * n
cnt = 0
for i in range(n-1):
    if s[i:i + 2] == ['A', 'C']:
        cnt += 1
    d[i+1] = cnt
for j in range(q):
    l, r = lrs[j][0], lrs[j][1]
    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):
	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())
l = [0]*n
r = [0]*n
for i in range(1,n):
    if s[i] == 'C':
        if s[i - 1] == 'A':
            l[i] = 1
            r[i] = 1
for i in  range(1, n):
    l[i] = l[i] + l[i - 1]
    r[i] = r[i] + r[i - 1]
for i in range(q):
    a,b = map(int,input().split())
    print(r[b - 1] - l[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)]
c=[0]*n
for i in range(n-1):
    c[i+1]=c[i]
    if s[i]=="A" and s[i+1]=="C":
        c[i+1]+=1
for i in range(q):
    st=lr[i]
    l=st[0]
    r=st[1]
    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 _ in range(Q)]
#dp[i]はi番目までの文字で'AC'がいくつあるか
dp = [0] * (N+1)
for i in range(1, N):
    if S[i-1] == 'A' and S[i] == 'C':
        dp[i] = dp[i-1] + 1
    else:
        dp[i] = dp[i-1]

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

Submission status: Accepted

Solution code:
n,q = map(int, input().split())
s = input()
a = [0]*n
for i in range(1,n):
    a[i] = a[i-1]
    if (s[i]=="C"):
        if (s[i-1]=="A"):
            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:
import bisect
N,Q=map(int,input().split())
S=input()
ar=[]
al=[]
ans=[]
for i in range(N-1):
    if S[i]=="A":
        if S[i+1]=="C":
            al.append(i+1)
            ar.append(i+2)
for _ in range(Q):
    l,r=map(int,input().split())
    L=bisect.bisect_left(al,l)
    R=bisect.bisect_right(ar,r)
    ans.append(R-L)
for i in range(Q):
    print(ans[i])

Submission status: Accepted

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

Submission status: Accepted

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

for _ in range(Q):
    li, ri = map(int, input().split())
    ans = memo[ri-1] - memo[li-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()
    l = [0] * Q
    r = [0] * Q
    for i in range(Q):
        l[i], r[i] = map(int, input().split())

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

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math

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

S = list(input())

l = [0 for _ in range(Q)]
r = [0 for _ in range(Q)]
i = 0
while True:
  try:
    lr=list(map(int,input().split()))
    l[i] = lr[0]
    r[i] = lr[1]
    i+=1
  except:
    break

    
#print(S)
def create_list():
  MAXI = N
  
  #ac = [1 for _ in range(MAXI+1)]
  

  sn = [0 for _ in range(MAXI+1)]
  flag = 0
  judge = ['A','C']
  for i in range(1,MAXI+1):
    #print(str(i)+'+1 when '+S[i-1])
    if(S[i-1] == judge[flag]):
        flag+=1
        if(flag == 2):
            sn[i] = sn[i-1] + 1
            flag = 0
        else:
            sn[i] = sn[i-1]
    else:
        flag = 0
        if(S[i-1] == judge[flag]):
          flag += 1
        sn[i] = sn[i-1]
     
  return sn

base = create_list()
#print(base)
for i in range(Q):
  print( base[r[i]] - base[l[i]] )#sum(rnum)-sum(lnum) )

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:i+1] == 'AC'):l[i] = l[i-1] + 1
    else:l[i] = l[i-1]
L = [0] * q
R = [0] * q
for i in range(q):
    a,b = map(int,input().split())
    L[i] = a
    R[i] = b
for i in range(q):
    a = L[i]
    b = R[i]
    x = l[b-1] - l[a-1]
    print(x)

Submission status: Accepted

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

def main():
    N, Q = map(int, input().split())
    S = input()
    ans = [None] * N
    ans[0] = S.count('AC')
    for i in range(1,N):
        ans[i] = ans[i-1]
        if S[i-1:i+1] == 'AC':
            ans[i] -= 1

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect
n, q = map(int, input().split())
s = input()
ac=[]
for i in range(n):
  if s[i:i+2] == "AC":
    ac.append(i)

for i in range(q):
  l, r = map(int, input().split())
  acl=bisect.bisect_left(ac,l-1)
  acr=bisect.bisect_left(ac,r-1)
  print(acr-acl)

Submission status: Accepted

Solution code:
from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():

    N,Q=map(int,input().split())
    S=list(input())
    res=[0]*N

    temp=False
    for i in range(N):
        if S[i]=='A':
            temp=True
        elif temp==True and S[i]=='C':
            res[i-1]=1
            temp=False
        else: temp=False


    B = [0] + res
    # 累積和を格納したリスト．A[l:r]の総和はB[r] - B[l]
    B = list(accumulate(B))

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



resolve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n, q = map(int, input().split())
s = input()
t = [0] * -~n
for i in range(n):
    t[i + 1] = t[i] + (1 if s[i:i+2] == "AC" else 0)
for _ in range(q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])

Submission status: Accepted

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

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

A=[0]*(N)

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

for k in li:
    l=k[0]-1
    r=k[1]-1
    print(A[r]-A[l])

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
s = input()
"""ナイーブ
for i in range(q):
    l, r = map(int, input().split())
    print(s[l-1:r].count("AC"))
"""
# 前処理＋全探索
# 区間なので累積和を疑う
t = [0]*n
count = 0
for i in range(n-1):
    t[i] = count
    if s[i] + s[i+1] == "AC":
        count += 1
    t[i+1] = count
#print(t)
for i in range(q):
    l, r = map(int, input().split())
    ans = t[r-1] - t[l-1]
    print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

a = [0]*n
p = 0
for i in range(1,n):
    if s[i-1] == 'A' and s[i] == 'C':
        p += 1
    a[i] = p
ans = []
for i in range(q):
    ans.append(a[lr[i][1]-1]-a[lr[i][0]-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):
    if s[i:i+2]=="AC":
        c=1
    else:
        c=0

    t[i+1]=t[i]+c

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

Submission status: Accepted

Solution code:
# 13:45~
n, q = map(int, input().split())
s = input()

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

count = [0]*(n+1)

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


for i, query in enumerate(queries):
    l = query[0]
    r = query[1]
    print(count[r-1] - count[l-1])

Submission status: Accepted

Solution code:
# 13:45~
n, q = map(int, input().split())
s = input()

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

count = [0]*(n+1)
count[0] = 0
aFlag = False
for i, c in enumerate(s):
    count[i+1] = count[i]

    if c == 'C' and aFlag:
        count[i+1] = count[i] + 1

    if c == 'A':
        aFlag = True
    else:
        aFlag = False

for i, query in enumerate(queries):
    l = query[0]
    r = query[1]
    print(count[r] - count[l])

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
s = input()
lst = [0] * q
for i in range(q):
    l, r = map(int, input().split())
    lst[i] = (l, r)

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

for x in lst:
    print(cum[x[1]-1] - cum[x[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()
lr_list = []
for i in range(Q):
    l, r = lr()
    lr_list.append((l, r))

cnt = 0
ac_list = [0]
for i, (s1, s2) in enumerate(zip(S, S[1:])):
    if s1 + s2 == 'AC':
        cnt += 1
        ac_list.append(cnt)
    else:
        ac_list.append(cnt)

for (l, r) in lr_list:
    print(ac_list[r - 1] - ac_list[l - 1])

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = str(input())
L = [0]  # ruisekiwa
for i in range(1, len(S)):
    if S[i-1:i+1] == 'AC':
        L.append(L[i-1]+1)
    else:
        L.append(L[i-1])

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

Submission status: Accepted

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

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

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

for x in ans:
   print(x)

Submission status: Accepted

Solution code:
from bisect import bisect_left

n, q = [int(x) for x in input().split()]
s = input()

index_list = []
i = 0
while i < n - 1:
    if s[i] == "A" and s[i + 1] == "C":
        index_list.append(i + 1)
        i += 2
    else:
        i += 1

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

Submission status: Accepted

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

for i in range(0,len(s)):
    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])

Submission status: Accepted

Solution code:
from itertools import accumulate
n, q = [int(i) for i in input().split()]
s = input()
m = [0] * (len(s) - 1)
for i in range(len(m)):
    if s[i:i+2] == "AC": m[i] = 1
a = [0] + list(accumulate(m))

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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

lis = [0]*N

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

lis_acc = list(accumulate(lis))

for _ in range(Q):
	l, r = MAP()
	print(lis_acc[r-1] - lis_acc[l-1])

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, Q = MAP()
S = input()
lr = [LIST() for _ in range(Q)]

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

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

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