Problem:


Score : 300 points

Problem Statement

You are given a string S of length N consisting of A, C, G and T. Answer the following Q queries:

Query i (1 \leq i \leq Q): You will be given integers l_i and r_i (1 \leq l_i < r_i \leq N). Consider the substring of S starting at index l_i and ending at index r_i (both inclusive). In this string, how many times does AC occurs as a substring?

Notes

A substring of a string T is a string obtained by removing zero or more characters from the beginning and the end of T.

For example, the substrings of ATCODER include TCO, AT, CODER, ATCODER and  (the empty string), but not AC.

Constraints

2 \leq N \leq 10^5

1 \leq Q \leq 10^5

S is a string of length N.

Each character in S is A, C, G or T.

1 \leq l_i < r_i \leq N

Input

Input is given from Standard Input in the following format:

N Q
S
l_1 r_1
:
l_Q r_Q

Output

Print Q lines. The i-th line should contain the answer to the i-th query.

Sample Input 1

8 3
ACACTACG
3 7
2 3
1 8

Sample Output 1

2
0
3

Query 1: the substring of S starting at index 3 and ending at index 7 is ACTAC. In this string, AC occurs twice as a substring.

Query 2: the substring of S starting at index 2 and ending at index 3 is CA. In this string, AC occurs zero times as a substring.

Query 3: the substring of S starting at index 1 and ending at index 8 is ACACTACG. In this string, AC occurs three times as a substring.



Sample input:
8 3
ACACTACG
3 7
2 3
1 8


Sample output:
2
0
3

Submission status: Accepted

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

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

for i, j in lr:
    print(box[j-1] - box[i-1])

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] + (1 if S[i-1:i+1] == 'AC' else 0)

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

print('\n'.join(list(map(str, ans))))

Submission status: Accepted

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

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

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

print('\n'.join(list(map(str, ans))))

Submission status: Accepted

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

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

print('\n'.join(list(map(str, ans))))

Submission status: Accepted

Solution code:
from collections import deque
from collections import Counter
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
#pypyではscipy, numpyは使えない
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
#from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
#import numpy as np
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7

def main():
  n, q = map(int, readline().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])
  
  
if __name__ == '__main__':
  main()

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,q = LI()
s = input()
lr = [LI() for _ in range(q)]
lst = [0]*n
for i in range(n-1):
    if s[i:i+2] == 'AC':
        lst[i] = 1

lst = [0] + list(accumulate(lst))
for l,r in lr:
    print(lst[r-1] - lst[l-1])

Submission status: Accepted

Solution code:
n,q = map(int, input().split())
s = input()
af = False
AClist = [0 for i in range(10**5)]
for i,c in enumerate(s):
    if af:
        if c == 'C':
            AClist[i-1]+=1
            af = False
        elif c != 'A':
            af = False
    else:
        if c == 'A':
            af = True

a2=[0]
for i in AClist:a2.append(a2[-1]+i)
def SumArea(l, r):
    return a2[r]-a2[l]

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

Submission status: Accepted

Solution code:
def main():
    from itertools import accumulate
    import sys
    n, q, s, *lr = sys.stdin.read().split()
    *query, = map(int, lr)
    c = [1 if s[i] == 'C' and s[i - 1] == 'A' else 0 for i in range(int(n))]
    a = tuple(accumulate(c))
    ans = ''
    for i,j in zip(*[iter(query)]*2):
        ans += str(a[j-1]-a[i-1]) + '\n'
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from itertools import accumulate

    n, q, s, *lr = open(0).read().split()
    n = int(n)
    *u, = map(int, lr)
    c = [1 if s[i] == 'C' and s[i - 1] == 'A' else 0 for i in range(n)]
    a = tuple(accumulate(c))
    ans = ''
    for i,j in zip(*[iter(u)]*2):
        ans += str(a[j-1]-a[i-1]) + '\n'
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from itertools import accumulate

    n, q, s, *lr = open(0).read().split()
    n = int(n)
    *l, = map(int, lr[::2])
    *r, = map(int, lr[1::2])
    c = [1 if s[i] == 'C' and s[i - 1] == 'A' else 0 for i in range(n)]
    a = list(accumulate(c))
    ans = ''
    for i,j in zip(l,r):
        ans += str(a[j-1]-a[i-1]) + '\n'
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
from itertools import accumulate

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

S = input()

cum_sum = [0] * len(S)

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


cum_sum = list(accumulate(cum_sum))

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

    print(cum_sum[r]-cum_sum[l])

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
s=input()
idx=[0 for i in range(n+1)]

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

ans=[]
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()

a=[0]*(n+1)
for i in range(2,n+1):
    if s[i-2]=='A' and s[i-1]=='C':
        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]-a[l])

Submission status: Accepted

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

for j in range(0,N-1):
  if S[j]+S[j+1]=="AC":
    T.append(T[-1]+1)
  else:
    T.append(T[-1])
T.append(T[-1])
#print(T)

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

Submission status: Accepted

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

C = [0 for _ in range(N+1)]
#C[i]:i文字目までで"AC"が出てくる回数
for i in range(1,N):
    if S[i] == "A" and S[i+1] == "C":
        C[i+1] += 1

for i in range(N):
    C[i+1] += C[i]


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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,Q = [int(x) for x in input().split()]
s = input()
l = list(s)
rui = [0] * (N+1)
for i in range(2,len(l)+1):
    if l[i-2] == "A" and l[i-1] == "C":
        rui[i] = rui[i-1] + 1
    else:
        rui[i] = rui[i-1]
for i in range(Q):
    a,b = [int(x) for x in input().split()]
    print(rui[b]-rui[a])

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
s = input()
ac = [0 for _ in range(n+1)]
a = 0
for i in range(n):
    if s[i] == "C" and a:
        ac[i] = 1
    if s[i] == "A":
        a = 1
    else:
        a = 0
for i in range(n):
    ac[i+1] += 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:
import sys
from itertools import accumulate

readline = sys.stdin.readline
n, q = map(int, readline().split())
s = readline().rstrip()
ac = [False] * (n - 1)
for i, x in enumerate(zip(s, s[1:])):
    if x == ('A', 'C'):
        ac[i] = True
ac = [0] + list(accumulate(ac))
for _ in range(q):
    l, r = map(int, readline().split())
    print(ac[r-1] - ac[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())

cs = [0]*(N+1)
for i in range(N-1):
    if(S[i] == 'A' and S[i+1] == 'C'):
        cs[i+2] = cs[i+1] + 1
    else:
        cs[i+2] = cs[i+1]
for q in range(Q):
    print(cs[r[q]] - cs[l[q]])

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 

def resolve():
    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())

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

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

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
N,Q=map(int,input().split())
S=input()
query=[list(map(int,input().split())) for _ in range(Q)]
table=[0 for _ in range(N)]
num=0
for i in range(N-1):
    if (S[i]=="A")and(S[i+1]=="C"):
        num=num+1
    table[i+1]=num
for i in range(Q):
    print(table[query[i][1]-1]-table[query[i][0]-1])

Submission status: Accepted

Solution code:
def main():
    n, q = [int(e) for e in input().split()]
    s = input()
    LR = [[int(e) for e in input().split()] for i in range(q)]

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

        CNT.append(cnt)

    CNT.append(0)
    for lr in LR:
        print(CNT[lr[1] - 2] - CNT[lr[0] - 2])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#conding utf-8
N,Q=map(int,input().split())
S=input()
lr=[[int(i) for i in input().split()] for i in range(Q)]

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

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

Submission status: Accepted

Solution code:
import sys
from math import ceil, floor
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return

def main():
    n,q = map(int, input().split())
    s = input()
    cumsum = list()

    for i in  range(n+1):
        if i == 0:
            cumsum.append(0)
        else:
            if i > 1 and  s[i-2:i] == 'AC':
                
                cumsum.append(cumsum[i-1] + 1)
            else:
                cumsum.append(cumsum[i-1])
    #print(cumsum)
    for i in range(q):
        l,r = map(int, input().split())
        print(cumsum[r] - cumsum[l])
    
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
s = input() + '0'
lr = [list(map(int,input().split())) for _ in range(q)]
cnt = [0] * (n+1)

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

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = input()
t = [0] * (N + 1)
 
for i in range(N):
  t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0) # i文字目まででACが出現する数
  
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)

# iはSのインデックス。i,i+1がACならtのi+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()
lr=[]
for _ in range(Q):
    lr.append(tuple(map(int, input().split())))
#print(N, Q, S, lr)

accum=[0]*(N+1)
should_plus=0
for i in range(2, N+1):
    if S[i-2]=='A' and S[i-1]=='C':
        should_plus+=1
    accum[i]=should_plus
#print(accum)

for val in lr:
    left=val[0]
    right=val[1]
    OK=accum[right]-accum[left-1]
    if S[(left-2):left]=='AC':
        OK-=1
    print(OK)

Submission status: Accepted

Solution code:
import re
N, Q = map(int, input().split())
S=input()
lr=[]
for _ in range(Q):
    lr.append(tuple(map(int, input().split())))
#print(N, Q, S, lr)



accum=[0]*(N+1)
should_plus=0
for i in range(2, N+1):
    if S[i-2]=='A' and S[i-1]=='C':
        should_plus+=1
    accum[i]=should_plus
#print(accum)

for val in lr:
    OK=accum[val[1]]-accum[val[0]-1]
    if S[(val[0]-2):val[0]]=='AC':
        OK-=1
    print(OK)

Submission status: Accepted

Solution code:
import math
import collections
from operator import mul
from functools import reduce



n,q=map(int,input().split())
s=input()
y=[0]*(n+1)
flag=0
for i in range(n):
    if flag==0:
        if s[i]=="A":flag=1
    else:
        if s[i]=="C":
            y[i+1]+=1
            flag=0
        elif s[i]!="A":
            flag=0

    y[i+1]+=y[i]

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

Submission status: Accepted

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

csum = [0,0]
for i in range(1, N):
    if S[i-1] + S[i] == 'AC':
        csum.append(csum[i-1] + 1)
    else:
        csum.append(csum[i])
        
#文字番号に合わせた形になっている
for i in range(Q):
    l, r = map(int, input().split())
    print(csum[r]-csum[l])

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
# coding:utf-8
from itertools import accumulate
def main():
    n,q = map(int, input().split())
    s = input()
    l = [list(map(int,input().split())) for _ in range(q)]

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

if __name__ == '__main__' :
    main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import bisect

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

aclist = []
target = "AC"
index = -1
while True:
    index = S.find(target, index + 1)
    if index == -1:
        break
    aclist.append(index)

for [l, r] in lr:
    min_ac = bisect.bisect_left(aclist, l)
    max_ac = bisect.bisect_right(aclist, r-1)
    print(max_ac - min_ac)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
s = input()
cnt = [0] * (n+1)
for i in range(n):
    if s[i:i+2] == "AC":
        cnt[i+1] = cnt[i] + 1
    else:
        cnt[i+1] = cnt[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()
lr = [list(map(int, input().split())) for _ in range(Q)]
ans = [0 for _ in range(N+10)]

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

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

Submission status: Accepted

Solution code:
import sys
from bisect import *
from heapq import *
from collections import *
from itertools import *
from functools import *
from math import *
from fractions import *

sys.setrecursionlimit(100000000)
input = lambda: sys.stdin.readline().rstrip()

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

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

Submission status: Accepted

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

anum = [0]
for i in range(1, ls):
    if (s[i - 1] == "a"):
        anum.append(anum[i - 1] + 1)
    else:
        anum.append(anum[i - 1])

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

Submission status: Accepted

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

A = [0] * N

prev = s[0]
for i, v in enumerate(s):
    if prev == 'A' and v == 'C':
        A[i] = A[i-1] + 1
    else:
        A[i] = A[i-1]
    prev = v

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

Submission status: Accepted

Solution code:
import numpy as np
n, q = map(int, input().split())
s = input()
lr = []
for i in range(q):
        l,r = map(int, input().split())
        lr.append([l,r])

n = len(s)
L = 0
R = 1
cntAC = [0] * n

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

# 累積和
cSum = np.cumsum(cntAC)


for _lr in lr:
    if _lr[L] == 1:
        print(cSum[_lr[R]-2])
    else:
        print(cSum[_lr[R]-2] - cSum[_lr[L]-2])
        

"""
ACACTACG
"""

Submission status: Accepted

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

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

Submission status: Accepted

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

lr = [None] * Q
for _ in range(Q):
    lr[_] = list(map(int, input().split()))

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

Submission status: Accepted

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

ac_counts = [0 for _ in range(n + 1)]

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

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

Submission status: Accepted

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

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


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

Submission status: Accepted

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

for i 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 = list(map(int, input().split()))
S = input()

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

acc_sum = [0] * N
for i in range(1, N):
    if flags[i] == 1:
        acc_sum[i] = acc_sum[i - 1] + 1
    else:
        acc_sum[i] = acc_sum[i - 1]

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

Submission status: Accepted

Solution code:
import sys
import bisect
input = sys.stdin.readline
n,q = map(int,input().split())
s = list(input())
lr = [list(map(int,input().split())) for _ in range(q)]
ac = []
for i in range(n-1):
  if s[i] == "A" and s[i+1] == "C":
    ac.append(i)
for i in range(q):
  print(bisect.bisect_left(ac,lr[i][1]-1)-bisect.bisect_left(ac,lr[i][0]-1))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect

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

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

for i in range(Q):
    a,b = map(int,(input().split()))
    print(bisect.bisect_left(l,b) - bisect.bisect_left(l,a))

Submission status: Accepted

Solution code:
n,m=map(int,input().split()) 
q=input() 
l=[list(map(int,input().split())) for _ in range(m)] 
ans=0 
lst_j=[0]*(n+1) 
for i in range(n-1): 
	cnt=0 
	if q[i]+q[i+1]=="AC": 
		cnt=1 
		lst_j[i+1]=cnt+lst_j[i] 
	else:lst_j[i+1]=lst_j[i] 
for i,j in l: 
	ans=lst_j[j-1]-lst_j[i-1] 
	print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# import bisect
# from collections import Counter, deque
# import copy
# from fractions import gcd
# from functools import reduce
from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np
# import sys
# sys.setrecursionlimit(10**9)

def resolve():
    N,Q=map(int,input().split())
    S=str(input())

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

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

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

    # この問題は長さが1-Nの連続部分の和の最大値を出せというものなので以下の通り
    for j in range(Q):
        ans=B[R[j]]-B[L[j]]
        print(ans)



resolve()

Submission status: Accepted

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


t = [0] * (n+1)
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]


t[-1] = t[-2]


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):
    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()
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())
cnt = [0] * (N)

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

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

Submission status: Accepted

Solution code:
#122c
#累積和
N,Q = map(int, input().split())
S = list(input())

AC_cumsum = list()
AC_cumsum.append(0)

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
s = input()
t = [0] * n
for i in range(1, n):
    t[i] = t[i - 1] + (1 if s[i - 1:i + 1] == "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()
c=0
AC=[0]*(n)
for i in range(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:
N, Q = map(int, input().split())
S = input()
count_AC = [0]
tmp = 0
for i in range(1, len(S)):
    if S[i - 1] + S[i] == 'AC':
        tmp += 1
    count_AC.append(tmp)
for i in range(Q):
    l, r = map(int, input().split())
    print(count_AC[r-1] - count_AC[l-1])

Submission status: Accepted

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

Submission status: Accepted

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

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