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 numpy as np
from collections import Counter
import collections
import numpy as np 
from scipy import sqrt, power, exp, log10
from scipy.fftpack import fft, ifft, fftfreq
import tarfile
import re
import os
import glob
from datetime import datetime
import time
import numpy.linalg as LA

round = lambda x:(x*2+1)//2
a,b = list(map(int,input().split()))
S = input()
sub= "AC"
l = np.zeros(len(S)+1)
for i in range(len(S)):
  l[i+1] = l[i] + (1 if S[i:i+2]=="AC" else 0)

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
C - GeT AC
https://atcoder.jp/contests/abc122/tasks/abc122_c
AC
"""
import sys


def main(args):
    N, Q = map(int, input().split())
    S = input()
    ans = [0] * (N + 1)
    for i, a, c in zip(range(2, N), S, S[1:]):
        ans[i] = ans[i-1] + (a == 'A' and c == 'C')
    ans[-1] = ans[-2] + (S[-2:] == 'AC')

    # ans_d = {i:n for i, n in enumerate(ans)}
    for _ in range(Q):
        l, r = map(int, input().split())
        print(ans[r] - ans[l])


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
C - GeT AC
https://atcoder.jp/contests/abc122/tasks/abc122_c
WA
"""
import sys


def main(args):
    N, Q = map(int, input().split())
    S = input()
    ans = [0] * (N + 1)
    for i, a, c in zip(range(2, N), S, S[1:]):
        ans[i] = ans[i-1] + (a == 'A' and c == 'C')
    ans[-1] = ans[-2] + (S[-2:] == 'AC')

    ans_d = {i:n for i, n in enumerate(ans)}
    for _ in range(Q):
        l, r = map(int, input().split())
        print(ans_d[r] - ans_d[l])


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
N,Q=map(int,input().split())
S=input()
t=[0,0]
for i in range(2,N+1):
    t.append(t[-1]+(S[i-2:i]=='AC'))
for _ in range(Q):
    l,r=map(int,input().split())
    print(t[r]-t[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()

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()
num = [list(map(int, input().split())) for i in range(q)]
arr = [0]
tmp = 0
for i in range(n):
    if s[i:i+2] == 'AC':
        tmp += 1
    arr.append(tmp)

for left, right in num:
    ans = arr[right - 1] - arr[left - 1]
    print(ans)

Submission status: Accepted

Solution code:
N, Q = list(map(int, input().split()))
S = input()
l = [0] * Q
r = [0] * Q
for x in range(Q):
    l[x], r[x] = list(map(int, input().split()))

countAC = [0] * len(S)
for x in range(len(S) - 1):
    countAC[x + 1] = countAC[x]
    if S[x] == "A" and S[x + 1] == "C":
        countAC[x + 1] += 1
for x in range(Q):
    print(countAC[r[x] - 1] - countAC[l[x] - 1])

Submission status: Accepted

Solution code:
# クエリが複数回与えられて、毎回のクエリに対する回答をする必要がある
# という時点で累積和を意識するべきだった……

# 競技中に一瞬思いついたが、10万の配列を作ったときにメモリが足りるかを懸念して避けてしまった
# 10万くらいなら余裕で足りるよ

# printしてみた配列の大きさ：
# 提出時の表示： 実行時間とメモリ 878 ms	6104 KB https://atcoder.jp/contests/abc122/submissions/4758777

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

cumsum = [0] * N
# cumsum[i] := (0-indexで)0文字目からi文字目までに含まれる部分列"AC"の個数
# (0-indexで)l文字目からr文字目までに含まれる部分列"AC"の個数は、cumsum[r] -cumsum[l]である
# l-1文字目とl文字目が"AC"になるケースも除外したいので、cumsum[l]を引くこと

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

for _ in range(Q):
	left, right = map(int, input().split())
	left -= 1 # 1-indexから0-indexに変更する
	right -= 1
	print(cumsum[right] - cumsum[left])

Submission status: Accepted

Solution code:
# クエリが複数回与えられて、毎回のクエリに対する回答をする必要がある
# という時点で累積和を意識するべきだった……

# 競技中に一瞬思いついたが、10万の配列を作ったときにメモリが足りるかを懸念して避けてしまった
# 10万くらいなら余裕で足りるよ

# printしてみた配列の大きさ：
# 提出時の表示： URLを張る

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

cumsum = []
# cumsum[i] := (0-indexで)0文字目からi文字目までに含まれる部分列"AC"の個数
# (0-indexで)l文字目からr文字目までに含まれる部分列"AC"の個数は、cumsum[r] -cumsum[l]である
# l-1文字目とl文字目が"AC"になるケースも除外したいので、cumsum[l]を引くこと

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

for _ in range(Q):
	left, right = map(int, input().split())
	left -= 1 # 1-indexから0-indexに変更する
	right -= 1
	print(cumsum[right] - cumsum[left])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect

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

start = []
# end = []

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

length = len(start)
for _ in range(Q):
	left, right = map(int, input().split())
	left -= 1
	right -= 1

	if length == 0:
		print(0)
	else:
		# startの中で、left以上であるものの最小インデックス

		l1 = bisect.bisect_left(start, left)
#		r1 = bisect.bisect_right(end, right) - 1
		r1 = bisect.bisect_right(start, right-1) - 1

		print (r1-l1+1)

'''

	r = length
	l = 0
	c = int((r+l)//2)
	while(l<r):

		if start[c] >= left:
			r = c
			c = int((r+l)//2)
		else:
			l = c
			c = int((r+l)//2)

	X1 = c

	# endの中で、right以下であるものの最大インデックス
	r = length
	l = 0
	c = int((r+l)//2)
	while(l<r):

		if end[c] > right:
			r = c
			c = int((r+l)//2)
		else:
			l = c
			c = int((r+l)//2)

	X2 = c

	print(X2-X1+1)
'''

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
s = str(input())
ls = [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):
    l, r = ls[i][0], ls[i][1]
    ans = t[r - 1] - t[l - 1]
    print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

for fromto in fromtos:
  print(counts[fromto[1]-1] - counts[fromto[0]-1])

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,q = li()
s = lc()

cnt = [0]*(n)

for i in range(1,n):
    if s[i-1] == "A" and s[i] == "C":
        cnt[i] = cnt[i-1] + 1
    else:
        cnt[i] = cnt[i-1]
        
for _ in range(q):
    l,r = li_()
    print(cnt[r]-cnt[l])

Submission status: Accepted

Solution code:
N, Q = map(int,input().split())
S = input()
LRlist = []
for i in range(Q):
    LRlist.append(list(map(int,input().split())))
t = [0] * (N + 1)
for i in range(N):
    t[i+1] = t[i] + (1 if S[i:i+2] == 'AC' else 0) #t[i]=i文字目までのACのAの数：累積和
for LR in LRlist:
     L = LR[0]
     R = LR[1]
     print(t[R-1] - t[L-1])

Submission status: Accepted

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

N, Q = [int(x) for x in input().split()]
S = input().strip()
m = [0] * N
for i in range(1, N):
    if S[i-1:i+1] == 'AC':
        m[i] = m[i-1] + 1
    else:
        m[i] = m[i-1]

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

Submission status: Accepted

Solution code:
word_number, questions_number = map(int, input().split())
# words = list(input())
words = input()
questions = []
for question in range(questions_number):
    a,b = map(int, input().split())
    questions.append([a-1, b-1])

# 複数回の問題を2秒以内はきついので前処理する必要あり
# for i in range(len(questions)):
#     counter = 0
#     for j in range(questions[i][0], questions[i][1]):
#         # if words[j] == "A" and words[j+1] == "C":
#         if words[j: j+2] == "AC":
#             counter += 1
#     print(counter)

hasAC = [0] * word_number
for i in range(word_number-1):
    if words[i: i+2] == "AC":
        hasAC[i+1] = hasAC[i] + 1
    else:
        hasAC[i+1] = hasAC[i]

for i in range(questions_number):
    print(hasAC[questions[i][1]] - hasAC[questions[i][0]])

Submission status: Accepted

Solution code:
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)
#print(l, r)

total_list = []
total=0
S = ' ' + S
for i in range(1, len(S)):
  if S[i-1] + S[i] == "AC":
    total += 1
  total_list.append(total)
#print(total_list)
for j in range(Q):
  num_r = total_list[r[j]-1]
  num_l = total_list[l[j]-1]
  num = num_r - num_l
  print(num)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
# 累積和を使う
N, Q = map(int, input().split())  #長さN, Q個の問い

S = str(input())  # 長さNの文字列S(これはA, C, G, Tのいずれかの文字のみ)

starts_ends = []
# 始点lと終点rがQセット与えられる
for _ in range(Q):
    starts_ends.append(list(map(int, input().split())))

# print('hoge')
# print(N)
# print(Q)
# print(S)
# print(starts_ends)

# 'AC'を探す旅に出る
cumulative_sum = [0, 0]
for i in range(1, len(S)):
    if S[i] == 'C' and S[i-1] == 'A':
        cumulative_sum.append(cumulative_sum[i]+1)
    else:
        cumulative_sum.append(cumulative_sum[i])

for i in range(Q):
    start, end = starts_ends[i]
    print(cumulative_sum[end] - cumulative_sum[start])

Submission status: Accepted

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

#cnts = [S[:i].count("AC") for i in range(1,N+1)]
cnts = [0]*N

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



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

Submission status: Accepted

Solution code:
N, Q = map(int, raw_input().split())
S = raw_input()
count = 0
ac_list = list()
ac_list.append(0)
for idx in range(1, N):
    if S[idx-1] == 'A' and S[idx] == 'C': count += 1
    ac_list.append(count)
for i in xrange(Q):
    left, right = map(int, raw_input().split())
    print (ac_list[right-1] - ac_list[left-1])
# print ac_list

Submission status: Accepted

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

for i in range(1,n):
    li[i+1] = li[i] + s[i-1:i+1].count("AC")

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import bisect

n, q = [int(x) for x in input().split()]
s = input()

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

for i in range(q):
    l, r = [int(x) for x in input().split()]
    print(bisect.bisect_right(index, r-2) - bisect.bisect_left(index, l-1))

Submission status: Accepted

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N, Q = map(int, input().split())
s = input()[:-1]
acc = [0]*(N+1)
prev = ""
for i, c in enumerate(s):
    if c == "C" and prev == "A":
        prev = c
        acc[i+1] = 1
    else:
        prev = c
for i in range(len(acc)-1):
    acc[i+1] += acc[i]
ans = []
for _ in range(Q):
    l, r = map(int, input().split())
    ans.append(acc[r]-acc[l])
for a in ans:
    print(a)

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
s = input()
num_list = list()
#０文字目と１文字目はACの数０
ruisekiwa_tabun_rikaidekita = [0,0]

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

for i in range(n-1):
    if s[i:i+2] == "AC":
        ruisekiwa_tabun_rikaidekita.append(ruisekiwa_tabun_rikaidekita[-1] + 1)
    else:
        ruisekiwa_tabun_rikaidekita.append(ruisekiwa_tabun_rikaidekita[-1])
        
for left,right in num_list:
    print(ruisekiwa_tabun_rikaidekita[right] - ruisekiwa_tabun_rikaidekita[left])

Submission status: Accepted

Solution code:
# [参照先] https://img.atcoder.jp/abc122/editorial.pdf
# 累積和を用いる
n, q = map(int, input().split())
s = input()  # 長さnの文字列

t = [0] * (n + 1)
# ACが出るのは2文字目から
for i in range(1, n):
    t[i + 1] = t[i] + (1 if s[i - 1:i + 1] == 'AC' else 0)
for i in range(q):
    l, r = map(int, input().split())
    print(t[r] - t[l])

# わからなくなったら図を書く
# 0 1 2 3 4 5 6 7 8  (tの添字の位置)
# 0 0 1 1 2 2 2 3 3
#  A C A C T A C G
#  1 2 3 4 5 6 7 8   (r, lは1スタート)

# 入力例
# 8 3
# ACACTACG
# 3 7
# 2 3
# 1 8

# 出力例
# 2
# 0
# 3

Submission status: Accepted

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

counter = 0
lis = [0]*len(s)
for i in range(len(s)-1):
    if s[i:i+2] == 'AC':
        counter+=1
    lis[i+1]=counter
for b,e in zip(l,r):
    print(lis[e-1]-lis[b-1])

Submission status: Accepted

Solution code:
n,q = [int(i) for i in input().split()]
s = input()

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

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

Submission status: Accepted

Solution code:
n,q = [int(i) for i in input().split()]
s = input()
l = []
r = []
for i in range(q):
  l_tmp, r_tmp = [int(j) for j in input().split()]
  l.append(l_tmp-1)
  r.append(r_tmp-1)
  
r_cnt = [0]
for i in range(1,n):
  if s[i-1:i+1] == 'AC':
    r_cnt.append(r_cnt[i-1]+1)
  else:
    r_cnt.append(r_cnt[i-1])
    
for i in range(q):
  ans = r_cnt[r[i]] - r_cnt[l[i]]
  print(ans)

Submission status: Accepted

Solution code:
Q=input()
S=input()
N,Q_num = int(Q.split(" ")[0]),int(Q.split(" ")[1])
AC=[0]
count = 0
for i in range(N-1):
  if S[i]=="A" and S[i+1]=="C":
    count = 1+count
  AC.append(count)
for q in range(int(Q_num)):
  qu = input().split(" ")
  print(AC[int(qu[1])-1]-AC[int(qu[0])-1])

Submission status: Accepted

Solution code:
n,q = [int(i) for i in input().split()]
s = input()
l = []
r = []
for i in range(q):
  l_tmp, r_tmp = [int(j) for j in input().split()]
  l.append(l_tmp-1)
  r.append(r_tmp-1)
  
ac_cnt = s.count('AC')
r_cnt = [ac_cnt]
l_cnt = [0]
for i in range(1,n):
  if s[i-1:i+1] == 'AC':
    r_cnt.append(r_cnt[i-1]-1)
    l_cnt.append(l_cnt[i-1]+1)
  else:
    r_cnt.append(r_cnt[i-1])
    l_cnt.append(l_cnt[i-1])
    
for i in range(q):
  ans = r_cnt[l[i]] + l_cnt[r[i]] - ac_cnt
  print(ans)

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
S = input()
ac_list = [0,0]
question_list = []
for i in range(len(S)-1):
    if S[i:i+2] == "AC":
        ac_sum = ac_list[i+1] + 1
        ac_list.append(ac_sum)
    else:
        ac_list.append(ac_list[-1])
for _ in range(q):
    l, r = map(int,input().split())
    question_list.append([l,r])
for l,r in question_list:
    print(ac_list[r]-ac_list[l])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


def main():
    n, q = map(int, input().split())
    s = input()
    m = len(s)
    ac = [0 for _ in range(m)]

    for k in range(m - 1):
        if s[k] == 'A' and s[k + 1] == 'C':
            ac[k + 1] = ac[k] + 1
        else:
            ac[k + 1] = ac[k]

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


if __name__ == '__main__':
    main()

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:
#!/usr/bin/env python3
import sys


def solve(n: int, Q: int, S: str, l: "List[int]", r: "List[int]"):
    count = [0] * (n + 1)
    tmp = 0
    for idx in range(n - 1):
        if S[idx:idx + 2] == 'AC':
            tmp += 1
        count[idx + 1] = tmp
    #print(count)
    for i in range(Q):
        ret = count[r[i] - 1] - count[max(0, l[i] - 2)]
        if l[i] > 1 and S[l[i] - 2:l[i]] == 'AC':
            ret -= 1
        print(ret)

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    l = [int()] * (Q)  # type: "List[int]" 
    r = [int()] * (Q)  # type: "List[int]" 
    for i in range(Q):
        l[i] = int(next(tokens))
        r[i] = int(next(tokens))
    solve(N, Q, S, l, r)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
l=list(input())
list=[0]
c=0
for i in range(len(l)-1):
  if l[i]=="A" and l[i+1]=="C":
    c+=1
    list.append(c)
  else:
    list.append(c)
for i in range(m):
  n,m=map(int,input().split())
  print(list[m-1]-list[n-1])

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
in_str = input()
AC_count = []
r = [0]*(N+1)
for i in range(N):
    r[i+1] = r[i] + (1 if in_str[i:i+2] == "AC" else 0) 
    
    
for i in range(Q):
    in1, in2 = map(int, input().split())
    print(r[in2-1]-r[in1-1])

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = input()
t=[0]*(N+1)
ans = [0] * Q
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())
	ans[i] = t[r-1] - t[l-1]
for i in range(Q):
    print(ans[i])

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(lambda x: int(x) - 1, input().split()))

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

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(lambda x: int(x) - 1, input().split()))
 
b, t = 0, [0]*N
for i in range(1, N):
  if S[i-1] == 'A' and S[i] == 'C':
    t[i] = t[i-1] + 1
  else: t[i] = t[i-1]
 
for i in range(Q):
  print(t[lr[i][1]] - t[lr[i][0]])

Submission status: Accepted

Solution code:
import re

NQ = [int(i) for i in input().split()]
N = NQ[0]
Q = NQ[1]
S = input()
LR = [[int(i) for i in input().split()] for j in range(Q)]
check = [0] * N
for i in range(N - 1):
    check[i + 1] = check[i] + (1 if S[i:i + 2] == "AC" else 0)


for j in range(Q):
    print((check[LR[j][1] - 1]) - (check[LR[j][0] - 1]))

Submission status: Accepted

Solution code:
# coding: utf-8
import re
import bisect
from datetime import datetime as dt

N, Q = map(int, raw_input().split())
S = raw_input()
S += ' '
l = []
r = []
for i in range(Q):
    a = map(int, raw_input().split())
    l.append(a[0])
    r.append(a[1])

count = 0
d = [0 for i in range(N+1)]
for i in range(N):
    if S[i]+S[i+1] == 'AC':
        count += 1
    d[i + 1] = count

for i in range(Q):
    print '{}'.format(d[r[i]-1] - d[l[i]-1])

Submission status: Accepted

Solution code:
n,q = (int(num) for num in input().split())
s = input()
list_ac = [0]*n
list_sum = [0]*n
for i in range(n-1):
    if s[i:i+2] == 'AC':
        list_ac[i] = 1
for i in range(1,n):
    list_sum[i] = list_sum[i-1] + list_ac[i-1]
    
for j in range(q):
    l,r = (int(num)-1 for num in input().split())
    print(list_sum[r]-list_sum[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)
#    print(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:
def main():

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

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

    res = [None]*q

    for i in range(q):

        l, r = map(int, input().split())
        res[i] = cumsum[r-1] - cumsum[l-1]

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


main()

Submission status: Accepted

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

for i in range(N-1):
 if charList[i]=='A' and charList[i+1]=='C':
  AClist[i+1]=AClist[i]+1;
 else:
  AClist[i+1]=AClist[i];

result=[0]*Q;
for i in range(Q):
 l, r = map(int, input().split())
 result[i]=AClist[r-1]-AClist[l-1];
 if result[i]<0:
  result[i]=0;
for i in range(Q):
 print(result[i]);

Submission status: Accepted

Solution code:
from itertools import accumulate

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

t = [0] * N

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

T = list(accumulate(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 = list(input())
cum = [0 for i in range(n+1)]
i = 0
while i < n:
    if i < n-1 and s[i] == "A" and s[i+1] == "C":
        cum[i+1] = cum[i]
        cum[i+2] = 1+cum[i+1]
        i += 2
    else:
        cum[i+1] = cum[i]
        i += 1

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

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
S = input()
d = [0] * n
counter = 1
for i in range(n - 1):
    d[i] = counter
    if S[i]+S[i + 1] == 'AC':
            d[i+1] = counter
            counter += 1
d[len(S)-1] = counter
for i in range(q):
    r,l = map(int,input().split())
    print(d[l-1]-d[r-1])

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
 
N, Q = map(int, input().split())
S = input()
 
t = [0] * N
 
for i in range(1, N):
    s = S[i-1:i+1]
    if s == 'AC':
        t[i] += 1

T = list(accumulate(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 = list(map(int, input().split()))
S = str(input())
lr=[]
for i in range(Q):
    lr.append(list(map(int, input().split())))


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

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

Submission status: Accepted

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


count=[0]

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

for i,j in lr:
    print(count[j-1]-count[i-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 bisect


def solve(memo, left, right):
    left_key = bisect.bisect_left(memo, left)
    right_key = bisect.bisect_right(memo, right)
    return right_key - left_key


def main():
    length, questions = map(int, input().split())
    string = input()

    memo = []
    for key in range(length - 1):
        if string[key:key+2] == "AC":
            memo.append(key + 1)

    for question in range(questions):
        left, right = map(int, input().split())
        right -= 1
        ans = solve(memo, left, right)
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Sum = [0]

sum_ = 0

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

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

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
s = input()
ls = [0]*(n+1)
for i in range(len(s)):
    if s[i:i+2]=="AC":
        ls[i+1] += ls[i]+1
    else:
        ls[i+1] = ls[i]
for j 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_list = [0]*(N+1)
for i in range(N):
    if S[i:i+2] == "AC":
        AC_list[i+1] = AC_list[i]+1
    else:
        AC_list[i+1] = AC_list[i]

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

Submission status: Accepted

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

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

for i in range(q) :
    print(ANS[A[i][1]] - ANS[A[i][0]])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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

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

for _ in range(Q):
    l, r = map(int, input().split())
    print(Sl[r - 1] - Sl[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)]
count=[0]*(n)
for i in range(1,n):
    if s[i-1]+s[i]=='AC':
        count[i]+=count[i-1]+1
    else:
        count[i]+=count[i-1]
for j in range(q):
    start=lr[j][0]-1
    end=lr[j][1]-1
    print(count[end]-count[start])

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,q = LI()
    s = S()
    lr = [LI() for _ in range(q)]

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

    rr = []
    for a,b in lr:
        t = cc[b] - cc[a]
        rr.append(t)

    return '\n'.join(map(str, rr))


print(main())

Submission status: Accepted

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

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from bisect import bisect_left
N, Q = map(int, input().split())
S = str(input())
LR = [list(map(int, input().split())) for i in range(Q)]

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


for l, r in LR:
    i = bisect_left(ans_list, l-1)
    j = bisect_left(ans_list, r-1)
    print(j-i)

Submission status: Accepted

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