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.

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

Solution (Python):
n,q = (int(i) for i in input().split())
s = input()
query = [0]*(n+1)
point = [0]*(n+1)
ct = 0
for i in range(n-1):
  if s[i] == 'A' and s[i+1] =='C': 
    ct += 1
    point[i] = -1 
  query[i+1] = ct
query[i+2] = ct  

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

Solution (Python):
n,q = map(int,input().split()) 
a = list(input())
dp = [0]*n
cou_AC = 0

for i in range(n-1):
     if (a[i] == "A") and (a[i+1] == "C"):
          cou_AC += 1
     dp[i+1] = cou_AC

for i in range(q):
     s,e = map(int,input().split())
     s,e = s-1,e-1
     ans = dp[e]-dp[s]
     print(ans)

Solution (Python):
import sys

l = raw_input().split()
N = int(l[0])
Q = int(l[1])
l = raw_input().split()
S = l[0]

L = [0]*Q
R = [0]*Q

ac = 'AC'

for i in range(Q):
    l = raw_input().split()
    L[i] = int(l[0])
    R[i] = int(l[1])



def count(S, table):
    length = len(S)
    c = 0
    for i in range(length - 1):
        
        if ac == S[length - i - 2:length - i]:
            c += 1
        table[i+1] = c

length_S = len(S)
table = [0]*length_S

count(S, table)


for i in range(Q):
    print(table[length_S - L[i]] - table[length_S - R[i]])

Solution (Python):
import sys
input = sys.stdin.readline
import numpy as np
import bisect
left = bisect.bisect_left
right = bisect.bisect_right

def question():
    n, q = list(map(int, input().split()))
    s = input()
    lr = [list(map(int, input().split())) for i in range(q)]
    a = [i for i in range(n-1) if s[i:i+2]=="AC"]

    for i in range(q):
        left_index = left(a, lr[i][0]-1)
        right_index = right(a, lr[i][1]-2)
        print(right_index - left_index)

question()

Solution (Python):
N, Q = (int(i) for i in input().split())
S = input()

code = [0] * N
cnt = 0
index = 0
flag = False
for chr in S: 
    if chr == "A":
            flag = True
    elif chr == "C" and flag == True:
        cnt += 1
        flag = False
    else:
        flag = False
    code[index] = cnt
    index += 1

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

Solution (Python):
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())
count = 0
c_sum = [0]*n
for i in range(n-1):
  if s[i] == 'A' and s[i+1] == 'C':
    count += 1
  c_sum[i] = count
for i in range(q):
  print(c_sum[r[i]-2] - c_sum[l[i]-2])

Solution (Python):



import numpy as np

def main():
  N, Q = map(int, input().strip().split(' '))
  S = input()
  ans = []
  rs = np.zeros(len(S), dtype=np.int)
  for i in range(1,len(S)):
    if S[i-1:i+1] == 'AC':
      rs[i] = rs[i-1]+1
    else:
      rs[i] = rs[i-1]
  for _ in range(Q):
    l, r = map(int, input().strip().split(' '))
    l -= 1
    r -= 1
    ans += [rs[r]-rs[l]]
  [print(a) for a in ans]
  pass

if __name__=='__main__':
  main()

Solution (Python):



import bisect

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

i = 0
ac_indices = []
while True:
    index = S[i:].find('AC')
  
    if index == -1:
        break
    else:
        ac_indices.append(i + index)
        i +=  index + 1

for _ in range(Q):
    start, end = map(int, input().rstrip().split(' '))
    start -= 1
    end -= 1
    
    start_index = bisect.bisect_left(ac_indices, start)
    end_index = bisect.bisect_left(ac_indices, end)
        
    print(end_index - start_index)

Solution (Python):
from statistics import mean, median,variance,stdev
import numpy as np
import sys
import math
import fractions
import itertools
import copy
from operator import itemgetter

def j(q):
    if q==1: print("Yes")
    else:print("No")
    exit(0)


def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")

def ip():
    return int(input())

def pne(n):
    print(n,end='')

rem = pow(10,9)+7


n,q= (int(i) for i in input().split())       

a = input()                                  







gatacca = ["A","C","T","G"]
pa = [0]
pc = []
s = 0
for i in range(n-1):
    if a[i] == "A" and a[i+1] == "C":
        s+=1
    pa.append(s)
for i in range(q):
    left,right =  (int(i) for i in input().split())
    right-=1
    left-=1
    print(pa[right]-pa[left])

Solution (Python):
import bisect
n,q = map(int,input().split())

S = input()
aindex = []
for i in range(len(S)-1):
    if (S[i] == "A"):
        if(S[i+1] == "C"):
            aindex.append(i+1)

for i in range(q):
    l,r = map(int,input().split())
    x = bisect.bisect_left(aindex, l)
    y = bisect.bisect_left(aindex, r-1)
    if x == len(aindex):
        print("0")
        continue
    if y != len(aindex):
        if aindex[y] == r-1:print(y-x+1)
        else:print(y-x)
    else:
        print(y-x)

Solution (Python):

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

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

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

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

S = list(input())

ansList=[0]
ans=0
for i in range(N-1):
  if S[i] =="A" and S[i+1] =="C":
      ans+=1
      ansList.append(ans)
  else:
    ansList.append(ans)

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

Solution (Python):
N,Q =map(int,input().strip().split())


S = input()

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


for i in range(0,Q):
    l,r = map(int,input().strip().split())
    if r > len(count):
        r = len(count)
    if l == 0:
        l += 1
    print(count[r - 1] - count[l - 1])

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

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

Solution (Python):
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])

Solution (Python):
nq = input().split()
n = int(nq[0])
Q = int(nq[1])

s = input()

prefix_sums = [0 for i in range(0,n+1)]

for i in range(1, n):

    prefix_sums[i+1] = prefix_sums[i]

    if s[i] == 'C' and s[i-1] == 'A': prefix_sums[i+1]+=1

for query in range(0,Q):

    lr = input().split()
    l=int(lr[0])
    r=int(lr[1])

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

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

l = [0] * q
r = [0] * q

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

s_list = list(s)

ac_list = [0] * (n-1)

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



w = [0] * (n-1)

w[0] = ac_list[0]

for i in range(1,n-1):
    w[i] = w[i-1] + ac_list[i]



for i in range(0,q):
    if l[i] == 0:
        print(w[r[i]-1])
    else:
        print(w[r[i]-1]-w[l[i]-1])

Solution (Python):


import math
import sys
import itertools
import numpy as np


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


s = list(input())


x = [[int(i) for i in input().split()] for i in range(q)] 
c = [0]



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


for i in range(q):
    if x[i][0] == 1:
        print(c[x[i][1]-1])
    else:
        print(c[x[i][1]-1]-c[x[i][0]-1])

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

Solution (Python):
import sys
import bisect

N, Q = map(int, input().split())
s = sys.stdin.readline().rstrip()
ac_list = []
start = 0
while True:
  index = s.find('AC', start)
  if index == -1:
    break
  ac_list.append(index + 1)
  start = index + 1


for _ in range(Q):
  l, r = map(int, input().split())
  res = 0
  start = bisect.bisect_left(ac_list, l)
  end = bisect.bisect_right(ac_list, r-1) - 1
  print(end-start+1)

Solution (Python):
x = input()
y = x.split()
y = [int (i) for i in y]
string = input()

length = y[0]
num    = y[1]
arr    = [0] * (length + 1)
arr[0] = 0

count = 0
for i in range(length-1):
    if string[i] == "A" and string[i+1] == "C":
        count +=1
        arr[i+1] = count
    else:
        arr[i+1] = arr[i]

result   = 0
for i in range(num):
    z = input()
    c = z.split()
    c = [int (i) for i in c]
    l = c[0]
    r = c[1]
    result = arr[r-1] - arr[l-1]

    print(result)
    result = 0

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

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

Solution (Python):
n,q =map(int,input().split())
S = input()
LR = [list(map(int,input().split())) for _ in range(q)]
temp = ""
S2 = []

for s,i in zip(S,range(n)):
    if temp == "A" and s == "C":
        S2.append(i)
    temp = s

import bisect as bi

for l,r in LR:
    ans = - bi.bisect_right(S2,l-1) + bi.bisect_right(S2,r-1)
    print(ans)

Solution (Python):
import sys,collections,math;sys.setrecursionlimit(10**7)
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def Ss(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N,Q = Is()
S = S()
lis = [0]
t = 0
for i in range(N):
    if S[i:i+2] == "AC":
        t += 1
    lis.append(t)
for q in range(Q):
    l,r = Is()
    print(lis[r-1]-lis[l-1])

Solution (Python):
n, q = map(int, input().split())
s = input().strip()
ac = [0 for _ in range(n)]
prevs = ''
for i, _s in enumerate(s):
  if prevs == 'A' and _s == 'C':
    ac[i] = ac[i-1] + 1
    prevs = _s
  else:
    ac[i] = ac[i-1]
    prevs = _s
for _ in range(q):
  l, r = map(int, input().split())
  print(ac[r-1] - ac[l-1])

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

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

for i in range(Q):
    print( sum( lst[ lr[i][0] - 1 : lr[i][1] - 1 ] ) )
'''
for i in range(N-1):
    if S[i] == 'A' and S[i+1] == 'C' and i == 0:
        lst[i] += 1
    elif S[i] == 'A' and S[i+1] == 'C':
        lst[i] += 1 + lst[i-1]
    else:
        lst[i] += lst[i-1]

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

Solution (Python):
n, q = map(int, input().split())
s = input()
li = []
a = 0
li.append(0)

for i in range(len(s)-1):
    if s[i] == "A" and s[i+1] == "C":
        a += 1
        li.append(a)
    else:
        li.append(a)

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

Solution (Python):
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq
import itertools
import operator
import re


inf = float('inf')


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types):
    if len(types) == 1:
        return [types[0](input()) for _ in range(n)]
    return zip(*(
        [t(x) for t, x in zip(types, input().split())]
        for _ in range(n)
    ))



N, Q = 0, 0
S = ""
L, R = [], []


def set_inputs():
    global N, Q, S, L, R
    N, Q = get_li()
    S = get_str()
    L, R = get_data(Q, [int, int])
    return


def main():
    setrecursionlimit(100000)
    set_inputs()
    a, c = [], []
    for m in re.finditer("AC", S):
        a.append(m.start())
        c.append(m.end())
    for l, r in zip(L, R):
        s = bisect_left(a, l-1)
        e = bisect_right(c, r)
        if e - s <= 0:
            print(0)
        else:
            print(e - s)
    return







if __name__ == '__main__':
    main()

Solution (Python):
N, Q= map(int, input().split())
S = input()
D = []
for i in range(Q):
    l, r = map(int, input().split())
    D.append([l,r])

c =[0]*N
for i in range(N-1):
    if S[i:i+2] == "AC":
        c[i+1]=c[i]+1
    else:
        c[i+1]=c[i]
for l, r in D:
    print(c[r-1]-c[l-1])

Solution (Python):
from itertools import accumulate
N, Q = map(int, input().split())
S = input()


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


A_acc = list(accumulate(A))
for q in range(Q):
    l, r = map(int, input().split())
    ans = A_acc[r] - A_acc[l]
    print(ans)

Solution (Python):
import sys
from itertools import accumulate

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    S = [str(c) for c in input().strip()]

    dp = [0] * N
    for i in range(1, N):
        s = S[i-1] + S[i]
        if s == 'AC':
            dp[i] += 1
    
    DP = list(accumulate(dp))

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


if __name__ == '__main__':
    main()

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


s = input()
arr = []
c = 0
for i in range(len(s)):
    if i == 0:
        arr.append(0)
    else: 
        
        if (s[i-1]+s[i]) == "AC":
            c+=1
        arr.append(c)


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

Solution (Python):
n, q = map(int, input().split())
s = input()
a = [0]*n
for i in range(n-1):
    if s[i:i+2] == 'AC':
        a[i+1] = 1
    if i > 0:
        a[i] += a[i-1]
a[n-1] += a[n-2]

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

Solution (Python):
from sys import stdin

def main():
    N, Q = map(int, input().split())
    S = input()
    LR = [tuple(map(int, input().split())) for _ in [0] * Q]

    cnt = [0] * N
    prev = ''
    for i, s in enumerate(S):
        if prev + s == 'AC':
            cnt[i] = cnt[i-1] + 1
        else:
            cnt[i] = cnt[i-1]
        prev = s

    for l, r in LR:
        n = cnt[r-1] - cnt[l-1]
        print(n)

input = lambda: stdin.readline().rstrip()
main()

Solution (Python):
GI = lambda: int(input()); GIS = lambda: map(int, input().split()); LGIS = lambda: list(GIS())

def main():
    N, Q = GIS()
    s = input()
    d = [0]
    c = 0
    for i in range(1, len(s)):
        if s[i] == 'C' and s[i-1] == 'A':
            c += 1
        d.append(c)
    for q in range(Q):
        l, r = GIS()
        print(d[r-1] - d[l-1])



main()

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

S = ['X'] + list(S)
count = [0]*(N+1)

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

Solution (Python):
import sys

N,Q=map(int, sys.stdin.readline().split())
S=raw_input()
L=[ map(int, sys.stdin.readline().split())  for i in range(Q) ] 

W=[0]

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


for x, y in L:
	print W[y-1]-W[x-1]

Solution (Python):
import sys
read = sys.stdin.readline


def readln():
    return list(map(int, read().split()))


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

L = []
R = []
for _ in range(Q):
    a, b = readln()
    L.append(a-1)  
    R.append(b-1)

AC_count = [0] * N  
cnt = 0

for i, (s1, s2) in enumerate(zip(S[:-1], S[1:])):
    if s1 == 'A' and s2 == 'C':
        cnt += 1

    AC_count[i+1] = cnt

for l, r in zip(L, R):
    print(AC_count[r]-AC_count[l])

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

Solution (Python):
n,q=map(int,input().split())
s=input()
l=[]
r=[]
for i in range(q):
    a,b=map(int,input().split())
    l.append(a)
    r.append(b)
i=0
k=[0]
while i <len(s)-1:
    if s[i]=="A" and s[i+1]=="C":
        k.append(k[i]+1)
    else:
        k.append(k[i])
    i+=1
k.append(k[i])
for j in range(q):
    print(k[r[j]-1]-k[l[j]-1])

Solution (Python):


def genindex(N, S):
    index = [0] * len(S)
    c = 0
    i = 0
    while i < len(S)-1:
        if S[i] == 'A' and S[i+1] == 'C':
            c+=1
            index[i] = c
            i+=1
        else: 
            index[i] = c
            i+=1
    return index


def main():
    N, Q = [int(x) for x in input().split()]
    S = "__" + input()
    
    index = genindex(N, S)


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

main()

Solution (Python):
import re
 
n, q = map(int, input().split())
s = input()
 
l = []
r = []
 
for i in range(q):
    _l, _r = map(int, input().split())
    l.append(_l)
    r.append(_r)
 
memo = [0 for i in range(len(s))]
cnt = 0
 
for i in range(1, len(s)):
    if s[i - 1] == "A" and s[i] == "C":
        cnt += 1
    memo[i] = cnt
 
for i in range(q):
    print(memo[r[i] - 1] - memo[l[i] - 1])

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


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):
  b,c=map(int,input().split())
  l.append(b-1)
  r.append(c-1)

for i in range(q):
  print(a[r[i]]-a[l[i]])

Solution (Python):
import bisect
N,Q=map(int,input().split())
S=input()
l=[]
for i in range(N-1):
  if S[i:i+2]=="AC":
    l.append(i+1)
for i in range(Q):
  a,b=map(int,input().split())
  c=bisect.bisect_left(l,a)
  d=bisect.bisect_right(l,b-1)
  print(d-c)

Solution (Python):

import sys
input = sys.stdin.readline

n, q = (int(i) for i in input().split())
s = input()

mem = [0]
count = 0
for i in range(1, len(s)):
    if s[i-1]+s[i] == "AC":
        count +=1
    mem.append(count)
    
for x in [[int(i)-1 for i in input().split()] for i in range(q)]:
    res = mem[x[1]] - mem[x[0]]
    print(res)

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

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

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

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

cnt = [0]*N
tmp = 0
for i,c in enumerate(S):
    if tmp == 0 and c == "A":
        tmp =1
        cnt[i] = cnt[i-1]
    elif tmp == 1 and c == "C":
        tmp =0
        cnt[i] = cnt[i-1]+1
    else:
        tmp = int(c == "A")
        cnt[i] = cnt[i-1]

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

Solution (Python):
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())

ans = [0] * N


for i in range(len(S)-1):
    if S[i] == 'A' and S[i+1] == 'C':
        ans[i+1] = ans[i] + 1
    else:
        ans[i+1] = ans[i]
        
for j in range(Q):
    print(ans[r[j]-1]-ans[l[j]-1])

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

Solution (Python):
N, Q = [int(i) for i in input().split()]
S = input()
lrs = [[int(i) for i in input().split()] for _ in range(Q)]


cache = {1: {'c': 0, 'm': False}}
cnt = 0
for i in range(1, N):
    if S[i - 1]+S[i] == 'AC':
        cnt += 1
    cache[i + 1] = {'c': cnt, 'm': True}

for l, r in lrs:
    print(cache[r]['c'] - cache[l]['c'])

Solution (Python):
n, q = [int(i) for i in input().split()]
S = input()
counter = [0] * len(S)
for i in range(len(S)):
    if i == 0:
        counter[i] == 0
    elif S[i-1:i+1] == 'AC':
        counter[i] = counter[i-1] + 1
    else:
        counter[i] = counter[i-1]

counter = [0] + counter



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

Solution (Python):



import sys


N,Q = map(int, input().split())
S = str(input())
lr = [[0 for j in range(2)] for i in range(Q)]
for i in range(Q):
  lr[i] = list(map(int, input().split()))

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


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

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

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

Solution (Python):
from itertools import accumulate
N, Q = map(int, input().split())
S = input()
rs = [0] * N

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

rm = [0] + list(accumulate(rs))

for i in range(Q):
    ans = 0
    l, r = map(int, input().split())
    if S[l] == "C":
        ans -= 1
    ans = rm[r] - rm[l]
    print(ans)

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

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


count = [0 for i in range(N)]

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

for beg, end in indices:
    if beg == 0:
        print(count[end])
    
    else:
        is_boundary = S[beg-1:beg+1] == 'AC'
        print(count[end] - count[beg - 1] - int(is_boundary))

Solution (Python):
import bisect
N,Q=[int(x) for x in input().split()]
S=input()

L=[]
c=0
while True:
    try:
        if S[c]=="A" and S[c+1]=="C":
            L.append(c+1)
        c+=1
    except:
        break

for i in range(Q):
    l,r=[int(x) for x in input().split()]
    first=bisect.bisect_left(L,l)
    last=bisect.bisect_left(L,r-1)
    L.append(10**5+1)
    if L[last]==r-1:
        print(last-first+1)
    else:
        print(last-first)

Solution (Python):
n, q = map(int, input().split())
listS = list(input())
index=0
listA=[]
listM=[0]*n
index2=1
countM=0
while index2 < len(listS):
    if listS[index2-1]=="A" and listS[index2]=="C":
        countM+=1
    listM[index2] = countM               
    index2+=1

while index < q:
    l, r = map(int, input().split())
    listA.append(listM[r-1]-listM[l-1])
    index+=1
for ans in listA:
    print(ans)

Solution (Python):



import sys


class OccCounter(object):

    def __init__(self, n, s):
        self.length = n
        self.base_str = s
        self.occ_nums = [0] * n
        for i in range(1, n):
            self.occ_nums[i] = self.occ_nums[i - 1] + int(s[i - 1] == "A" and s[i] == "C")
        
        self.occ_nums.insert(0, 0)
        
        
    
    def count_occs(self, le, ri):
        
        res = self.occ_nums[ri] - self.occ_nums[le - 1]
        if le > 1 and self.base_str[le - 2] == "A" and self.base_str[le - 1] == "C":
            res -= 1
        return res


def main():
    n, q = (int(z) for z in input().split())
    s = input()
    oc = OccCounter(n, s)
    for _ in range(q):
        le, ri = (int(z) for z in input().split())
        print(oc.count_occs(le, ri))


if __name__ == "__main__":
    main()

Solution (Python):
n, q = [int(x) for x in input().split()]
s = input()
c = [s[i:i + 2] == "AC" for i in range(n - 1)]
d = [0] * n
for i in range(1, n):
    d[i] = d[i - 1] + c[i - 1]

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

Solution (Python):
N,Q = map(int,input().split())
S = input()
ans = []

ac = [0]*(len(S)+1)
last = ''
for i in range(len(S)):
    s = S[i]
    if s=='C' and last == 'A':
        ac[i-1] = 1
    last = s

add = [0]*(len(S)+2)
for i in range(len(ac)):
    add[i+1] = add[i] + ac[i]

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

for a in ans:
    print(a)

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

s = input()

cnt = [0]

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


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

Solution (Python):
import bisect
N, Q = map(int, input().split())
S = input()
minians = []
for i in range(N-1):
    if S[i:i + 2] == "AC":
        minians.append(i)

ans = [0]*Q
for i in range(Q):
    left, right = map(int, input().split())
    left -= 1
    right -= 1
    """print("\n", bisect.bisect_left(minians, right),
          bisect.bisect_left(minians, left))"""
    ans[i] = bisect.bisect_left(minians, right) - \
        bisect.bisect_left(minians, left)

    
    """for j in range(len(minians)):
        if left <= minians[j] and minians[j] < right:
            ans[i] += 1
        elif minians[j] >= right:
            break"""
print('\n'.join(map(str, ans)))

Solution (Python):
import bisect

N, Q = map(int, input().split())
S = input()
Qi = []
for i in range(Q):
    a = list(map(int, input().split()))
    Qi.append(a)

index_list = []
idx = 0
while idx < len(S):
    i2 = S.find("AC", idx)
    if i2 < 0:
        break
    index_list.append(i2)
    idx = i2 + 2

for q in Qi:
    if len(index_list) == 0:
        print(0)
        continue
    left = bisect.bisect_left(index_list, q[0] - 1)
    right = bisect.bisect_right(index_list, q[1] - 2)
    print(right - left)

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

Solution (Python):
from bisect import bisect_left, bisect_right


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


[N, Q] = ii()
S = input()
Q_list = [ii() for _ in range(Q)]

AC_idx = []
try:
    start_idx = 0
    while True:
        found_idx = S.index("AC", start_idx)
        AC_idx.append(found_idx)
        start_idx = found_idx + 1
except ValueError as e:
    pass

for q in Q_list:
    left_idx = bisect_left(AC_idx, q[0] - 1)
    right_idx = bisect_right(AC_idx, q[1] - 2)
    print(right_idx - left_idx)

Solution (Python):
n, m = map(int, input().split())
s = input()
imos = [0 for _ in range(n)]
for i in range(1, n):
    if s[i-1] == "A" and s[i] == "C":
        imos[i] = imos[i-1]+1
    else:
        imos[i] = imos[i - 1]
for _ in range(m):
    l, r = map(int, input().split())
    if l > 1:
        print(imos[r-1]-imos[l-1])
    else:
        print(imos[r-1])

Solution (Python):


from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

N, Q = map(int, raw_input().split())
S = raw_input()
cnt = [0] * (N + 1)
for i in range(N - 1):
    cnt[i + 2] = cnt[i + 1]
    if S[i] == 'A' and S[i + 1] == 'C':
        cnt[i + 2] += 1
for _ in range(Q):
    l, r = map(int, raw_input().split())
    ans = cnt[r] - cnt[l - 1]
    if cnt[l] != cnt[l - 1]:
        ans -= 1
    print ans

Solution (Python):
N,Q = map(int,input().split())
S = input()
tmp = 0
ruiseki = [0]

for i in range(1,len(S)):
    if S[i-1] == 'A' and S[i] == 'C':
        tmp += 1
    ruiseki.append(tmp)

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

Solution (Python):
n, q = map(int, input().split())
listS = list(input())
index=0
listA=[]
listM=[0]*n
index2=1
countM=0
while index2 < len(listS):
    if listS[index2-1]=="A" and listS[index2]=="C":
        countM+=1
    listM[index2] = countM               
    index2+=1

while index < q:
    l, r = map(int, input().split())
    listA.append(listM[r-1]-listM[l-1])
    index+=1
for ans in listA:
    print(ans)

Solution (Python):


import sys


INF = float('inf')
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 LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    n, q = LI()
    s = 'X' + SI()
    Q = [LI() for _ in range(q)]

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

    for l, r in Q:
        print(ac[r] - ac[l])
    


main()

Solution (Python):
nums = list(map(int, input().split()))
N, Q = nums[0], nums[1]
S = input()
ls = []
rs = []
for i in range(Q):
    nums = list(map(int, input().split()))
    ls.append(nums[0])
    rs.append(nums[1])

pattern = 'AC'

import re

results = re.finditer(pattern, S)
S_cum = [0 for _ in range(N)]
for r in results:
    S_cum[r.span()[1]-1] = S_cum[r.span()[0]] + 1
import numpy as np
S_cum = np.cumsum(S_cum)
for i in range(Q):
    print(S_cum[rs[i]-1] - S_cum[ls[i]-1])