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()
tmp = [0 for i in range(len(s))]
for i in range(len(s)-1):
  if s[i] == "A" and s[i+1] == "C":
    tmp[i] = 1
    
ans = [0 for i in range(len(s)+1)]
for i in range(1, len(ans)):
  ans[i] = ans[i-1] + tmp[i-1]
  
for i in range(q):
  l, r = map(int, input().split())
  count = 0
  print(ans[r-1] - ans[l-1])

Submission status: Accepted

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

num=[0]*N

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

sums=[0]*(N+1)
for i in range(1,N+1):
    sums[i]=sums[i-1]+num[i-1]

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

Submission status: Accepted

Solution code:
# coding: utf-8
N,Q=map(int,input().split())
S=list(input())
W=[0]*N
W[0]=0

for i in range(1,N):
    if S[i-1]=='A' and S[i]=='C':
        W[i]=W[i-1]+1
    else:
        W[i]=W[i-1]
#print(W)

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

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = str(input())
 
#ac = [1 if S[i] == 'A' and S[i+1] == 'C' else 0 for i in range(N-1) ]
a = 0
lst = [0]
for i in range(1, N):
  if S[i-1] == 'A' and S[i] == 'C':
    a += 1
  lst.append(a)
for _ in range(Q):
  l, r = map(int, input().split())
  print(lst[r-1] - lst[l-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
h,n = list(map(int, input().split()))
st = str(input())
a = [list(map(int, input().split())) for _ in range(n)]

o = "B"
b = []
c = 0
for i in range(len(st)):
    sti = st[i]
    if sti == "A":
        o = "A"
        b.append(c)
    elif sti == "C" and o == "A":
        o = "C"
        c += 1
        b.append(c)
    else:
        o = "B"
        b.append(c)

for a1,b1 in a:
    print(b[b1-1] - b[a1-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:
import sys
input = sys.stdin.readline


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

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

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

Submission status: Accepted

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

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

a = [0]*len(S)
for i in range(1, len(S)):
	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):
	print(a[L[i][1] - 1] - a[L[i][0] - 1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
s=input()
cnt=[0]*n
icnt=0
for i in range(n-1):
#    print(s[i:i+2])
    if s[i:i+2]=="AC":
      icnt=icnt+1
      cnt[i+1]=cnt[i]+1
    else:
      cnt[i+1]=cnt[i]
#print(cnt,s)
for i in range(q):
    li,ri=map(int,input().split())
#    print(s[li-1:ri].count("AC"))
#    print(sum(cnt[li-1:ri-1]))
    print(cnt[ri-1]-cnt[li-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)

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

[print(x) for x in ans]

Submission status: Accepted

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

def convert_N_AC():
    
    for i in range(1, len(S)):
        tmp = 0
        if (S[i - 1 : i + 1] == 'AC'):
            tmp = 1
        S_con[i] += tmp + S_con[i-1]

convert_N_AC()

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

Submission status: Accepted

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

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

ss=[0]*(n+1)

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

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

Submission status: Accepted

Solution code:
import sys

INPUT = lambda: sys.stdin.readline().rstrip()
MAP = lambda: map(int, INPUT().split())

sys.setrecursionlimit(10 ** 9)


def main():
    N, Q = MAP()
    S = INPUT()
    
    L = [0]
    for i in range(N-1):
        L.append(L[-1] + (1 if S[i:i+2] == "AC" else 0))

    ans = []
    for i in range(Q):
        l, r = MAP()
        ans.append(L[r-1] - L[l-1])

    print(*ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

t = [0] * len(S)

for index, s in enumerate(S):
  if index+1 > len(S)-1:
    break

  if s == 'A' and S[index+1] == 'C':
    t[index+1] = t[index] + 1
    
  else:
    t[index+1] = t[index]

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

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
f = lambda : map(int,input().split())

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

ln = [0]
for i in range(n):
  ln += [ln[i] + (s[i-1:i+1]=='AC')]

for _ in range(q):
  l, r = f()
  print(ln[r] - ln[l])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
f = lambda : map(int,input().split())

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

ln = [0]*n
for i in range(1,n):
  ln[i] = ln[i-1] + (s[i-1:i+1]=='AC')

for _ in range(q):
  l, r = f()
  print(ln[r-1] - ln[l-1])

Submission status: Accepted

Solution code:
f = lambda : map(int,input().split())

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

ln = [0]*n
for i in range(1,n):
  ln[i] = ln[i-1] + (s[i-1:i+1]=='AC')

for _ in range(q):
  l, r = f()
  print(ln[r-1]-ln[l-1])

Submission status: Accepted

Solution code:
f = lambda : map(int,input().split())

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

cnt = 0
ln = [0]*n
for i in range(1,n):
  if s[i-1:i+1] == 'AC':
    cnt += 1
  ln[i] = cnt
for _ in range(q):
  l, r = f()
  print(ln[r-1]-ln[l-1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
f = lambda : map(int,input().split())

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

cnt = 0
ln = [0]*n
for i in range(1,n):
  if s[i-1:i+1] == 'AC':
    cnt += 1
  ln[i] = cnt
for _ in range(q):
  l, r = f()
  print(ln[r-1]-ln[l-1])

Submission status: Accepted

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

cnt = 0
ln = [0]*n
for i in range(1,n):
  if s[i-1:i+1] == 'AC':
    cnt += 1
  ln[i] = cnt
for _ in range(q):
  l, r = f()
  print(ln[r-1]-ln[l-1])

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
s=input()
t=[0]*(n+1)
for i in range(n):
	t[i+1]=t[i]+(s[i:i+2]=='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()
l, r = [0] * Q, [0] * Q
cnt = [0] * len(S)
for i in range(Q):
    l[i], r[i] = map(int, input().split())
    l[i] -= 1
    r[i] -= 1
for i in range(1, len(S)):
    if(i == 0): pass
    cnt[i] = cnt[i - 1]
    if (S[i] == 'C' and S[i - 1] == 'A'):
        cnt[i] += 1
for i in range(Q):
    print(cnt[r[i]] - cnt[l[i]])

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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

lr=[]
for _ in range(q):
    D = list(map(int, input().split()))
    lr.append(D)

ac_list=[]

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

import bisect

for j in range(q):
    ind1 = bisect.bisect_left(ac_list,lr[j][0]-1)
    ind2 = bisect.bisect_left(ac_list,lr[j][1]-1)

    print(ind2-ind1)

Submission status: Accepted

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

Submission status: Accepted

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

s.append("")

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

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

Submission status: Accepted

Solution code:
import numpy as np

N, Q = map(int, input().split())
S = np.zeros(N+1, dtype="S1")
S[1:] = list(input())

A = (S == b'A')
C = (S == b'C')
AC = (A[:-1] & C[1:]) # Aが右、Cが左になる形
AC_cum = list(AC.cumsum())

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

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = input()
LR = [[int(x)-1 for x in input().split()] for _ in range(Q)]
AC = []
pre = None
cnt = 0
for s in S:
  if s == "A":
    pre = "A"
  elif pre == "A" and s == "C":
    cnt += 1
    pre = None
  elif pre == "A": # 次の処理の為、初期化
    pre = None
  AC.append(cnt)

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

Submission status: Accepted

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

for j in range(0,n-1):
    if((s[j] == 'A') and s[j+1] == 'C'):
        sum_array[j+1] = sum_array[j] + 1
    else:
        sum_array[j+1] = sum_array[j]

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

Submission status: Accepted

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def ifn(): return float(input()) #浮動小数点読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def fmn(): return map(float, input().split()) #浮動小数点map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, input().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD

N,Q = imn()
S = input()
lr = [iln() for _ in range(Q)]

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

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

for i in range(Q):
    left = lr[i][0]-1
    right = lr[i][1]-1
    print(c[right]-c[left])

Submission status: Accepted

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def ifn(): return float(input()) #浮動小数点読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def fmn(): return map(float, input().split()) #浮動小数点map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, input().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD

N,Q = imn()
S = input()
lr = [iln() for _ in range(Q)]

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

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

for i in range(Q):
    l = lr[i][0]
    r = lr[i][1]
    print(s[r-1]-s[l-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import _collections
import string

class cin():
    def int():
        return int(sys.stdin.readline().rstrip())
    def string():
        return sys.stdin.readline().rstrip()
    def mapInt():
        return [int(x) for x in cin.string().split()]
    def stringList(n):
        return [input() for i in range(n)]
    def intListList(n):
        return [cin.mapInt() for i in range(n)]
    def intColsList(n):
        return [int(input()) for i in range(n)]

class Util():
    def roundUp(a,b):
        return -(-a // b)
    def toUpperMultiple(a,x):
        return Util.round_up(a,x) * x
    def toLowerMultiple(a,x):
        return (a // x) * x
class Math():
    def gcd(a,b):
        if b == 0:
            return a
        return Math.gcd(b,a % b)

def main():
    N,Q = cin.mapInt()
    S = cin.string()
    A = cin.intListList(Q)
    sums = [0] * N 
    for i in range(1,N):
        sums[i] = sums[i - 1]
        if S[i] == "C" and S[i - 1] == "A":
            sums[i] +=1
    for q in A:
        print(sums[q[1] - 1] - sums[q[0] - 1])
    return

if __name__ == "__main__":
    main()

Submission status: Accepted

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


ac = [0] * n

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

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

Submission status: Accepted

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

lr = []

for i in range(Q):
    lr.append(list(map(int,input().split())))

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

for i in range(Q):
    print(acs[lr[i][1]-1]-acs[lr[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)
for i in range(q):
    l,r = map(int,input().split())
    print(t[r-1]-t[l-1])

Submission status: Accepted

Solution code:
def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def main():
    N, Q = read_values()
    S = input()
    
    num = [0]
    pre = None
    count = 0
    for s in S:
        if pre == "A" and s == "C":
            count += 1
        num.append(count)
        pre = s

    for _ in range(Q):
        l, r = read_values()
        print(num[r] - num[l])


if __name__ == "__main__":
    main()

Submission status: Accepted

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

  print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

# cum[i]: S[0]~S[i]におけるACの数
cum = [0]
cnt = 0
for i in range(1, N):
    if S[i-1]+S[i] == 'AC':
        cnt+=1
    cum.append(cnt)

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

for i in ans:
    print(i)

Submission status: Accepted

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

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

Submission status: Accepted

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

count_seq = [0]*n

for i in range(n-1):
  if s[i:i+2] == 'AC':
    count_seq[i+1] = 1

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from bisect import bisect, bisect_left

n,q=map(int,input().split())
s=input()
l=[]
r=[]
for i in range(q):
	L,R=map(int,input().split())
	l.append(L-1)
	r.append(R-1)

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

for i in range(q):
	print(bisect(c,r[i])-bisect_left(a,l[i]))

Submission status: Accepted

Solution code:
def calculate(n,q,S):
    indexes = [0 for i in range(n)]

    arr = list(S)

    for i in range(len(arr)):
        if i == 0:
            indexes[i] = 0
            continue
        if arr[i] == 'C' and arr[i-1] == 'A':
                indexes[i] = indexes[i-1] + 1
        else:
            indexes[i] = indexes[i-1]
    return indexes

def conclution(res,Q):
    for qrr in Q:
        s2 = res[qrr[1]-1]
        s1 = res[qrr[0]-1]
        print(s2-s1)


input1 = input().split(" ")

n = int(input1[0])
q = int(input1[1])
S = input()

res = calculate(n,q,S)

qrr = []

for i in range(q):
    qrr.append([int(s) for s in input().split()])

conclution(res, qrr)

Submission status: Accepted

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

ls=[0]

Spre=S[0]
for i in range(1,N):
    Si=S[i]
    if Spre=='A' and Si=='C':
        ls.append(ls[-1]+1)
    else:
        ls.append(ls[-1])
    Spre=Si
 
for i in range(Q):
    l,r=map(int,input().split())
    print(ls[r-1]-ls[l-1])

Submission status: Accepted

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

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

Submission status: Accepted

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

for l, r in l_r_list:
    print(tmp[r-1] - tmp[l-1])

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline
import bisect
left = bisect.bisect_left
right = bisect.bisect_right

def question():
    n ,q = 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()

Submission status: Accepted

Solution code:
import sys

n, q = map(int, sys.stdin.readline().split())
s = '$' + sys.stdin.readline().rstrip()
lr = zip(*[map(int, sys.stdin.read().split())] * 2)

def main():
    res = [None] * (n + 1); res[0] = 0
    prev = '$'
    for i in range(1, n+1):
        res[i] = res[i-1]
        cur = s[i]
        res[i] += (prev == 'A' and cur == 'C') & 1
        prev = cur
    
    for l, r in lr:
        yield res[r] - res[l]

if __name__ == '__main__':
    ans = main()
    print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import sys

n, q = map(int, sys.stdin.readline().split())
s = '$' + sys.stdin.readline().rstrip()
lr = zip(*[map(int, sys.stdin.read().split())] * 2)

def main():
    res = [None] * (n + 1); res[0] = 0
    prev = '$'
    for i in range(1, n+1):
        res[i] = res[i-1]
        res[i] += (prev == 'A' and s[i] == 'C') & 1
        prev = s[i]
    
    for l, r in lr:
        yield res[r] - res[l]

if __name__ == '__main__':
    ans = main()
    print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
 
def main():
    N, Q = map(int, input().split())
    S = input().rstrip()
 
    cnt_ac = 0
    arr_ac = [0] * (N)
    for x in range(0, N-1):
        if S[x:x+2] == 'AC':
            cnt_ac += 1
        arr_ac[x+1] = cnt_ac
 
    for i in range(Q):
        L, R = map(int, input().split())
        print(arr_ac[R-1] - arr_ac[L-1])
 
 
main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
#coding: utf-8
import math
import heapq
import bisect
import numpy as np
#from scipy.misc import comb

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)

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

for i in range(Q):
    ans = rs[R[i]]-rs[L[i]]
    print(ans)

Submission status: Accepted

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

for _ in range(Q):
    l, r = map(int, input().split())
    if S[l-1:l+1] == 'AC':
        print(acm_cntAC[r] - acm_cntAC[l - 1] - 1)
    else:
        print(acm_cntAC[r] - acm_cntAC[l-1])

Submission status: Accepted

Solution code:
import sys


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

AC = [0] * N

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

LR = [map(int, x.split()) for x in sys.stdin.readlines()]

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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

AC = [0] * N

flag = 0
for i, s in enumerate(S):
    if s == 'C':
        if flag == 1:
            AC[i] = AC[i - 1] + 1
            flag = 0
        else:
            AC[i] = AC[i - 1]
            flag = 0
    elif s == 'A':
        AC[i] = AC[i - 1]
        flag = 1
    else:
        AC[i] = AC[i - 1]
        flag = 0


ans = [0] * Q
for q in range(Q):
    l, r = map(lambda x: int(x) - 1, input().split())
    ans[q] = AC[r] - AC[l]

for q in range(Q):
    print(ans[q])

Submission status: Accepted

Solution code:
from itertools import accumulate
n,q = map(int,input().split())
s = input()
a = [0] + [s[i-1:i+1] == 'AC' for i in range(1,n)]
acc = list(accumulate(a))

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import bisect
n,m = map(int,input().split())
l = list(input())
check = []
for i in range(n-1):
    if l[i] == "A" and l[i+1] == "C":
        check.append(i+1)
for i in range(m):
    a,b = map(int,input().split())
    left = bisect.bisect_left(check,a)
    right = bisect.bisect_left(check,b)
    print(right-left)

Submission status: Accepted

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

csm = [0]
cnt = 0

for i in range(n - 1):
	if s[i:i+2] == 'AC':
		cnt += 1
	csm.append(cnt)
	
for j in range(q):
	print(csm[ls[j][1] - 1] - csm[ls[j][0] - 1])

Submission status: Accepted

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

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

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