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:
def solve():
    n, q = map(int, input().split())
    s = input()
    lrs = list(list(map(int, input().split())) for _ in range(q))
    # ans = [s[l - 1:r].count("AC") for l, r in lrs]
    c = [0] * n
    for i in range(1, n):
        c[i] = c[i - 1]
        if s[i - 1] == "A" and s[i] == "C":
            c[i] += 1
    ans = [c[r - 1] - c[l - 1] for l, r in lrs]
    print(*ans, sep="\n")


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import math
from itertools import accumulate


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

ans = []

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

# print(ans)

L = [0] * Q
R = [0] * Q
for i in range(Q):
    L[i], R[i] = list(map(int, input().split()))

ans = list(accumulate([0] + ans))
# print(ans)
for i in range(Q):
    # print(i, R[i], L[i])
    print(ans[R[i] - 1] - ans[L[i] - 1])

Submission status: Accepted

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

l = [0]
ll = []
count = 0

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


for i in range(q):
    array = list(map(int, input().split()))
    ll.append(array)

for i in range(q):
    print(l[ll[i][1]-1] - l[ll[i][0]-1])

Submission status: Accepted

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

for 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()) # input:"2 2"
s = str(input())
#どこにACがあるかを計算しておいて、あとからL,Rでsplitする
ans=[0]*(n+1)
for i in range(n):
  if s[i : i + 2] == 'AC': #if s[i]=='A' and s[i+1]=='C':だとerror
    ans[i+1]=ans[i]+1
  else:
    ans[i+1]=ans[i]
#ti =「S の 1 文字目から i 文字目までに出現する a の数」として数列 t = {t0, t1, . . . , tN } を考えると、問 i の答えは tri−1 − tli−1
for i in range(q):
  l, r = map(int, input().split()) #ループ内で一行ずつ読み込む
  print(ans[r-1]-ans[l-1])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
Mod = 1000000007



def main(): #startline--------------------------------------------
    N,Q = map(int,input().split())
    S = input()
    LR = [list(map(int,input().split())) for i in range(Q)]
    accum = [0]
    keep = "start"
    S += "D"

    for i in S:
        if i == "C":
            if keep == "A":
                accum.append(accum[-1]+1)
                keep = ""
            else:
                keep = ""
                accum.append(accum[-1])
        elif i == "A":
            keep = "A"
            accum.append(accum[-1])
        else:
            keep = ""
            accum.append(accum[-1])
    accum = accum[1:]
    for i in range(Q):
        print(accum[LR[i][1]-1]-accum[LR[i][0]-1])

if __name__ == "__main__":
    main() #endline===============================================




def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n < 2 is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))):
        if prime[i] == 1:
            for j in range(2*i,n):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n):
        if prime[i] == 1:
            res.append(i)
    return res

class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py

    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)

Submission status: Accepted

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

Submission status: Accepted

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

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

for i in range(1, len(s)):
    if s[i-1] + s[i] == 'AC':
        t[i] = t[i-1] + 1
    else:
        t[i] = t[i-1]

#print(t)

for i in range(q):
    left = l[i] - 1
    right = r[i] - 1
    # print(left)
    # print(right)
    print(t[right] - t[left])

Submission status: Accepted

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

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
input = sys.stdin.readline
n,q=map(int,input().split())
s=str(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 j in range(q):
        l,r=map(int,input().split())
        print(t[r-1]-t[l-1])

Submission status: Accepted

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

nums = [0] * N
count = 0
for i in range(len(S)-1):
    nums[i] = count
    if S[i] == "A" and S[i+1] == "C":
        count += 1
nums[-1] = count

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
from itertools import accumulate

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

S = ['0'] + S
check = [0] * N

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

check = list(accumulate(check))
for left, right in zip(L, R):
    print(check[right-1] - check[left-1])

Submission status: Accepted

Solution code:

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

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

for i in li:
    print(pos[i[1]-1]-pos[i[0]-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:

n,q=map(int,input().split())
s=list(input())
a=[0]*n

for i in range(1,n):
  if s[i-1]=='A' and s[i]=='C':
    a[i]=a[i-1]+1
  else:
    a[i]=a[i-1]
    
for i in range(q):
  sita,ue=map(int,input().split())
  if sita==1:
    print(a[ue-1])
  elif s[sita-2]=='A' and s[sita-1]=='C':
    print(a[ue-1]-a[sita-2]-1)
  else:
    print(a[ue-1]-a[sita-2])

Submission status: Accepted

Solution code:
import bisect

n,q = [int(x) for x in input().split()]
s = input()
questions = [list(map(lambda x: int(x),input().split())) for x in range(q)]

index = 0
findIndexes = []
while(index != -1):
    index = s.find('AC',index)
    if index > -1:
        findIndexes.append(index+1)
        index += 1

for q in questions:
    left_index = bisect.bisect_left(findIndexes,q[0])
    right_index = bisect.bisect_right(findIndexes,q[1]-1)
    print(right_index-left_index)

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

Submission status: Accepted

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

for i in range(n):
  if i==0:
    continue
  if s[i-1]=="A" and s[i]=="C":
    cnt+=1  
  li[i]=cnt
    
for i in range(q):
  l,r=map(int,input().split())
  ans=li[r-1]-li[l-1]
  print(ans)

Submission status: Accepted

Solution code:
N,Q=map(int,input().split())
S=input()
cnt=[0]*N
for i in range(1,N):
    cnt[i]+=cnt[i-1]
    if S[i-1:i+1]=="AC": cnt[i]+=1
for j 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()
X = [list(map(int, input().split()))for _ in range(Q)]

a =[0]*N
for i in range(1,N):
    if S[i] =="C" and S[i-1] =="A":
        a[i] = a[i-1]+1
    else:
        a[i] = a[i-1]
# print(a)
for i in range(Q):
    print(a[X[i][1]-1]-a[X[i][0]-1])

Submission status: Accepted

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

cnt_list = [0] * len(S)
i = 0
for i in range(1, len(S)):

    cnt_list[i] = cnt_list[i - 1]
    if S[i - 1] == 'A' and S[i] == 'C':
        cnt_list[i] += 1

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

Submission status: Accepted

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

a = [0] * N

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


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

Submission status: Accepted

Solution code:

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

cnt = [False] * n

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

acc = [0] * n
now = 0

for i in range(n):
    if cnt[i]:
        now += 1
    acc[i] = now


for _ in range(q):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    cnt_b = acc[b]
    cnt_a = acc[a] if a >= 0 else 0
    print(cnt_b - cnt_a)

Submission status: Accepted

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


def get_num():
    return int(input())


def get_nums(n):
    res = [0 for _ in range(n)]
    for i in range(n):
        res[i] = int(input())
    return res


def get_numbers():
    return map(int, input().split())

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

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

ans = list()
for i in range(q):
    l, r = get_numbers()
    ans.append(dp[r] - dp[l])

for a in ans:
    print(a)

Submission status: Accepted

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

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

for l, r in ran:
    print(table[r-1]  - table[l - 1] )

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = input()
l = [0] * Q
r = [0] * Q
for i in range(Q):
    l[i], r[i] = map(int, input().split())

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

for i in range(Q):
    ans = dp[r[i]-1] - dp[l[i]-1]
    print(ans)

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
s=input()
i=1
dp=[0 for i in range (n)]
while(i<n):
	if(s[i-1]=='A' and s[i]=='C'):
		dp[i]=dp[i-1]+1
	else:
		dp[i]=dp[i-1]
	i+=1
i=0
# print(dp)

while(i<q):
	l,r=map(int,input().split())
	print(dp[r-1]-dp[l-1])
	i+=1

Submission status: Accepted

Solution code:
from itertools import accumulate
n,q = list(map(int,input().split()))
s = input()
A = [list(map(int,input().split())) for i in range(q)]

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

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


for a in A:
    print(flg2[a[1]-1] - flg2[a[0]-1])

Submission status: Accepted

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

collection = [0] * n
temp = 0

for i in range(1, n):
    if string[i] == 'C' and string[i-1] == 'A':
        temp += 1
    collection[i] = temp

for i in range(q):
    start, end = [int(i) for i in input().split()]
    print(collection[end-1] - collection[start-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
sn,qn=map(int,input().split())
s=input()
x=list(list(map(int,input().split())) for _ in range(qn))

s2=[0]*sn

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

for i in range(qn):
	res=s2[x[i][1]-1]-s2[x[i][0]-1]
	print(res)

Submission status: Accepted

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

lr = []
for i in range(q):
    lr.append([int(_) for _ in input().split()])
number_ac = [0]
state = 0
for i in range(1, len(s)):
    if (s[i - 1] == "A" and s[i] == "C"):
        state += 1
    number_ac.append(state)

def ans(l, r):
    if l == 0:
        res = number_ac[r]
    else:
        res = number_ac[r] - number_ac[l - 1]
        if (s[l-1] == "A" and s[l] == "C"):
            res -= 1
    return res

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

Submission status: Accepted

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

cnt = [0]*(n)

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

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

Submission status: Accepted

Solution code:
from copy import deepcopy
from sys import exit,setrecursionlimit
import math
from collections import defaultdict,Counter,deque
from fractions import Fraction as frac

setrecursionlimit(1000000)


def main():
	n,q = map(int,input().split())
	s = input()
	lr = []
	for i in range(q):
		lr.append(list(map(int,input().split())))
		lr[-1][0] -= 1
		lr[-1][1] -= 1
	ac = [0, (1 if s[0]+s[1]=='AC' else 0)]
	for i in range(1,n-1):
		ac.append((ac[-1]+1) if s[i]+s[i+1]=='AC' else ac[-1])
	for i in lr:
		print(ac[i[1]]-ac[i[0]])

def zip(a):
	mae = a[0]
	ziparray = [mae]
	for i in range(1,len(a)):
		if(mae != a[i]):
			ziparray.append(a[i])
			mae = a[i]
	return ziparray

def is_prime(n):
	if n < 2: return False

	for k in range(2, int(math.sqrt(n)) + 1):
		if n % k == 0:
			return False

	return True

def list_replace(n,f,t):
	return [t if i==f else i for i in n]

def base_10_to_n(X, n):
	X_dumy = X
	out = ''
	while X_dumy>0:
		out = str(X_dumy%n)+out
		X_dumy = int(X_dumy/n)
	if(out == ''): return '0'
	return out

def gcd(l):
	x = l.pop()
	y = l.pop()
	while(x%y!=0):
		z = x%y
		x = y
		y = z
	l.append(min(x,y))
	return gcd(l) if len(l) > 1 else l[0]

class Queue():
	def __init__(self):
		self.q = deque([])
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.popleft()
	def size(self):
		return len(self.q)
	def debug(self):
		return self.q

class Stack():
	def __init__(self):
		self.q = []
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.pop()
	def size(self):
		return len(self.q)
	def debug(self):
		return self.q

class graph():
	def __init__(self):
		self.graph = defaultdict(list)
	def addnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].append(t)
		self.graph[t].append(f)
	def rmnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].remove(t)
		self.graph[t].remove(f)
	def linked(self,f):
		return self.graph[f]

class dgraph():
	def __init__(self):
		self.graph = defaultdict(set)
	def addnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].append(t)
	def rmnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].remove(t)
	def linked(self,f):
		return self.graph[f]

main()

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right

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

AC = []
a = False
for i, s in enumerate(S):
    if s == 'A':
        a = True
        continue
    if a and s == 'C':
        AC.append(i-1)
    a = False

for l, r in LR:
    left = bisect_left(AC, l-1)
    right = bisect_right(AC, r-2)
    print(right-left)

Submission status: Accepted

Solution code:
"""
# 標準入力取得
## 文字列
 = sys.stdin.readline().rstrip()
 = list(sys.stdin.readline().rstrip())

## 数値
 = int(sys.stdin.readline())
 = map(int, sys.stdin.readline().split())
 = list(map(int, sys.stdin.readline().split()))
 = [list(map(int,list(sys.stdin.readline().split()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

# 0埋め, 小数点出力桁指定時のときの出力
a = 100
b = 0.987654321
print("{0:06d}-{1:6f}".format(a,b))
000100-0.987654

# 文字列をリストに格納
char_list = list("abcd") # ["a","b","c","d"]
"""

import math
import sys
import itertools
import queue
from fractions import gcd
from itertools import accumulate

def lcm(a, b):
    return a * b // gcd(a, b)

mod = 1000000007

if __name__ == "__main__":
    N,Q= map(int, sys.stdin.readline().split())
    S = sys.stdin.readline().rstrip()
    l= [list(map(int,list(sys.stdin.readline().split()))) for i in range(Q)]
    # 累積和
    flg = []
    for i in range(N-1):
        tmp_S = S[i:i+2] #２文字ずつ
        if tmp_S == "AC":
            flg.append(1)
        else:
            flg.append(0)

    flg2 = [0] + flg
    flg2 = list(accumulate(flg2)) #accumurateで累積和[0, 1, 1, 2, 2, 2, 3, 3]

    for e in l:
        print(flg2[e[1]-1] - flg2[e[0]-1]) #累積和から順番で引っ張ってくる

Submission status: Accepted

Solution code:
from bisect import bisect_left
n,q=map(int,input().split())
s=input().replace("AC","XY")
ref=[i for i,j in enumerate(s) if j=="X"]
for _ in range(q):
	a,b=map(int,input().split())
	a-=1;b-=1
	print(bisect_left(ref,b)-bisect_left(ref,a))

Submission status: Accepted

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
#ABC122C
import sys
import copy
tmp = input().split()
hoge = list(map(lambda a: int(a), tmp))
n=hoge[0]
q=hoge[1]

s = input()

ans=[]
sum=0
#print(s)

for j in range(0,n-1):
	if(s[j]=="A")and(s[j+1]=="C"):
		sum+=1
	ans.append(sum)
	#print(s[j])
ans.append(sum)
ans.append(0)
#ans[n-1]=sum
#print(ans)
#print(ans)

l=[]
r=[]
sum=0
for i in range(0,q):
	tmp = input().split()
	hoge = list(map(lambda a: int(a), tmp))

	print(ans[hoge[1]-2]-ans[hoge[0]-2])

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
# GET AX
N, Q = map(int, input().split())
S = str(input())
lr = [list(map(int, input().split())) for _ in range(Q)]
#N, Q = 8, 3
#S = 'ACACTACG'
#lr = [[3,7],[2,3],[1,8]]

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

for q in range(Q):
	l, r = lr[q]
	nl = a[l-1]
	nr = a[r-1]
	print(nr - nl)

Submission status: Accepted

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

S = input()

a = [0]*len(S)
nac = 0
for i in range(1, len(S)):
    if S[i-1] == "A" and S[i] =="C":
        nac += 1
    a[i] = nac

for _ in range(Q):
    l,r = (int(x) for x in input().split())
    if l == 0:
        lac = 0
    else:
        lac = a[l-1]
    print(a[r-1]-a[l-1])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

t = [0] * (n+1)

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

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

Submission status: Accepted

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

idx = [0] * n

# idx = [idx[i-1]+int(s[i-1:i+1] == "AC") for i in range(1, n)]
for i in range(1,n):
    idx[i] = idx[i-1] + (s[i-1:i+1] == "AC")


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

Submission status: Accepted

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

left = [0 for _ in range(N+1)]

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

for _ in range(Q):
    l, r = map(int, input().split())

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

Submission status: Accepted

Solution code:
a, b = map(int, input().split())
c = input()
d = [0] * a
e = 0
for i in range(a):
    if c[i] == "C" and c[i-1] == "A":
        e += 1
    d[i] = e
for i in range(b):
    f, g = map(int, input().split())
    print(d[g-1] - d[f-1])

Submission status: Accepted

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

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

Submission status: Accepted

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

ACindex = []
index = 0
while (True):
    index = S.find("AC", index)
    if index == -1:
        break
    ACindex.append(index)
    index += 2
# print(ACindex)

ACs = []
num_of_AC = 0
pre = -1
for i in ACindex:
    ACs += [num_of_AC]*(i-pre)
    num_of_AC += 1
    pre = i

ACs += [num_of_AC]*(N-1-pre)

for i in range(Q):
    L, R = map(int, input().split())
    L -= 1
    R -= 1
    count = ACs[R]-ACs[L]
    print(count)
# print(ACs)

Submission status: Accepted

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

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

for i in range(q):
    l, r = lr[i]
    ans = arr[r-1] - arr[l-1]
    print(ans)

Submission status: Accepted

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

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

cnt = [0]*n
for i in range(1, n):
    cnt[i] += cnt[i-1] + ac[i]
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()

X = [list(map(int,input().split())) for _ in range(Q)]

count = [0]*len(S)
for i in range(1,len(S)):
	if S[i-1] == "A" and S[i] == "C":
		count[i] = count[i-1] + 1
	else:
		count[i] = count[i-1]
        
for j in range(Q):
	ans = count[X[j][1]-1]-count[X[j][0]-1]
	print(ans)

Submission status: Accepted

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

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


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

Submission status: Accepted

Solution code:
# ABC 122 C

import bisect

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

S = input()

indexes = []  # 'AC' の開始位置

startPos = 0

while True:
    index = S.find('AC', startPos)
    if index != -1:
        indexes.append(index)
        startPos = index + 2
    else:
        break

for i in range(Q):
    l, r = map(int, input().split())
    i = bisect.bisect_left(indexes, l-1)
    j = bisect.bisect_left(indexes, r-1)
    print(j-i)

Submission status: Accepted

Solution code:
from bisect import bisect_right, bisect_left
N, Q = map(int, input().split())
S = input()
ac = []
for i in range(N-1):
  if S[i:i+2] == "AC":
    ac.append(i)
for i in range(Q):
  l, r = map(int, input().split())
  l -= 1
  r -= 1
  print(bisect_right(ac, r-1) - bisect_left(ac, l))

Submission status: Accepted

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

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

Submission status: Accepted

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