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:
# 2019/04/28
# AtCoder Beginner Contest 122 - C

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

acgt = ["A", "C", "G", "T"]
acgtl = list()
acgtl.append(0)

# Search AC and make Accumed sum
for i in range(n-1):
    if s[i] == "A" and s[i+1] == "C":
        acgtl.append(acgtl[i]+1)
    else:
        acgtl.append(acgtl[i])
        
# Calc AC count
for x in range(q):
    l, r = map(int,input().split())
    ans = acgtl[r-1] - acgtl[l-1]
    print(ans)

Submission status: Accepted

Solution code:

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

cnt = [0] * (n+1)

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

for query in range(q):
    l, r = map(int,input().split())
    print(cnt[r] - cnt[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):
    if s[i] == 'A' and s[i+1] == 'C':
        t[i] += 1
    t[i+1] += t[i]

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

Submission status: Accepted

Solution code:
import sys
import numpy as np

readInt = lambda: int(sys.stdin.readline())
readIntN = lambda: [int(v) for v in sys.stdin.readline().split(' ')]

n, q = readIntN()
s = input()
lrs = [readIntN() for i in range(q)]

acc = [0] * n
for i, (b, e) in enumerate(zip(s, s[1:]), 1):
    acc[i] = acc[i-1]
    if b == 'A' and e == 'C':
        acc[i] += 1

for b, e in lrs:
    print(acc[e-1] - acc[b-1])

Submission status: Accepted

Solution code:
n, q = [int(e) for e in input().strip().split()]
s = input().strip()
lrs = []
for i in range(q):
    l, r = [int(e) for e in input().strip().split()]
    lrs.append((l, r))

cnt = 0
cumcnt = [0 for _ in range(len(s))]

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

    cumcnt[i] = cnt



for inx in lrs:
    l, r = inx
    tmp = cumcnt[r-1] - cumcnt[l-1]
    print(tmp)

Submission status: Accepted

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

N,Q = [int(x) for x in input().split()]
S = list(input())
lrlist =[]
for _ in range(Q):
    l,r = [int(x) for x in input().split()]
    lrlist.append((l,r))

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

for _ in range (Q):
    l = lrlist[_][0]
    r = lrlist[_][1]
    ans = sumls[r-1]-sumls[l-1]
    print(ans)

Submission status: Accepted

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

aclist = []
acnum = 0
for j in range(n - 1):
  if s[j] == "A" and s[j + 1] == "C":
    aclist.append(j)
    acnum += 1
if acnum == 0:
  for i in range(q):
    print(0)
else:
  rightac = []
  acindex = 0
  for j2 in range(n):
    if j2 == aclist[acindex] + 1:
      acindex = min(acindex + 1, len(aclist) - 1)
      acnum -= 1
    rightac.append(acnum)

  anslist = []
  for k in range(q):
    ans = rightac[inputlist[k][0] - 1] - rightac[inputlist[k][1] - 1]
    anslist.append(ans)

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

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = input()
LR = [list(map(int, input().split())) for _ in range(Q)]
csm = [0] * (N+1)

for i in range(1, N):
    csm[i + 1] += csm[i]
    if S[i-1:i+1] == 'AC':
        csm[i + 1] += + 1
for i in range(Q):
    l, r = LR[i]
    print(csm[r] - csm[l])

Submission status: Accepted

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

Submission status: Accepted

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

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

for i, j in l:
    print(ans[j] - ans[i])

Submission status: Accepted

Solution code:
# C - GeT AC
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())
ans = [0]*(N+1)
ans[0] = 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 k 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()

#S[i]までの"AC"の数を計算して、countリストに保存するための処理
count=[]
ans=0
for i in range (N):
  if i!=0 and S[i-1]=="A" and S[i]=="C":
    ans+=1
    count.append(ans)
  else:
    count.append(ans)
#print(count)

#countリストから答えを呼び出すための処理
for _ in range(Q):
  l, r=map(int, input().split())
  print(count[r-1]-count[l-1])

"""
最初思ついた処理（TLEになった）
for _ in range(Q):
  l, r= map(int, input().split())
  SP= S[l-1:r]
  print(SP.count("AC"))
"""

Submission status: Accepted

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

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

for _ 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()
ac_count = [0]
ac_num = 0
for i in range(n-1):
    if s[i] + s[i+1] == "AC":
        ac_num += 1
    ac_count.append(ac_num)
for i in range(q):
    l, r = map(int, input().split())
    print(ac_count[r-1] - ac_count[l-1])

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n,q = map(int, input().split())
s = input()
l = [0] * q
r = [0] * q
for i in range(q):
    l[i],r[i] = map(int, input().split())
c = [0] * n
for i in range(1,n):
    if s[i-1:i+1] == "AC":
        c[i] = c[i-1] + 1
    else:
        c[i] = c[i-1]
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 = str(input())
i = [0] * (N + 1)
j = 1
while j < N:
    i[j+1] = i[j] 
    if (S[j-1] == 'A' and S[j] == 'C'):
        i[j+1] += 1
    j += 1
k = 0
#print (i)
while k < Q:
    l, r = map(int, input().split())
    ans = i[r]-i[l]
    k += 1
    print (ans)

Submission status: Accepted

Solution code:
N,Q = map(int, input().split())
S = str(input())
# N,Q=8,3
# S = "ACACTACG"
L = [0] * len(S) #ACのAの個数を保持
i = 0
sum_i = 0
while i < len(S)-1:
    if S[i] == "A":
        if S[i+1] == "C":
            L[i] = sum_i
            sum_i += 1
            L[i+1] = sum_i
            i += 2
        elif S[i+1] == "A":
            L[i] = sum_i
            i += 1
        else:
            L[i] = sum_i
            L[i+1] = sum_i
            i += 2
    else:
        L[i] = sum_i
        i += 1
L[len(S)-1] = sum_i
for _ in range(Q):
    l, r = map(int, input().split())
    print(L[r-1] - L[l-1])

Submission status: Accepted

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

# s = 'ACACTACG'
# lr = [
#     [3, 7],
#     [2, 3],
#     [1, 8],
# ]

wa = [0]

for index in range(1, len(s)):

    if s[index - 1] == 'A' and s[index] == 'C':
        wa.append(wa[index - 1] + 1)
    else:
        wa.append(wa[index - 1])

for row in lr:
    start = row[0] - 1
    end = row[1] - 1

    diff = wa[end] - wa[start]
    print(diff)

Submission status: Accepted

Solution code:
N, Q = map(int, input().split(" "))
S = input()
ac_cnts = [0]
ac_cnt = 0
for i in range(N-1):
    if S[i:i+2] == "AC":
        ac_cnt += 1
    ac_cnts.append(ac_cnt)
for j in range(Q):
    l, r = map(int, input().split(" "))
    print(ac_cnts[r-1] - ac_cnts[l-1])

Submission status: Accepted

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

Submission status: Accepted

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

"""
###文章そのままの実装ー＞N,Q によりオーダーが大きくなりすぎる
for i in range(int(Q)):
	count = 0
	l,r = map(int, input().split(" "))
	for j in range(r-l):
		if sentence[l-1+j:l+j+1] == "AC":
			count += 1
	print(count)

"""

###累積和を用いて高速に計算
#予め累積和を計算　クエリで高速回答
#ACACTGC
#0112222
AC_list = [0]*(N)
count = 0
for i in range(N-1):
	if sentence[i : i+2] == "AC":
		count += 1
	AC_list[i+1] = count

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:
def resolve():
    # 読み込み
    N, Q = map(int, input().split())
    S = 'X' + input()
    l = [0]
    r = [0]
    for i in range(Q):
        ll, rr = map(int, input().split())
        l.append(ll)
        r.append(rr)
    
    # n番目までにACが含まれる数をc[n]としてカウント
    c = [0] * (N + 1)
    for i in range(2, N + 1):
        if S[i - 1] == 'A' and S[i] == 'C':
            c[i] = c[i-1] + 1
        else:
            c[i] = c[i-1]

    # 各l[i], r[i]について出力
    for i in range(1, Q+1):
        cr = c[r[i]]
        cl = c[l[i]]

        print(cr - cl)
        
resolve()

Submission status: Accepted

Solution code:
import collections
import itertools

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

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

A = list(itertools.accumulate(A))
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()
 
ACDP=[0]*N
Aflag=0
ACcount=0
for i in range(len(S)):
  if S[i]=='C' and Aflag==1:
    ACcount+=1
  if S[i]=='A':
    Aflag=1
  else:
    Aflag=0
  ACDP[i]=ACcount
#print(ACDP)
 
for _ in range(Q):
  start,end=map(int,input().split())
  print(ACDP[end-1]-ACDP[start-1])

Submission status: Accepted

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

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

Submission status: Accepted

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

cnt, buf = [0] * (N + 1), None
for i in range(N):
    s = S[i]
    cnt[i + 1] = cnt[i]
    if buf == 'A' and s == 'C':
        cnt[i + 1] += 1
    buf = s

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
N,Q = list(map(int,input().split(" ")))
S = input()
nums = [0] * len(S)
for i,(s1,s2) in enumerate(zip(S[:-1],S[1:])):
    if s1 == "A" and s2 == "C":
        nums[i+1] += nums[i] + 1
    else:
        nums[i+1] += nums[i]
ls = []
rs = []
for i in range(Q):
    l,r = list(map(int,input().split(" ")))
    l -= 1
    r -= 1
    ls.append(l)
    rs.append(r)
for l,r in zip(ls,rs):
    print(nums[r]-nums[l])

Submission status: Accepted

Solution code:
from itertools import accumulate

N,Q=map(int,input().split())
S=input()
count=[0]*(N)
for i in range(N-1):
    if S[i:i+2]=="AC":
        count[i]=1
sums=list(accumulate([0]+count))

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

Submission status: Accepted

Solution code:
import sys

def main():
    input = sys.stdin.readline
    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):
        start, end = map(int, input().split())
        print(t[end - 1] - t[start - 1])
    
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def solve(string):
    n, q, s, *lr = string.split()
    n = int(n)
    c = [0] * n
    count = 0
    for i in range(n):
        if i == 0:
            continue
        if s[i - 1:i + 1] == "AC":
            count += 1
        c[i] = count

    lr = list(map(int, lr))
    return "\n".join([str(c[r - 1] - c[l - 1]) for l, r in zip(lr[::2], lr[1::2])])


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve('{} {}\n'.format(n, m) + '\n'.join([input() for _ in range(m + 1)])))

Submission status: Accepted

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

L = []
for i in range(Q):
  L.append([int(i) for i in input().split()])
  
for i in range(N-1):
  if S[i] == "A" and S[i+1] == "C":
    S = S[:i] + "a" + S[i+1:]

l = []
c = 0
for i in range(N):
  l.append(c)
  if S[i] == "a":
    c += 1
  

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
S = input()
b = [0]*(n+1)
for i in range(n-1):
    if S[i] == 'A' and S[i+1] == 'C':
       b[i+1] += 1
from itertools import accumulate
b = list(accumulate(b))
#print(b)
for i in range(q):
    l,r = map(int,input().split())
    print(b[r-1]-b[l-1])

Submission status: Accepted

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

# Sのi番目までに出現するACの数を格納するリストです
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 = list(map(int, input().split()))
  print(t[r-1] - t[l-1])

Submission status: Accepted

Solution code:
def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

n, q = read_line(int, int)
s, = read_line(str)

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

c = 0
for i in range(len(s)):
    if s[i:i+2] == 'AC':
        c += 1
    m[i + 1] = c

for i in range(q):
    l, r = read_line(int, int)

    if c == 0:
        print(0)
        continue
    print(m[r - 1] - m[l - 1])

Submission status: Accepted

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

counter = [0]*(n+1)
count=0
for i,s in enumerate(base):
    if i < n-1 and s=="A" and base[i+1]=="C":
        count+=1
    counter[i+1]=count

ans=[]
for i in range(q):
    l,r = map(int,input().split())
    ans.append(str(counter[r-1]-counter[l-1]))
print('\n'.join(ans))

Submission status: Accepted

Solution code:
N,Q = map(int,input().split())
S = list(input())
AC_list=[]
sum_AC=0
sum_list=[]
Ans=[]

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

    sum_AC = sum_AC+int(AC_list[i])
    sum_list.append(sum_AC)

for j in range(Q):

    l,r=map(int,input().split())
    if l == 1 :
        Ans.append(sum_list[r-2])
    else:
        Ans.append(sum_list[r-2]-sum_list[l-2])

for k in range(Q):
    print(Ans[k])

Submission status: Accepted

Solution code:
import sys
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits


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


def INT(): return int(input())


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


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


sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

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

lis = [0]*N

for i, x in enumerate(S):
    if (i == N-1):
        break
    else:
        if x == 'A' and S[i + 1] == 'C':
            lis[i+1] = lis[i]+1
        else:
            lis[i+1] = lis[i]


for i in range(Q):
    print(lis[lr[i][1]-1]-lis[lr[i][0]-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 permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

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

accum = []
count = 0

for i in range(len(S)-1):
	accum.append(count)
	if S[i] == "A" and S[i+1] == "C":
		count += 1
accum.append(count)
# print(accum)
for l, r in lr:
	print(accum[r-1]-accum[l-1])

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
S = input()
dp = [0]*(N+1)
cnt = 0
for i in range(2,N+1):
    if S[i-1] == "C" and S[i-2] == "A":
        cnt += 1
    dp[i] = cnt
ans = []
for _ in [0]*Q:
    l, r = map(int, input().split())
    ans.append(dp[r] - dp[l])
print(*ans, sep="\n")

Submission status: Accepted

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

lis = [0] * len(S)
for i in range(len(S)):

  if i>0:
    lis[i] += lis[i-1]
  if i < len(S)-1 and S[i] == 'A' and S[i+1] == 'C':
    lis[i+1] += 1


for _ in range(Q):
  L = tuple(map(int, input().split()))

  c = 0
  print(lis[L[1]-1]-lis[L[0]-1])

Submission status: Accepted

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

lis = [0] * len(S)
for i in range(len(S)):

  if i>0:
    lis[i] += lis[i-1]
  if i < len(S)-1 and S[i] == 'A' and S[i+1] == 'C':
    lis[i+1] += 1


for _ in range(Q):
  L = tuple(map(int, input().split()))

  c = 0
  print(lis[L[1]-1]-lis[L[0]-1])

Submission status: Accepted

Solution code:
import bisect

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

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

for i in range(q):
    l, r = [int(i) for i in input().split()]
    l_index = bisect.bisect_left(positions, l)
    r_index = bisect.bisect_left(positions, r)
    print(r_index - l_index)

Submission status: Accepted

Solution code:
n,q = map(int,input().split(" "))
s = input()
counter = 0
ac_num = []
ac_num.append(0)

for i in range(1,n):
    if (s[i]=="C") & (s[i-1]=="A"):
        counter = counter + 1
    ac_num.append(counter)

rng = [0,0]
result = []

for i in range(q):
    rng[0],rng[1] = map(int,input().split(" "))
    result.append(ac_num[rng[1]-1]-ac_num[rng[0]-1])

for i in result:
    print(i)

Submission status: Accepted

Solution code:
from itertools import*
n,q=map(int,input().split())
s=input()
dp=[0]*n
for i in range(n-1):
    if s[i:i+2]=="AC":
        dp[i+1]=1
x=list(accumulate(dp))
for i in range(q):
    l,r=map(int,input().split())
    print(x[r-1]-x[l-1])

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 = list(map(int,input().split()))
S = input()
sums = [0]
for i in range(len(S)):
	if i == 0:
		continue
	sums.append(sums[i-1])
	if S[i-1]+S[i] == 'AC':
		sums[i] += 1

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
#累積和による解法

N,Q = map(int, input().split())
S = input()
cnt_list = [0]

for i in range(1,N):
    if S[i]=="C" and S[i-1]=="A":
        cnt_list.append(cnt_list[-1]+1)
    else:
        cnt_list.append(cnt_list[-1])
for j in range(Q):
    l,r = map(int, input().split())
    ans = cnt_list[r-1]-cnt_list[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 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()

list = [0]*N

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

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

Submission status: Accepted

Solution code:
import sys


def inp():
    return sys.stdin.readline().strip()


n, q = map(int, inp().split())
s = inp()
a = [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 _ in range(q):
    l, r = map(int, inp().split())
    print(a[r-1] - a[l-1])

Submission status: Accepted

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

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

#print(count)
        
for i in range(Q):
    l = ls[i]
    r = rs[i]
    print(count[r] - count[l])

Submission status: Accepted

Solution code:
N, Q = [int(i) for i in input().split()]
S = list(input())
term = [[int(i) for i in input().split()] for x in range(Q)]
ACs = [0 for i in range(N)] 
ans = []

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

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

Submission status: Accepted

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

acc[N-1] = acc[N-2]
for i in range(Q):
    l,r = map(int,input().split(" "))
    if l > 1:
        ans = acc[r-1] - acc[l-2]
    else:
        ans = acc[r-1]
    if a[r-1] == 1:
        ans -= 1
    
    print(ans)

Submission status: Accepted

Solution code:
N, Q = [int(i) for i in input().split()]
S = input()
lr = []
for i in range(Q):
    l, r = input().split(" ")
    lr.append((int(l)-1, int(r)-1))
    
# i番目を含む右部分文字列中に"AC"が何回現れるか
c = [0 for _ in range(N)]
for i in range(N-1)[::-1]:
    if S[i] == "A" and S[i+1] == "C":
        c[i] = c[i+1] + 1
    else:
        c[i] = c[i+1]
        
for i in range(Q):
    l, r = lr[i]
    a = c[l] - c[r]
    print(a)

Submission status: Accepted

Solution code:
N, Q = [int(i) for i in input().split()]
S = input()
lr = []
for i in range(Q):
    l, r = input().split(" ")
    lr.append((int(l)-1, int(r)-1))
    
# i番目を含む右部分文字列中に"AC"が何回現れるか
c = [0 for _ in range(N)]
for i in range(N-1)[::-1]:
    if S[i] == "A" and S[i+1] == "C":
        c[i] = c[i+1] + 1
    else:
        c[i] = c[i+1]
        
for i in range(Q):
    l, r = lr[i]
    a = c[l] - c[r]
    if r < len(S) - 1 and c[r] == "A" and c[r] == "C":
        a -= 1
    print(a)

Submission status: Accepted

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

for q in range(Q):
    l, r = map(int, input().split())
    if S[l - 1] != 'C':
        l -= 1
    print(asum[r] - asum[l])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

def isAC(i):
    return s[i:i + 2] == "AC"

cs = [0] * n
for i, v in enumerate(s[:-1]):
    if isAC(i):
        cs[i] = 1

cs.insert(0, 0)
for i in range(1, len(cs)):
    cs[i] += cs[i - 1]

for query in range(q):
    left, right = map(int, input().split())
    result = cs[right] - cs[left - 1]
    if right < n and isAC(right - 1):
        result -= 1
    print(result)

Submission status: Accepted

Solution code:
N,Q = map(int,input().split())
s = input()
t = [0]
ans = []
for i in range(N):
    if s[i:i+2] == "AC":
        t.append(t[i] + 1)
    else:
        t.append(t[i])
for i in range(Q):
    l,r = map(int,input().split())
    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()
assert len(S) == N

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

nAC = [0]  # nAC[i] == the number of 'AC' whose head 'A' is in S[:i]
for i in range(len(AC)):
    nAC.append(nAC[-1] + (1 if AC[i] else 0))

def solve(l, r):
    return nAC[r - 1] - nAC[l - 1]

for i in range(Q):
    l, r = map(int, input().split())
    print(solve(l, r))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,Q = list(map(int, input().split()))
S = input()
x=[]
y=[]
for i in range(Q):
    x1,y1=[int(i) for i in input().split()]
    x.append(x1)
    y.append(y1)
t = [0]*(N+1)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = input()
target = 'AC'
shiftID = len(target) - 1

found_id = []

for i in range(N-shiftID):
    if S[i:i+len(target)] == target:
        found_id.append(i)

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

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

for _ in range(Q):
    l, r = map(int, input().split())
    print(found_count[r] - found_count[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] = (1 if s[i:i + 2] == "AC" else 0) + t[i]
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())
hoge=input()
huga=[0]
for i in range(n-1):
  flag=0
  if(hoge[i]=="A" and hoge[i+1]=="C"):
    flag=1
  huga.append(huga[-1]+flag)

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

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
s=input()
list_ac=[]
number=0
state=0
for i in range(0,len(s)):
    if s[i]=='A':
        state=1
        list_ac.append(number)
    elif s[i]=='C':
        if state==1:
            number=number+1   
        list_ac.append(number)
        state=0
    else:
        state=0
        list_ac.append(number)
for i in range(0,q):
    l,r=map(int,input().split())
    print(list_ac[r-1]-list_ac[l-1])

Submission status: Accepted

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