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 = list(input())
lr = [list(map(int,input().split())) for i in range(q)]
ans = [0]
x = 0

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

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

Submission status: Accepted

Solution code:
import bisect
n,q = map(int,input().split())
s = input()
acindex = []
for i in range(n-1):
	if s[i]=="A" and s[i+1]=="C":
		acindex.append(i+1)
for _ in range(q):
	l,r = map(int,input().split())
	count = bisect.bisect_left(acindex, r)-bisect.bisect_left(acindex, l)
	print(count)

Submission status: Accepted

Solution code:
def main():
    n, q = map(int, input().split())
    s = input()
    
    t = [0] * n
    pre = s[0]
    t_sum = 0
    for i in range(1, n):
        if pre == 'A' and s[i] == 'C':
            t[i] = t_sum + 1
            t_sum +=  1
        else: 
            t[i] = t_sum
        pre = s[i]
    for _ 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:
N, Q = map(int, input().split())
S = input()
queries = [tuple(map(int, input().split())) for _ in range(Q)]
counters = [0 for _ in range(N + 1)]
for idx, s in enumerate(S):
    counters[idx + 1] = counters[idx] + (1 if S[idx:idx + 2] == "AC" else 0)
for q in queries:
    l, r = q
    print(counters[r - 1] - counters[l - 1])

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def getN():
    return int(input())


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


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


from collections import defaultdict, deque
from sys import exit
import math
import copy
from bisect import bisect_left, bisect_right
from heapq import *
import sys

# sys.setrecursionlimit(1000000)
INF = 10 ** 17
MOD = 1000000007

from fractions import *


def inverse(f):
    # return Fraction(f.denominator,f.numerator)
    return 1 / f


def combmod(n, k, mod=MOD):
    ret = 1
    for i in range(n - k + 1, n + 1):
        ret *= i
        ret %= mod

    for i in range(1, k + 1):
        ret *= pow(i, mod - 2, mod)
        ret %= mod

    return ret

MOD = 998244353
def solve():
    n, q = getList()
    s = input().strip()
    acc = [0]
    tmp = 0
    pred = ""
    for c in s:
        if pred == "A" and c == "C":
            tmp += 1
        acc.append(tmp)
        pred = c

    for i in range(q):
        l, r = getList()
        print(acc[r] - acc[l])

def main():
    n = getN()
    for _ in range(n):
        solve()


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
#累積和的な

n,q = map(int,input().split())
s = input() + 'A' 
li = [0]*(n+1)

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
import fractions
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())[:-1]
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [list(input())[:-1] for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]

n,q=map(int,input().split())
s=list(input())[:-1]
lr = [list(map(int,input().split())) for _ in range(q)]
l=[0]*(n)
for i in range(1,n):
    if s[i]=='C' and s[i-1]=='A':
        l[i]=1
    else:
        l[i]=0
wa=[0]*(n)
for i in range(n):
    if i==0:
        wa[i]=0
    else:
        wa[i]=wa[i-1]+l[i]

for i in range(q):
    print(wa[lr[i][1]-1]-wa[lr[i][0]-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]
    if S[i -1: i +1] == "AC":
        T[i] += 1
for j in range(Q):
    l, r = map(int, input().split())
    print(int(T[r-1] - T[l-1]))

Submission status: Accepted

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

li = [0]*n

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

from itertools import accumulate

lin = [0]+list(accumulate(li))

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

Submission status: Accepted

Solution code:
from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
# 累積和
n,q = readInts()
Cum = [0] * (n+1)
S = input()
# 左にAがあるC
for i in range(1,n):
    if S[i-1] == 'A' and S[i] == 'C':
        Cum[i] += 1
for i in range(n):
    Cum[i+1] += Cum[i]
#print(Cum)
for k in range(q):
    l,r = readInts()
    l -= 1
    r -= 1
    print(Cum[r] - Cum[l])

Submission status: Accepted

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

Submission status: Accepted

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

mae = [0 for i in range(n)]
ato = [0 for i in range(n)]
bef = 'Z'
for i in range(n):
    if bef == 'A' and s[i] == 'C':
        mae[i-1] = -1
    bef = s[i]
bef = 'Z'
for i in range(n-1, -1, -1):
    if bef == 'C' and s[i] == 'A':
        ato[i+1] = -1
    bef = s[i]

for i in range(1, n):
    mae[i] += mae[i-1]
for i in range(n-2, -1, -1):
    ato[i] += ato[i+1]
num = -mae[-1]

ans = []
for i in range(q):
    li, ri = map(int, input().split())
    li, ri = li-1, ri-1
    minus = 0
    if li > 0:
        minus += mae[li-1]
    if ri < n-1:
        minus += ato[ri+1]
    ans.append(num+minus)

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

#print(count)

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

Submission status: Accepted

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

N, Q = map(int, input().split())
S = input()[:-1]
acc = [0]

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

acc.append(acc[-1])

for _ 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()

T = S.replace("AC","!?")

csum = [0]*N

s = 0

for i in range(N):
    if T[i] == "?":
        s += 1
    csum[i] = s

for i in range(Q):
    l,r = map(int,input().split())
    print(csum[r-1]-csum[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, groupby
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()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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

lis = [0]*(N+1)

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

lis = list(accumulate(lis))

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

Submission status: Accepted

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

counts = [0]
c = 0
for i, s in enumerate(S[1:]):
    if (S[i] == 'A') and (s == 'C'):
        c += 1
    counts.append(c)

ans = []
for _ in range(Q):
    l, r = map(int, input().split())
    ans.append(counts[r-1] - counts[l-1])
    #ans.append(S[l-1:r].count('AC'))

for a in ans:
    print(a)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = input()
query = [input().split() for i in range(Q)]
AC = [0 for i in range(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 = int(query[i][0]), int(query[i][1])
    print(AC[R-1] - AC[L-1])

Submission status: Accepted

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

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

for q 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()

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

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

import re

s = [i.span()[0] for i in list(re.finditer("AC", S))]
#print(s)

count = [0] * (N+1)
c = 0
for i in range(N):
    try:
        if s[0]+1 == i:
            s.pop(0)
            c += 1
    except:
        pass
            
    count[i] = c
    
#print(count)

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

print(" ".join(map(str, ans)))

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
n, q = 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] = 1

cac = [0]*(n+1)
for i in range(n):
    cac[i+1] = cac[i] + ac[i]

for i in range(q):
    l, r = map(int, input().split())
    ans = cac[r] - cac[l-1]
    if 0 <= l-1 and s[l-2:l]=='AC':
            if r+1 <= n and s[r-1:r+1]=='AC':
                ans-=2
    ans//=2
    print(ans)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#C
def f(x):
    return int(x) - 1

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)
# print(t)
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()
Q_lst = []
for i in range(Q):
    Q_lst.append(list(map(int,input().split())))

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

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

for q in Q_lst:
    left = q[0]-1
    right = q[1]-1
    print(ruiseki_lst[right] - ruiseki_lst[left])

Submission status: Accepted

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

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


count = [0]


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

# print(count)

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

Submission status: Accepted

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

ac = [0] * n
for i in range(n-1):
    if s[i] == "A":
        if s[i+1] == "C":
            ac[i+1] = 1
i = itertools.accumulate(ac)
ac = list(i)

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

for i in range(n-1):
  cnt+=s[i:i+2].count("AC")
  t[i+1]=cnt
##  t[-1]=cnt
##print(t)

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

Submission status: Accepted

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

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

#print(C)

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

  ans = C[r-1] - C[l-1]
  print(ans)

Submission status: Accepted

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

ac_index = [0]*n

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

for j in range(q):
    l = questions[j][0]-1
    r = questions[j][1]-1
    print(ac_index[r] - ac_index[l])

Submission status: Accepted

Solution code:
N,Q = map(int,input().split())
s = str(input())
LEN = len(s)
SUM = [0 for _ in range(N+1)]
for i in range(2,N+1):
  if s[i-2:i] == "AC":
    SUM[i] += SUM[i-1]+1
  else:
    SUM[i] = SUM[i-1]
#print(SUM)

for i in range(Q):
  l,r = map(int,input().split())
  ans = SUM[r]-SUM[l-1]
  if l >=2 and s[l-2:l] == "AC":
    ans -= 1
  print(ans)

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

Submission status: Accepted

Solution code:
import fractions
import sys
from functools import reduce
import math

input = sys.stdin.readline


def main():
    n, q = input_list()
    s = input()
    cumulative_sum = [0]
    i = 0
    for index, sv in enumerate(s):
        if index >= len(s)-1:
            continue
        if s[index] + s[index+1] == 'AC':
            i += 1
            cumulative_sum.append(i)
        else:
            cumulative_sum.append(i)
    for _ in range(q):
        l, r = input_list()
        print(cumulative_sum[r-1] - cumulative_sum[l-1])


def get_camulative(l):
    import itertools
    # 累積和
    return [0] + list(itertools.accumulate(l))

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


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


def input_list_str():
    return list(map(str, input().split()))


def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)


def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


def gcd(*numbers):
    return reduce(fractions.gcd, numbers)


def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,Q = map(int,input().split())
S = input()
left=[]
right=[]
for _ in range(Q):
  l,r = map(int,input().split())
  left.append(l)
  right.append(r)

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

#print(a)
ans = []
for j in range(Q):
  ans.append(a[right[j]-1] - a[left[j]-1])

for k in ans:
  print(k)

Submission status: Accepted

Solution code:
import numpy as np
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect


N, Q = list(map(int, input().split()))
S = input()
l = [0] * Q
r = [0] * Q
for i in range(Q):
    l_i, r_i = list(map(int, input().split()))
    l[i], r[i] = l_i-1, r_i-1
# 累積のACの数を数えて、引き算？
ruiseki_AC = [0] * N

for i in range(1, N):
    if S[i-1:i+1] == 'AC':
        ruiseki_AC[i] = ruiseki_AC[i-1] + 1
    else:
        ruiseki_AC[i] = ruiseki_AC[i-1]
# print("=======-")
for i in range(Q):
    # print('r', 'l', r[i], l[i])
    print(ruiseki_AC[r[i]] - ruiseki_AC[l[i]])

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
def main():
    n, q = map(int, readline().split())
    s = readline().rstrip().decode()
    ac = [0]    
    cnt = 0
    for i in range(1, n):
        if (s[i-1] == 'A') and (s[i] == 'C'):
            cnt += 1
            ac.append(cnt)
        else:
            ac.append(cnt)
    query = []
    for _ in range(q):
        l, r = map(int, readline().split())
        l -= 1
        r -= 1
        print(ac[r]-ac[l])
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
S = input()
piyo = False
work = [0]*n
i = 0
hoge = 0
for s in S:
    if s == "A":
        piyo = True
    elif s == "C" and piyo:
        hoge += 1
        piyo = False
    else:
        piyo = False
    work[i] = hoge
    i += 1
lr = [list(map(int, input().split())) for _ in range(q)]
for l, r in lr:
    result = work[r-1] - work[l-2] if l > 1 else work[r-1]
    if l>1 and S[l-2:l] == "AC":
        result -= 1
    print(result)

Submission status: Accepted

Solution code:

# 初期入力
import sys
input = sys.stdin.readline
N,Q = (int(x) for x in input().split())
S =input().strip()

# ACのindex(左端)
import re
import numpy as np
x =[m.start() for m in re.finditer('AC', S)]
#x =np.array(x)

import bisect
ans =[]
for i in range(Q):
    l1,r1 = (int(x) for x in input().split())
    l =bisect.bisect_left(x,l1-1)
    r =bisect.bisect_right(x,r1-2)  #"AC"のAの位置と比べるため－２
    ans.append(r -l)
print(*ans,sep="\n")

Submission status: Accepted

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

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

from itertools import accumulate 
B = list(accumulate(B))

for i in range(Q):
    print(B[L[i][1]-1] - B[L[i][0]-1 ])

Submission status: Accepted

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

for _ 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()
cumulative = [0] * (N+1)
for i in range(N-1):
  if S[i:i+2] == "AC":
    cumulative[i+2] = cumulative[i+1] + 1
  else:
    cumulative[i+2] = cumulative[i+1]
    
for _ in range(Q):
  start, end = map(int, input().split())
  ans = cumulative[end] - cumulative[start-1]
  if start > 1 and S[start-2:start] == "AC":
    ans -= 1
  print(ans)

Submission status: Accepted

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

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

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

print(*output, sep="\n")

Submission status: Accepted

Solution code:
# 初期入力
import sys
input = sys.stdin.readline
N,Q = (int(x) for x in input().split())
S =input().strip()
l =[]
r =[]
for i in range(Q):
    l1,r1 = (int(x) for x in input().split())
    l.append(l1 -1) #indexは０始まりだからー１
    r.append(r1 -1) #"AC"のAの位置と比べるため－２

# ACのindex(左端)
import re
import numpy as np
index =0
t =[0]*N

for i in range(N-1):
    t[i+1] = t[i] +np.count_nonzero(S[i:i+2] =="AC")

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

Submission status: Accepted

Solution code:
import bisect

n, q = map(int, input().split())
S = str(input())
L = []
for i in range(n-1):
    if S[i] + S[i+1] == 'AC':
        L.append(i+1)
for _ in range(q):
    l, r = map(int, input().split())
    s = bisect.bisect_left(L, l)
    t = bisect.bisect_left(L, r)
    print(t - s)

Submission status: Accepted

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

    # ruiseki
    rui = [0]*(n+1)
    for i in range(n):
        if i < n-1:
            if s[i] == 'A' and s[i+1] == 'C':
                rui[i+1] = rui[i]+1
            else:
                rui[i+1] = rui[i]

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
 
N, Q = map(int, input().split())
 
S = input()
 
ac = np.zeros(N)
count = 0
for i in range(N):
  ac[i] = count
  if S[i:i+2] == 'AC':
    count += 1
#print(ac)
for i in range(Q):
  l, r = map(int, input().split())
  print(int(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] + (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 = str(input())

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

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

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

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

Submission status: Accepted

Solution code:
import numpy as np
n, q = map(int, input().split())
s = input()
ans = np.zeros(n, dtype=int)

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

ans = ans.cumsum()

result = []

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

print(*result, sep="\n")

Submission status: Accepted

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

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

  #if s[i-1] == "A":
  #  if s[i] == "C":
  #    a[i] = a[i-1]+1
  #else:
  #  a[i] = a[i-1]

#print(a)
for i in range(q):
  b, c = list(map(int, input().split()))
  print(a[c-1]-a[b-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 = input()
l, r = [0]*q, [0]*q
for i in range(q):
    l[i], r[i] = map(int, input().split())

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

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

Submission status: Accepted

Solution code:
import bisect
n, q = map(int, input().split())
s = str(input())
A, C = [], []
for i in range(n - 1):
    if s[i] == 'A' and s[i + 1] == 'C':
        A.append(i)
        C.append(i + 1)
for i in range(q):
    l, r = map(int, input().split())
    print(bisect.bisect_right(C, r - 1) - bisect.bisect_left(A, l - 1))

Submission status: Accepted

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

a = [0 for i in range(N)]
b = [0 for i in range(N)]

for i in range(N-1):
  if S[i] == "A" and S[i+1] == "C":
    a[i] = 1
    b[i+1] = 1
    
def cumsum(xs):
  result = [xs[0]]
  for x in xs[1:]:
    result.append(result[-1] + x)
  result.append(0)
  result.sort()
  return result

A = cumsum(a)
B = cumsum(b)

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

Submission status: Accepted

Solution code:
ii = lambda:int(input())
mi = lambda:list(map(int,input().split()))
ix = lambda x:list(input() for _ in range(x))
mix = lambda x:list(mi() for _ in range(x))
iix = lambda x:list(int(input()) for _ in range(x))
##########
def main(n,q,s,l):
    lst_ac = [0]*(len(s))
    for i in range(len(s)-1):
        if s[i]+s[i+1] == "AC":
            lst_ac[i+1] = lst_ac[i]+1
        else:
            lst_ac[i+1] = lst_ac[i]
    for item in l:
        print(lst_ac[item[1]-1] - lst_ac[item[0]-1])

def resolve():
    n,q = mi()
    s = input()
    l = mix(q)
    main(n,q,s,l)

if __name__ == "__main__":
    resolve()