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:
# -*- coding: utf-8 -*-
"""
Created on Sun Mar 24 20:50:58 2019

@author: Yamazaki Kenichi
"""

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

res = [0]
flg = False
for c in S:
    if flg:
        if c == 'C':
            res.append(res[-1]+1)
            flg = False
        elif c == 'A':
            res.append(res[-1])
        else:
            res.append(res[-1])
            flg = False
    elif c == 'A':
        res.append(res[-1])
        flg = True
    else:
        res.append(res[-1])
#    print(c,res)
for a in A:
    print(res[a[1]]-res[a[0]])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,Q = map(int,input().split())
S = input()
ACnum = [0]
for i in range(1,N):
    if "AC" == S[i-1:i+1]:
        ACnum.append(ACnum[i-1] + 1)
    else:
        ACnum.append(ACnum[i-1])
lr = []
for i in range(Q):
    lr.append(list(map(int,input().split())))

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

T = [0]*N
a_flag = False
ac_num = 0
for i in range(N):
    if S[i] == 'A':
        a_flag = True
    elif a_flag and S[i] == 'C':
        ac_num += 1
        a_flag = False
    else:
        a_flag = False
    T[i] = ac_num

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from itertools import chain, accumulate
from functools import reduce
from collections import OrderedDict, Counter, deque
import operator

IS = lambda: int(input())
IA = lambda: [int(x) for x in input().split()]
IM = lambda N: [IA() for _ in range(N)]

N, Q = IA()
S = input()
LR = IM(Q)

a = [0] * (N+5)
l = 0
while True:
    p = S[l:].find('AC')
    if p == -1: break
    a[l + p + 1] = 1
    l += p + 2
a = list(accumulate(a))

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

Submission status: Accepted

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

  count_list = [0] * N
  A_found = False
  count = 0

  for i, s in enumerate(S):
    if A_found and s == 'C':
      count += 1
      A_found = False
    else:
      A_found = s == 'A'
    count_list[i] = count

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

solve()

Submission status: Accepted

Solution code:
from itertools import accumulate as ac
n,q=map(int,input().split())
s=input()
d=[0]*(n+1)
for i in range(1,n):
    if s[i-1]+s[i]=="AC":
        d[i+1]+=1
d=list(ac(d))
for i in range(q):
    l,r=map(int,input().split())
    print(d[r]-d[l])

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
S = input()
a = [0]
ans = 0
for i in range(1,N):
  if S[i - 1] == 'A' and S[i] == 'C':
    a.append(a[-1] + 1)
  else:
    a.append(a[-1])

for i in range(M):
  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()
cnts = [0]

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

# for l in range(1, n+1):
#   for r in range(l+1, n+1):
#     ll = l-1
#     rr = r-1
#     cnt = cnts[rr] - cnts[ll]
#     subs = s[ll:rr+1]
#     print('{2}: {0} ACs found in {1}'.format(cnt, subs, (l,r)))
for qq in range(q):
  l, r = map(int, input().split())
  cnt = cnts[r-1] - cnts[l-1]
  print(cnt)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
S = input()
q = [list(map(int, input().split())) for _ in range(Q)]
f = [0 for _ in range(N)]
for i in range(2, N + 1):
    if S[i - 2:i] == "AC":
        f[i - 1] += f[i - 2] + 1
    else:
        f[i - 1] += f[i - 2]
for i in range(Q):
    print(f[q[i][1] - 1] - f[q[i][0] - 1])

Submission status: Accepted

Solution code:
def get_ac(N: int, Q: int, S: str, queries: list)->list:
    before = ''
    cum = [0] * (N+1)
    for i, c in enumerate(S):
        cum[i+1] = cum[i]
        if before + c == 'AC':
            cum[i+1] += 1
        before = c

    # print(cum)

    res = []
    for l, r in queries:
        res.append(cum[r] - cum[l])

    return res


if __name__ == "__main__":
    Q = 0
    N, Q = map(int, input().split())
    S = input()
    queries = [tuple(int(s) for s in input().split()) for _ in range(Q)]
    ans = get_ac(N, Q, S, queries)

    for a in ans:
        print(a)

Submission status: Accepted

Solution code:
import sys


fin = sys.stdin.readline
N, Q = map(int, fin().split())
S = fin().rstrip("\n")
queries = tuple(tuple(int(elem) - 1 for elem in fin().split()) for _ in range(Q))

# [0, i]
prefix_num_ACs = [0] * len(S)
for i, char in enumerate(S[1:], start=1):
    if char == "C" and S[i - 1] == "A":
        prefix_num_ACs[i] = prefix_num_ACs[i - 1] + 1
    else:
        prefix_num_ACs[i] = prefix_num_ACs[i - 1]
# print(prefix_num_ACs)
for l, r in queries:
    num_ACs = prefix_num_ACs[r] - prefix_num_ACs[l]
    print(num_ACs)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from bisect import bisect, bisect_left
def inpl(): return list(map(int, input().split()))

N, Q = inpl()
S = input()
D = [i for i in range(N-1) if S[i:i+2] == "AC"]
for _ in range(Q):
    l, r = inpl()
    a = bisect_left(D, l-1)
    b = bisect(D, r-2)
    print(b-a)

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
s = input()
lr = []
for i in range(q):#h:高さ
    lr.append([int(m) for m in input().split()])
accntli = [0] * len(s)
accnt = 0
for i in range(1, len(s)):
    accntli[i] = accnt
    if s[i - 1] == "A" and s[i] == "C":
        accnt += 1
        accntli[i] = accnt
ansli = [0] * q
for i in range(q):
    ansli[i] = accntli[lr[i][1] - 1] - accntli[lr[i][0] - 1]
for i in range(q):
    print(ansli[i])

Submission status: Accepted

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

Submission status: Accepted

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

ac_count = [0 for i in range(N+1)]
ac_flag = [False for i in range(N+1)]
acc=0
for i in range(1,N):
    if S[i]=="C" and S[i-1]=="A":
        acc+=1
        ac_flag[i]=True
    ac_count[i+1]=acc

ans = []
for i in range(Q):
    l,r = list(map(int,input().split()))
    count=ac_count[r]-ac_count[l-1]
    if ac_flag[l-1]:
        count-=1
       
    ans.append(count)

for a in ans:
    print(a)

Submission status: Accepted

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

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

for i in range(n-1):
    memo[i+1] += memo[i]

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

Submission status: Accepted

Solution code:
N,Q = map(int,input().split())
S = input()
S += 'J'
L = []
for i in range(Q):
  L.append(list(map(int,input().split())))
cnt = [0]*(N+1)
for i in range(N):
  if S[i] == 'A' and S[i+1] == 'C':
    cnt[i+1] = 1
for i in range(1,N+1):
  cnt[i] += cnt[i-1]
for j in range(Q):
  print(cnt[L[j][1]-1]-cnt[L[j][0]-1])

Submission status: Accepted

Solution code:
N,Q = [int(i) for i in input().split()]
S=input()
lr = [[int(j)-1 for j in input().split()] for i in range(Q)]

imos = [0 for i in range(N)]
for i in range(N-1):
    if S[i]=='A' and S[i+1]=='C':
        imos[i]=1
for i in range(N-1):
    imos[i+1]+=imos[i]
for l,r in lr:
    res = imos[r]
    if l>0:
        res-=imos[l-1]
    if S[r]=='A' and r<N-1 and S[r+1]=='C':
        res-=1
    print(res)

Submission status: Accepted

Solution code:
#! usr/bin/env python
# -*- coding: utf-8 -*-

from collections import deque
import heapq
import math
import bisect


def main():
    N, Q = map(int, input().split())
    S = input()
    CNT = [0] * (N+1)

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,q=map(int,input().split(' '))
x=list(input())
d=[0 for i in range(n)]
for i in range(1,n):
    if x[i]=="C" and x[i-1]=="A":
        d[i]=d[i-1]+1
    else:
        d[i]=d[i-1]
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 = [int(i) for i in input().split()]
S = input()
dp = [0] * N
for i in range(1, N):
    if S[i-1:i+1] == 'AC':
        dp[i] = dp[i - 1] + 1
    else:
        dp[i] = dp[i - 1]
for _ in range(Q):
    l, r = [int(i) - 1 for i in input().split()]
    print(dp[r] - dp[l])

Submission status: Accepted

Solution code:
(N,M) = (int(s) for s in input().split(" "))
s = input()
is_ac = [False,False]
total = [0,0]
for i in range(1,len(s)):
	if s[i-1:i+1] == "AC":
		total.append(total[-1]+1)
		is_ac.append(True)
	else:
		total.append(total[-1])
		is_ac.append(False)
for i in range(M):
	(l,r) = (int(t) for t in input().split(" "))
	ans = total[r] - total[l-1]
	if is_ac[l]:
		ans-=1
	print(ans)

Submission status: Accepted

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

aflag=0
count=0
arr=[]
for num,i in enumerate(S):
    if i == "A":
        aflag=1
    elif aflag==1 and i == "C":
        #arr.append(num-1)
        count+=1
        aflag=0
    else:
        aflag=0
    arr.append(count)

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

Submission status: Accepted

Solution code:
import io, sys, atexit, os

import math as ma
from sys import exit
from decimal import Decimal as dec
from itertools import permutations


def li ():
	return list (map (int, input ().split ()))


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


def nu ():
	return int (input ())


def find_gcd ( x, y ):
	while (y):
		x, y = y, x % y
	return x


mm = 1000000007



def solve ():
	t = 1
	for it in range (t):
		n,q=num()
		s=input()
		ff=[0]*n
		for i in range(n-1):
			if(s[i]=="A" and s[i+1]=="C"):
				ff[i]=1
		for i in range(1,n):
			ff[i]=ff[i-1]+ff[i]
		for i in range(q):
			l,r=num()
			l-=1
			r-=1
			if(s[r]=="A"):
				r-=1
			if(l==0):
				print(ff[r])
			else:
				print(ff[r]-ff[l-1])







if __name__ == "__main__":
	solve ()

Submission status: Accepted

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

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

# そのままカウントしたのでは、O(Q(r-l))の時間がかかる
# Sと同じ長さ(<10^5)の配列ACを作って、Sの添え字に対応するAC数をカウントし、
# AC[r]-AC[l]で差分を取れば求める部分文字列のACはカウントできそう。

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

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

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

Submission status: Accepted

Solution code:
def main():
    N, Q = [int(q) for q in input().split()]
    S = input()
    lr = [
        [int(q) - 1 for q in input().split()]
        for _ in range(Q)
    ]

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, Q = map(int,input().split())
S = input()
L = [0 for k in range(N)]
t = 0
for k in range(N-1):
    if S[k:k+2] == "AC":
        t += 1
    L[k+1] = t

for k 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 = list(input())
preC = [0]
for i in range(1, len(S)):
    if S[i] == 'C' and S[i-1] == 'A':
        preC += [preC[-1] + 1]
    else:
        preC += [preC[-1]]

for q in range(Q):
    l, r= map(int,input().split())
    total = preC[r - 1]
    if l == 1:
        print(total)
    else:
        total -= preC[l - 2]
        if S[l - 1] == 'C' and S[l - 2] == 'A':
            total -= 1
        print(total)        
        

'''
8 3
ACACTACG
1 3
4 7
1 8     
        
'''

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, Q = map( int, input().split())
S = input()
AAT = [0]*(N+1)
ATT = [0]*(N+1)
now = 0
ac = 0
for i in range(N):
    if S[i] == 'A':
        now = 1
    elif S[i] == 'C':
        if now == 1:
            ac += 1
        now = 0
    else:
        now = 0
    ATT[i] = ac
    if i == 0:
        continue
    AAT[i-1] = ac
AAT[N-1] = ac
for _ in range(Q):
    l, r = map( int, input().split())
    if l == 1:
        print(ATT[r-1])
    else:
        print( ATT[r-1] - AAT[l-2])

Submission status: Accepted

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

acdet = [0] * N

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

acdet_flag = [0] * N
for i in range(N):
    if acdet[i] == 2:
        acdet_flag[i] = 1

ruiseki = [0]
for i in range(N):
    ruiseki.append( ruiseki[-1] + acdet_flag[i] )

for l,r in LR:
    # l,r = l-1, r-1
    print( ruiseki[ r] - ruiseki[l] )
    # print("ruiseki[r:", r, "], l-1: ", l-1)
    # print(ruiseki)

Submission status: Accepted

Solution code:
n, q = [int(i) for i in input().split()]
s = input()
l_list = []
r_list = []
for i in range(q):
    l, r = [int(i) for i in input().split()]
    l_list.append(l)
    r_list.append(r)

ac_map = [0 for i in range(n+1)]
for i in range(1, n+1):
    if s[i-1:i+1] == "AC":
        ac_map[i] = ac_map[i-1] +1
    else:
        ac_map[i] = ac_map[i-1]
for i in range(q):
    ans = ac_map[r_list[i]-1] - ac_map[l_list[i]-1]
    print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
n,q = map(int, input().split())
s = input()
b = [0] * len(s)
c = 0
lr = [list(map(int, input().split())) for i in range(q)]
for i,j in enumerate(s):
  if c == 0:
    if j == "A":
      c += 1
  elif c == 1:
    if j == "A":
      continue
    elif j == "C":
      b[i] += 1
      c = 0
    else:
      c = 0
cumsum = list(accumulate(b))
for i in lr:
  print(cumsum[i[1]-1]-cumsum[i[0]-1])

Submission status: Accepted

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

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

for i in range(q):
  print(ruiseki[info[i][1]]-ruiseki[info[i][0]])

Submission status: Accepted

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

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

cs = [0] + cs

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

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = input()
isA = (S[0] == "A")
ruiseki = [0]
for s in S[1:]:
  if isA:
    if s == "C":
      ruiseki.append(ruiseki[-1]+1)
    else:
      ruiseki.append(ruiseki[-1])
  else:
    ruiseki.append(ruiseki[-1])
  isA = (s == "A")
for _ in range(Q):
  l, r = map(int, input().split())
  print(ruiseki[r-1]-ruiseki[l-1])

Submission status: Accepted

Solution code:
def solve(N, Q, S, LRs):
    Ts = [0 for _ in range(N)]
    tans = 0
    for i, (s1, s2) in enumerate(zip(S, S[1:])):
        if s1 == "A" and s2 == "C":
            tans += 1
        Ts[i + 1] = tans

    ans = []
    for l, r in LRs:
        ans.append(Ts[r - 1] - Ts[l - 1])
    return "\n".join(str(a) for a in ans)


if __name__ == "__main__":
    N, Q = tuple(map(int, input().split(" ")))
    S = input()
    LRs = [tuple(map(int, input().split(" "))) for __ in range(Q)]
    print(solve(N, Q, S, LRs))

Submission status: Accepted

Solution code:
def int_raw():
    return int(raw_input())

def ss_raw():
    return raw_input().split()

def ints_raw():
    return map(int,ss_raw())

INF = 1<<29

def make1d_arr(n,val=INF):
    return [val for i in xrange(n)]

def make2d_arr(w,h,val =INF):
    return [[val for i in xrange(w)]for i in xrange(h)]


N,Q = ints_raw()
S = raw_input()
target = "AC"

table = [0]*N
 
for i in xrange(1,len(S)):
    if S[i-1:i+1] == target:
        table[i]=table[i-1]+1
    else:
        table[i]=table[i-1]

for i in xrange(Q):
    l, r = ints_raw()
    print table[r-1]-table[l-1]

Submission status: Accepted

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

numAC = [0]
for i in range(1, N):
  numAC.append(numAC[-1] + int(S[i-1:i+1] == 'AC'))

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

Submission status: Accepted

Solution code:
import collections as c
ip = lambda : map(int, input().split())

#################
N,Q = ip()
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]


for i in range(Q):
    ql,qr = ip()
    ql -= 1
    qr -= 1
    print(l[qr] - l[ql])

#d = {'A':'T','T':'A','C':'G','G':'C'}

Submission status: Accepted

Solution code:
N,Q = map(int,input().split())
S = input()
cumulative = []
value = 0
flagA = False
for c in S:
    if flagA:
        if c=="C":
            value += 1
        if c=="A":
            flagA = True
        else:
            flagA = False
    else:
        if c=="A":
            flagA = True
        else:
            flagA = False
    cumulative.append(value)
for _ in range(Q):
    a,b=map(int,input().split())
    x=a-1
    y=b-1
    print(cumulative[y]-cumulative[x])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

from itertools import accumulate

def main():
    N, Q = LI()
    S = SI()
    LR = []
    for _ in range(Q):
        LR.append(LI_())

    AC = [0] * (N + 1)
    for i in range(N - 1):
        if S[i:i + 2] == 'AC':
            AC[i] = 1
    acc = [0] + list(accumulate(AC))
    for l, r in LR:
        print(acc[r] - acc[l])

    return 0

main()

Submission status: Accepted

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

from itertools import accumulate

prev = ""
acc = [0] * N
for i, s in enumerate(S):
    if s == "C" and prev == "A":
        acc[i] = 1
    prev = s


acc = list(accumulate(acc))
ans = []
for i in range(Q):
    l, r = items[i]

    ans.append(acc[r -1] - acc[l-1])
for a in ans:
    print(a)

Submission status: Accepted

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

s = input()


cnt = 0
d = [0]*len(s)
i = 0
while i<=(len(s)-2):
    if s[i]=='A' and s[i+1] == 'C':
        d[i] = cnt
        cnt += 1
        d[i+1] = cnt
        i+=2
    else:
        d[i]=cnt
        i+=1    
d[len(s)-1] = cnt
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()

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

Submission status: Accepted

Solution code:

def main():
    atgc = ["A", "T", "G", "C"]
    n, q = [int(i) for i in input().split()]
    s=input()
    lr = []
    for i in range(q):
        lr.append([int(i) for i in input().split()])

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

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

main()

Submission status: Accepted

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

import itertools
import collections
import bisect

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

    counter = [0] * N
    for i in range(N-1):
        if "{}{}".format(S[i], S[i+1]) == 'AC':
            counter[i+1] = counter[i] + 1
        else:
            counter[i + 1] = counter[i]
    # print(counter)

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
#def input():
#    return sys.stdin.readline()[:-1]

'''
n=int(input())
for i in range(n):
    a[i]=int(input())
    a[i],b[i]=map(int,input().split())
a=[int(x) for x in input().split()]
n,m=map(int,input.split())
from operator import itemgetter
a = [(1, "c", 1), (1, "b", 3), (2, "a", 0), (1, "a", 2)]
print(sorted(a))  # 0 番目の要素でソート、先頭の要素が同じなら 1 番目以降の要素も見る
print(sorted(a, key=itemgetter(0)))  # 0 番目の要素だけでソート
print(sorted(a, key=itemgetter(0, 2)))  # 0 番目と 2 番目の要素でソート
print(sorted(a, key=lambda x: x[0] * x[2]))  # 0 番目の要素 * 2 番目の要素でソート
print(sorted(a, reverse=True))  # 降順にソート
a.sort()  # 破壊的にソート、sorted() よりも高速
try: # エラーキャッチ list index out of range
    for i in range():
        k=b[i]
except IndexError as e:
    print(i)
'''

test_data1 = '''\
8 3
ACACTACG
3 7
2 3
1 8
'''

test_data2 = '''\
8 7
ACACAACG
1 2
1 4
1 3
2 4
2 7
1 7
1 8
'''

test_data3 = '''\

'''
td_num=1

def GetTestData(index):
    if index==1:
        return test_data1
    if index==2:
        return test_data2
    if index==3:
        return test_data3

if False:
    with open("../test.txt", mode='w') as f:
        f.write(GetTestData(td_num))
    with open("../test.txt") as f:
        # Start Input code ---------------------------------------
        
        n,q=map(int,f.readline().split())
        s=str(f.readline())
        l=[0]*q
        r=[0]*q
        for i in range(q):            
            l[i],r[i]=map(int,f.readline().split())
            
        # End Input code ---------------------------------------
else:
    for i in range(1):
        # Start Input code ---------------------------------------
        
        n,q=map(int,input().split())
        s=str(input())
        l=[0]*q
        r=[0]*q
        for i in range(q):            
            l[i],r[i]=map(int,input().split())
        # End Input code ---------------------------------------

pre=0
ac=[0]*n
for i in range(1,n):
    if s[i-1:i+1]=='AC':
        ac[i]=pre+1
    else:
        ac[i]=pre
    pre=ac[i]
    
#print('n,q,s,l,r=',n,q,s,l,r)
#print('ac',ac)
for i in range(q):
    print(ac[r[i]-1]-ac[l[i]-1])

Submission status: Accepted

Solution code:
import itertools
import numpy as np
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N,Q = IL()
s = S()
lr = [IL() for i in range(Q)]

dp = [0]*(len(s))

cnt = 0
for i in range(1,len(s)):
    if s[i] == "C":
        if s[i-1] == "A":
            cnt += 1
    dp[i] = cnt
for a,b in lr:
    print(dp[b-1]-dp[a-1])

Submission status: Accepted

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

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

SUM=[0]
for i in range(N):
    SUM.append(SUM[-1]+ANS[i])

for x,y in Query:
    if S[y-1:y+1]=="AC":
        y-=1
    print(SUM[y]-SUM[x-1])

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
from bisect import bisect_left
n,q=map(int,input().split())
S=input()
A=[]
for i in range(len(S)-1):
    if S[i]=='A' and S[i+1]=='C':
        A.append(i)
for _ in range(q):
    l,r=map(int,input().split())
    left=bisect_left(A,l-1)
    right=bisect_left(A,r-1)
    print(right-left)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


#A
def A():
    n = input()
    if n == "A":
        print("T")
    elif n == "C":
        print("G")
    elif n == "G":
        print("C")
    else:
        print("A")
    return

#B
def B():
    s = S()
    ans = 0
    n = len(s)
    for i in range(n):
        for j in range(i,n):
            f = 1
            for k in range(i,j+1):
                if s[k] not in list("AGCT"):f = 0
            if f:
                ans = max(ans,j+1-i)
    print(ans)
#C
def C():
    n,q = LI()
    s = S()
    f = [0 for i in range(n)]
    for i in range(n-1):
        if s[i:i+2] == ["A","C"]:
            f[i+1] += 1
    for i in range(n-1):
        f[i+1] += f[i]
    f.insert(0,0)
    for i in range(q):
        l,r = LI()
        print(f[r]-f[l])
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    C()

Submission status: Accepted

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

for i in range(N-1):
    if s[i]=="A" and s[i+1]=="C":
        cnt_ac[i+1] = 1
for i in range(1, N):
    cnt_ac[i] += cnt_ac[i-1]
# print(cnt_ac)

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
l = list(input())
ll = [0 for i in range(n)]

for i in range(n-1):
    if l[i] == "A" and l[i+1] == "C":
        ll[i+1] += ll[i] + 1
    else:
        ll[i+1] += ll[i]
for i in range(m):
    a,b = map(int,input().split())
    k = ll[b-1] - ll[a-1]
    print(k)