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:
import sys
import math
import itertools
import collections
import heapq
import re
import numpy as np
from functools import reduce

rr = lambda: sys.stdin.readline().rstrip()
rs = lambda: sys.stdin.readline().split()
ri = lambda: int(sys.stdin.readline())
rm = lambda: map(int, sys.stdin.readline().split())
rl = lambda: list(map(int, sys.stdin.readline().split()))
inf = float('inf')
mod = 10**9 + 7

n, q = rm()
s = rr()
cnt_li = [0]*n
for i in range(n-1):
    if s[i:i+2] == 'AC':
        cnt_li[i+1] += 1
    cnt_li[i+1] += cnt_li[i]
for _ in range(q):
    l, r = rm()
    print(cnt_li[r-1] - cnt_li[l-1])

Submission status: Accepted

Solution code:
import re
import sys
from collections import *
from functools import lru_cache
from heapq import *
from itertools import *
from statistics import *
from string import (
    ascii_letters as letters,
    ascii_lowercase as lcletters,
    ascii_uppercase as ucletters,
    digits
)

xdigits='01234567890ABCDEFabcdef'
inf=float('inf')
bigi=2**31-1

cache=lru_cache(None)

sys.setrecursionlimit(bigi)

rfs=lambda:rl().split()
ri=lambda:int(rl())
ris=lambda:list(map(int,rfs()))
rl=lambda:next(sys.stdin)
rrs=lambda:list(map(str.strip,sys.stdin))
rs=lambda:rl().strip()
rt=lambda:sys.stdin.read()
rg=lambda:list(map(list,rrs()))
rig=lambda:[[*map(int,x.split())] for x in rls()]

def nbs4(i,j):
    return [
                (i-1,j),
        (i,j-1),        (i,j+1),
                (i+1,j),
    ]

def nbs8(i,j):
    return [
        (i-1,j-1),(i-1,j),(i-1,j+1),
        (  i,j-1),        (  i,j+1),
        (i+1,j-1),(i+1,j),(i+1,j+1),
    ]

inb=lambda i,j,m,n:0<=i<m and 0<=j<n

###########################################

N,Q=ris()
S=rs()
a=[0]*(N+1)
for i in range(1,N):
    if S[i-1]=='A' and S[i]=='C':
        a[i+1]+=1
    a[i+1]+=a[i]
for _ in range(Q):
    l,r=ris()
    print(a[r]-a[l])

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = input()
L = [0]*n

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

L = [0]+L
for i in range(n):
    L[i+1] += L[i]
#print(L)
for i in range(k):
    c,d = map(int,input().split())
    print(L[d-1]-L[c-1])

Submission status: Accepted

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

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

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

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

for x in lr:
    print(acli[x[1]-1]-acli[x[0]-1])

Submission status: Accepted

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
s = input()
lr = [list(map(int, input().split())) for i in range(q)]
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):
    print(t[lr[i][1]-1] - t[lr[i][0]-1])

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left, bisect_right


stdin = sys.stdin
def ns(): return stdin.readline().rstrip()
def ni(): return int(stdin.readline().rstrip())
def nm(): return map(int, stdin.readline().split())
def nl(): return list(map(int, stdin.readline().split()))


def main():
    n, q = nm()
    S = input()
    ans = []
    A_pos = []
    C_pos = []
    for i in range(n - 1):
        if S[i] == 'A' and S[i + 1] == 'C':
            A_pos += [i + 1]
            C_pos += [i + 2]
    for i in range(q):
        l, r = nm()
        ans += [bisect_right(C_pos, r) - bisect_left(A_pos, l)]
    print(*ans, sep='\n')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

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

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

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

for l, r in lrL:
    print(li[r - 1] - li[l - 1])

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
S = input()
lr = []
s = [0]*(n+1)
count = 0

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

for i in range(n-1):
    if S[i:i+2] == "AC":
        count += 1
        s[i+1] = count
    else:
        s[i+1] = s[i]
        
for i in range(q):
    print(s[lr[i][1] - 1] - s[lr[i][0] - 1])

Submission status: Accepted

Solution code:
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

N,Q = MI()
S = LS2()
A = [0]*N

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

from itertools import accumulate

A = list(accumulate(A))

for i in range(Q):
    l,r = MI()
    print(A[r-1]-A[l-1])

Submission status: Accepted

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

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

H=[0]*Q
for k in range(Q):
    X,Y=map(int,input().split())
    H[k]=T[Y]-T[X-1]-U[X]
print("\n".join(map(str,H)))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def solve():
  ans = 0
  N, Q = map(int, input().split())
  S = input()
  plus = [0]*N
  for i in range(1,N):
    plus[i] = plus[i-1]
    if S[i-1:i+1]=='AC':
      plus[i]+=1
  ans = [0]*Q
  for i in range(Q):
    x,y = map(int, input().split())
    ans[i] = plus[y-1]-plus[x-1]
  return ans
print(*solve(),sep='\n')

Submission status: Accepted

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

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

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

Submission status: Accepted

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

ac_counter = [0] * n
counter = 0
for i in range(n - 1):
    # ac_counter[i] = counter
    if s[i:i+2] == "AC":
        counter += 1
    ac_counter[i + 1] = counter

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
from itertools import accumulate #list(accumulate(A))

N, Q = mi()
S = input()
lr = li2(Q)

num = [0] * N

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

num = [0] + list(accumulate(num))

for s, t in lr:
    print(num[max(t-1, 0)]-num[max(s-1, 0)])

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:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

N, Q = getNM()
S = input()
que = [getList() for i in range(Q)]
imos = [0] * N
for i in range(N - 1):
    if S[i + 1] == 'C' and S[i] == 'A':
        imos[i + 1] += imos[i] + 1
    else:
        imos[i + 1] += imos[i]

imos = [0] + imos
for l, r in que:
    opt = imos[r] - imos[l - 1]
    # 修正入る
    if l >= 2 and S[l - 1] == 'C' and S[l - 2] == 'A':
        opt -= 1
    print(opt)

Submission status: Accepted

Solution code:
from typing import List


def query(S: List[str], l: int, r: int) -> int:
    return ac[r - 1] - ac[l - 1]


if __name__ == "__main__":

    N, Q = [int(x) for x in input().split(" ")]
    S = list(input())

    ac = [0]
    count = 0
    for i, s in enumerate(S):
        if i == 0:
            continue

        if S[i - 1] == "A" and S[i] == "C":
            count += 1

        ac.append(count)

    for _ in range(Q):
        l, r = [int(x) for x in input().split(" ")]
        print(query(S, l, r))

Submission status: Accepted

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

accs = [0]
for i in s:
    accs.append(accs[-1] + (i == '.'))
for l, r in lr:
    print(accs[r] - accs[l])

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = input()
qn = [list(map(int, input().split())) for _ in range(Q)]
S = "0" + S
cnt = [0 for _ in range(N+1)]
# cnt.append(0)
for i in range(1, N+1):
    if (S[i-1:i+1] == "AC"):
        cnt[i] = cnt[i-1] + 1
    else:
        cnt[i] = cnt[i-1]
for q in qn:
    l, r = q
#     print(l, cnt[l-2], r, cnt[r-1])
    print(cnt[r] - cnt[l])

Submission status: Accepted

Solution code:
from itertools import accumulate
n,q=list(map(int,input().split()))
s=list(input())
l=[]
r=[]
for i in range(q):
  o,p=list(map(int,input().split()))
  l.append(o)
  r.append(p)
  
ruiseki=[]
for i in range(n-1):
  if s[i]=="A" and s[i+1]=="C":
    ruiseki.append(1)
  else:
    ruiseki.append(0)
ruiseki=[0]+list(accumulate(ruiseki))

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

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = input()
qn = [list(map(int, input().split())) for _ in range(Q)]
S = "0" + S
cnt = []
cnt.append(0)
for i in range(1, N+1):
    if (S[i-1:i+1] == "AC"):
        cnt.append(cnt[i-1] + 1)
    else:
        cnt.append(cnt[i-1])
for q in qn:
    ans = cnt[q[1]] - cnt[q[0]-1]
    if S[q[0]-1:q[0]+1] == "AC":
        ans -= 1
    print(ans)

Submission status: Accepted

Solution code:
#! python3
#  solve_122C.py

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

t = [0]*(N+1) #ACの内Aの番号を格納(?番目形式)

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

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

Submission status: Accepted

Solution code:
import sys

N, Q = map(int, input().split())
S = input()
s = [0]
for i, c in enumerate(S):
    if i == 0:
        s.append(0)
    elif S[i-1] == 'A' and S[i] == 'C':
        s.append(s[-1] + 1)
    else:
        s.append(s[-1])

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

Submission status: Accepted

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

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


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

Submission status: Accepted

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

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 LR:
    l, r = i[0], i[1]
    print(t[r-1] - t[l-1])

Submission status: Accepted

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

Submission status: Accepted

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

memo = [0] * (n+1)


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

for l,r in l_r:
    print(memo[r-1]-memo[l-1])

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n, Q = map(int, input().split())
s = input()
q = [[*map(int, input().split())] for _ in range(Q)]
R = [0]
for i in range(n - 1):
    R.append(R[-1] + (s[i:i + 2] == "AC"))
for l, r in q:
    print(R[r-1]-R[l-1])

Submission status: Accepted

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

# In[15]:


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


# In[ ]:

Submission status: Accepted

Solution code:
import bisect
N, Q = list(map(int, input().split()))
S = input()
R = [0] * Q
V = []
Vp = V.append
for i in range(N - 1):
    if S[i:i+2] == 'AC':
        Vp(i)
for i in range(Q):
    l, r = list(map(int, input().split()))
    if len(V) > 0:
        l -= 1
        r -= 1
        low = bisect.bisect_left(V, l)
        up = bisect.bisect_right(V, r - 1) - 1
        R[i] = up - low + 1
    else:
        R[i] = 0
print('\n'.join(list(map(str, R))))

Submission status: Accepted

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

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

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

    cnt_lst.append(cnt)


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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect
n,q=map(int,input().split())
s=input()
a=[]
for i in range(n-1):
  if s[i:i+2]=='AC':
    a.append(i)
for _ in range(q):
  l,r=map(int,input().split())
  print(bisect.bisect(a,r-1.5)-bisect.bisect(a,l-1.5))

Submission status: Accepted

Solution code:
import math
import sys
import collections
import bisect
readline = sys.stdin.readline


def main():
    n, q = map(int, readline().rstrip().split())
    s = readline().rstrip()
    LRList = [list(map(int, readline().rstrip().split())) for _ in range(q)]
    sumAC = 0
    ACList = [0] * (n)
    for i in range(1, n):
        if s[i - 1: i + 1] == 'AC':
            sumAC += 1
        ACList[i] = sumAC
    for j in range(q):
        l, r = LRList[j][0], LRList[j][1]
        print(ACList[r-1] - ACList[l-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
N,Q = map(int,input().split())
S = input()
T = (N+1)*[0]

for n in range(N):
  if S[n:n+2]=="AC":
    T[n+1]+=1

T = np.cumsum(T)

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()
lr = [list(map(int,input().split())) for _ in range(Q)]

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

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

Submission status: Accepted

Solution code:
from itertools import accumulate

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

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

a = [0] + list(accumulate(t))
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 = map(int, input().split())
s = input()
keep = [0]*(n)

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

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

Submission status: Accepted

Solution code:
import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def v(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")

n,q=I()
s = v()
t = [0]*(n+1)
for i in range(n):
    t[i+1]=t[i]+(1 if s[i:i+2]=="AC" else 0)

ans = []
for i in range(q):
    l,r=I()
    ans.append(t[r-1]-t[l-1])
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
S = input()
CS = [0]
cur = 0
for i in range(1, n):
    if S[i-1] + S[i] == 'AC':
        cur += 1
        CS.append(cur)
    else:
        CS.append(cur)

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

Submission status: Accepted

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

#累積和
dp=[0 for _ in range(N)]
for n in range(1,len(S)):
    if S[n]=="C" and S[n-1]=="A":
        dp[n]=dp[n-1]+1
    else:
        dp[n]=dp[n-1]

#部分和の算出
for q in range(Q):
    print(dp[lr[q][1]-1]-dp[lr[q][0]-1])

Submission status: Accepted

Solution code:
from itertools import accumulate
N, Q = map(int,input().split())
S = input()
A = [list(map(int,input().split())) for q in range(Q)]
#print(A)

#フラグを立てて累積和で高速化
flg = []
for n in range(N-1):
    tmp_s = S[n:n+2]
    if tmp_s == "AC":
        flg.append(1)
    else:
        flg.append(0)

flg2 = [0] + flg
flg2 = list(accumulate(flg2))
#print(flg2)

for a in A:
    print(flg2[a[1]-1] - flg2[a[0]-1])

Submission status: Accepted

Solution code:
N,Q=map(int,input().split())
S=input()
L=[]
R=[]
for i in range(Q):
    LR=list(map(int,input().split()))
    L.append(LR[0]-1)
    R.append(LR[1]-1)

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

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

Submission status: Accepted

Solution code:
def resolve():
    '''
    code here
    '''
    N, Q = [int(item) for item in input().split()]
    S = input()
    queries = [[int(item) for item in input().split()] for _ in range(Q)]

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

    prev = S[0]
    for i in range(1, N):
        memo[i] = memo[i-1]
        if S[i] == 'C' and prev == 'A':
            memo[i] += 1
        prev = S[i]
    
    for l, r in queries:
        print(memo[r-1] - memo[l-1])




if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
from itertools import accumulate
N, Q = map(int,input().split())
S = input()
AC = [0]*N
flag = 0
for idx, s in enumerate(S):
    if flag and s == "C":
        AC[idx] = 1
    if s == "A":
        flag = 1
    else:
        flag = 0

acc = list(accumulate(AC))

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

Submission status: Accepted

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

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

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

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

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

for l, r in question:
    ans = nums[r] - nums[l]
    print(ans)

Submission status: Accepted

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

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

def cumulative_sum(collection):
    result = [0]
    for item in collection:
        result.append(result[-1] + item)
    return result
csml = cumulative_sum(ml)

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

Submission status: Accepted

Solution code:
n,q = map(int, input().split())
s=input()
a=[0]*n
for i in range(1,n):
    a[i]+=a[i-1]
    if s[i-1]=='A' and s[i]=='C':
        a[i]+=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=map(int,input().split())
s=input()
l,r=[],[]
c=[0]*(n+1)
for i in range(q):
    a,b=map(int,input().split())
    l.append(a)
    r.append(b)
t=0
for i in range(n-1):
    if  s[i]=="A" and s[i+1]=="C":
        t+=1
    c[i+1]=t
c[n]=c[n-1]
c.append(c[n])
for i in range(q):
    print(c[r[i]-1]-c[l[i]-1])

Submission status: Accepted

Solution code:
N,Q=map(int,input().split())
S=list(input())
answers=[0 for _ in range(N)]
for n in range(1,N):
    if S[n]=='C':
        if S[n-1]=='A':
            answers[n]=answers[n-1]+1
        else:
            answers[n]=answers[n-1]
    else:
        answers[n]=answers[n-1]


for _ in range(Q):
    l,r=map(int,input().split())
    print(answers[r-1]-answers[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:
import sys
input=sys.stdin.readline
n,q=map(int,input().split())
s=input()
a=[0]*n
for x in range(1,n):
  a[x]+=a[x-1]
  if s[x-1]=='A' and s[x]=='C':
    a[x]+=1
  
    
for y in range(q):
  
  l,r=map(int,input().split())
  ans=a[r-1]-a[l-1]
  print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import copy

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

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

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

Submission status: Accepted

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

ans = 0
ans_ls = []
ans_ls.append(0)

for n in range(N-1):
  if S[n] == "A" and S[n+1] =="C":
    ans += 1
  ans_ls.append(ans)

for q in range(Q):
  print(ans_ls[lr[q][1]-1]-ans_ls[lr[q][0]-1])

Submission status: Accepted

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

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

for q in quiz:
  l = q[0]
  r = q[1]
  print(t[r-1] - t[l-1])

Submission status: Accepted

Solution code:
N, Q=map(int, input().split())
S=input()
count=0
ac=[0]
for i in range(N-1):
  if S[i]=="A" and S[i+1]=="C":
    count+=1
  ac.append(count)
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=list(input())
sum=[0]*n

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

Submission status: Accepted

Solution code:
import bisect
n,q=map(int,input().split())
s=list(input())
former_list=[]
latter_list=[]

for i in range(n-1):
    if s[i]=="A" and s[i+1]=="C":
        former_list.append(i+1)
        latter_list.append(i+2)
for j in range(q):
    l,r=map(int,input().split())
    start=bisect.bisect_left(former_list,l)
    end=bisect.bisect_right(latter_list,r)
    print(end-start)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n, q = [int(w) for w in input().split()]

s = input()
c_ac = [0]*(len(s)+1)

is_p_c = False
for i in range(len(s)-1, -1, -1):
    if s[i] == "A"and is_p_c:
        c_ac[i] = c_ac[i+1]+1
    else:
        c_ac[i] = c_ac[i+1]
    if s[i] == "C":
        is_p_c = True
    else:
        is_p_c = False


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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque, defaultdict
from math import sqrt, factorial, gcd
# def input(): return sys.stdin.readline()[:-1] # warning not \n
# def input(): return sys.stdin.buffer.readline().strip() # warning bytes
# def input(): return sys.stdin.buffer.readline().decode('utf-8')


def solve():
    n, q = [int(x) for x in input().split()]
    s = input()
    a = [0] * n
    b = [0] * n
    for i in range(n-1):
        if s[i:i+2] == 'AC':
            a[i] = 1
        b[i] = a[i]
        if i:
            b[i] += b[i-1]
    for _ in range(q):
        l, r = [int(x) for x in input().split()]
        l -= 1
        r -= 1
        ans = b[r-1]
        if l:
            ans -= b[l-1]
        print(ans)
    
    

        
    
t = 1
# t = int(input())
for case in range(1,t+1):
    ans = solve()


"""

R s
S p
P r

"""

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
s=input()
ans_l=[0]*n
for i in range(n-1):
    tmp=s[i]+s[i+1]
    if tmp=='AC':
        ans_l[i+1]=ans_l[i]+1
    else:
        ans_l[i+1]=ans_l[i]
for i in range(q):
    l,r=map(int,input().split())
    print(ans_l[r-1]-ans_l[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)]
wa = [0,0]
num = 0
for i in range(2,N+1):
  if S[i-2:i] == "AC":
    num += 1
  wa.append(num)
left = 0
right = 0
for i in range(Q):
  left = lr[i][0]
  right = lr[i][1]
  print(wa[right]-wa[left])

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = input()
S = S.replace("AC", "XX")
acc = [0] * (N + 1)
i = 0
while i < N:
    if S[i] == "X":
        acc[i + 2] = 1 
        i += 2
    else:
        i += 1
for i in range(1, N + 1):
    acc[i] += acc[i - 1]

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

Submission status: Accepted

Solution code:
import sys
import math


def input():
    return sys.stdin.readline().rstrip()


def main():
    N, Q = map(int, input().split())
    S = list(input())
    t = [0] * N
    count =0
    for i in range(1,N):
        if S[i-1]=="A" and S[i] =="C":
            count +=1
        t[i] =count

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

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

#C:1(左がAの場合)
flag=[0]*N
for i in range(1,N):
    if S[i]=='C' and S[i-1]=='A':
        flag[i]=1

#t = 1からiまでのAC出現回数
t=[0]
for i in range(1,N):
    t.append(t[-1] + flag[i])
# print('flag, t:', flag, t)

#Qに答えていく
for i in range(Q):
    print(t[lr[i][1]-1] - t[lr[i][0]-1])

Submission status: Accepted

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

def main():
    n, q = map(int, input().split())
    s = list(input())
    lr = [list(map(int, input().split())) for _ in range(q)]
    ac = [0] * len(s)
    for i in range(1, len(s)):
        if s[i-1]=='A' and s[i]=='C':
            ac[i] = ac[i-1] + 1
        else:
            ac[i] = ac[i-1]
    for i in lr:
        print(ac[i[1]-1]-ac[i[0]-1])
            
if __name__ == '__main__':
    main()