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
input = sys.stdin.readline

#import numpy as np
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
#from collections import deque, defaultdict, Counter
#from heapq import heappush, heappop
#from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
#from operator import itemgetter as ig

#sys.setrecursionlimit(10 ** 7)
#nf = 10 ** 20
#INF = float("INF")
#mod = 10 ** 9 + 7

'''
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]
ddn9 = ddn + [(0, 0)]
for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:

def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]  # WideIntPoint
def ws(): return sys.stdin.readline().split()
def si(): return int(sys.stdin.readline())  # SingleInt
def ss(): return input()
def hi(n): return [si() for _ in range(n)]
def hs(n): return [ss() for _ in range(n)]  # HeightString
def s_list(): return list(input())
def mi(n): return [wi() for _ in range(n)]  # MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]
def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[0]] for _ in range(n)]  # NumberGrid
def grid(n): return [s_list() for _ in range(n)]
# 深さ優先探索
def dfs(G, v):
    global time, first_order,seen,last_order
    time += 1
    first_order[v-1] = time   #　行きがけ

    seen[v-1] = True # v を訪問済みにする
    # v から行ける各頂点 next_v について
    for next_v in G[v]:
        if seen[next_v-1]:
            continue
        dfs(G, next_v)

    time += 1
    last_order[v - 1] = time  # 帰りがけ
'''

def main():

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

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

    for task_n in task:
        print(count[task_n[1]] - count[task_n[0]])

if __name__ == '__main__':
    main()

Submission status: Accepted

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

for i in range(q):
    g = list_score[i]
    print(list_c[g[1]-1]-list_c[g[0]-1])

Submission status: Accepted

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

Submission status: Accepted

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

s = input()
t = [0] * (n+1)
p = []
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())
	p.append(t[r-1]-t[l-1])

for i in p:
	print(i)

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = input()
count = [0]*N  # count[i] は i 番目まで S[:i+1] の解
for i in range(1, N):
    count[i] = count[i-1]
    if S[i-1: i+1] == "AC":
        count[i] += 1
for _ in range(Q):
    l,r = map(int, input().split())
    print(count[r-1] - count[l-1])

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n, q = MAP()
s = STR()
arr = [1 if s[i] + s[i + 1] == 'AC' else 0 for i in range(n - 1)]
arr2 = [[0, False] for _ in range(n - 1)]
arr2[0] = [arr[0], True if arr[0] == 1 else False]
for i in range(1, n - 1):
    arr2[i][0] = arr2[i - 1][0] + arr[i]
    arr2[i][1] = True if arr[i] == 1 else False
for _ in range(q):
    l, r = MAP()
    print(arr2[r - 2][0] - arr2[l - 1][0] + arr2[l - 1][1])

Submission status: Accepted

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

for i in range(1, N):
    T[i+1] = T[i] + (1 if S[i-1:i+1]=='AC' else 0)
ans = []
for _ in range(Q):
    l, r = map(int, input().split())
    ans.append(T[r] - T[l])
print(*ans, sep='\n')

Submission status: Accepted

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

S = [0] + list(accumulate(A))

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

for qi in Q:
    print(S[qi[1]]-S[qi[0]])

Submission status: Accepted

Solution code:
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    N,Q=map(int,readline().split())
    S=readline().strip()
    l=[0]*Q
    r=[0]*Q
    for i in range(Q):
        l[i],r[i]=map(lambda x:int(x)-1,readline().split())

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

    for i in range(Q):
        print(sum_ac[r[i]]-sum_ac[l[i]])

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
s = input()
ans = []
li = [0] * (len(s))
count = 0

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

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

for aa in ans:
    print(aa)

Submission status: Accepted

Solution code:
import sys
N, Q = map(int, sys.stdin.readline().rstrip().split(" "))

S = sys.stdin.readline().rstrip()

cs = [0] * (N+1)

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

for _ in range(Q):
    l, r = map(int, sys.stdin.readline().rstrip().split())
    print(cs[r] - cs[l])

Submission status: Accepted

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


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

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

    result = []

    for _ in range(Q):
        left, right = map(int, input().split())
        result.append(ac_count[right - 1] - ac_count[left - 1])

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:

import bisect


def read_input():
    n, q = map(int, input().split())
    s = list(input().strip())
    queries = []
    for _ in range(q):
        st, ed = map(int, input().split())
        queries.append((st - 1, ed - 1))

    return n, s, queries


def submit():
    n, s, queries = read_input()

    # AC pointを列挙する
    ac_st = []
    for i in range(n - 1):
        if s[i] == "A" and s[i + 1] == "C":
            ac_st.append(i)

    for ql, qr in queries:
        print(bisect.bisect_right(ac_st, qr - 1) -\
              bisect.bisect_left(ac_st, ql))


if __name__ == "__main__":
    submit()

Submission status: Accepted

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

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

for _ 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())
l=[0 for i in range(n)]
for i,v in enumerate(list(input().replace("AC","X!"))):
    l[i]=l[i-1]+(v=="!")
for c in range(q):
    h,m=map(int,input().split())
    print(l[m-1]-l[h-1])

Submission status: Accepted

Solution code:

n, q = map(int, input().split())
s = input()
cnt = 0
data = [0] * (n + 1)
ans = [0] * q
for i in range(n - 1):
    if s[i] == 'A' and s[i + 1] == 'C':
        cnt += 1
    data[i + 1] = cnt

data[n - 1] = cnt

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

    ans[i] = data[r - 1] - data[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

def inp(l: list) -> list:
    return [int(l[0]) - 1, int(l[1]) - 1]

for i in range(q):
    lr[i] = tuple(inp(input().split()))

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

# print(count)

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

Submission status: Accepted

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

N, Q = MAP()
S = input()
L = [LIST() for i in range(Q)]
ruiseki = [0] * (N)

for i in range(N-1):
    if S[i+1] == "C" and S[i] == "A":
        #if S[i] == "A":
            ruiseki[i+1] += ruiseki[i] + 1
    else:
        ruiseki[i+1] = ruiseki[i]
for l, r in L:
    ans = ruiseki[r-1] - ruiseki[l-1]
    print(ans)

Submission status: Accepted

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

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

# 愚直な計算時間
# ループn回
# リスト切り取りO(n)
# O(n^2)
# 計算リミットが2000msで、n<=10^5
# 0(n)でn=10^6くらいが限度
# O8n^2)だと、n=3000くらい

# 先に回数を数える。累積和的に
# ここで結構時間かかる
# hoge = [s[0:(i + 1)].count('AC') for i in range(n)]

# 修正ver
hoge = [0]
cnt = 0
for i in range(1, n):
    if s[i - 1] + s[i] == 'AC':
        cnt += 1
    hoge.append(cnt)

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

Submission status: Accepted

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

# table[i] = i文字目以下のsにACは部分文字列として何回現れるか
table = [None] * (n+1)
table[0] = 0
table[1] = 0
for i in range(2, n+1):
    if s[i-2:i] == 'AC':
        table[i] = table[i-1] + 1
    else:
        table[i] = table[i-1]

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

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
# from fractions import gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))

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


def main():
    N, Q = MAP()
    S = INPUT()

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

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


if __name__ == '__main__':
        main()

Submission status: Accepted

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

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

for _ in range(Q):
    L, R = map(int, input().split())
    ans = cnt[R-1] - (cnt[L-2] if L >= 2 else 0)
    if L >= 2 and cnt[L-1] != cnt[L-2]:
        ans -= 1
    print(ans)

Submission status: Accepted

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

geta = []
acam = [0]*n
c = 0

for i in range(1,n):
    if s[i-1] == 'A' and s[i] == 'C':
        c += 1
        geta.append(i-1)
    acam[i] = c
    
for i in range(q):
    l , r = map(int,input().split())
    l -= 1
    r -= 1
    print(acam[r] - acam[l])

Submission status: Accepted

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

ans = [0 for _ in range(N+1)]
temp = 0
for i in range(N) :
    if S[i:i+2] == "AC" :
        temp += 1
    ans[i+1] += temp

for i in range(Q) :
    print(ans[rs[i]-1] - ans[ls[i]-1])

Submission status: Accepted

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

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

lis = [0]*N
count = 0

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

lis_acc = list(accumulate(lis))

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

Submission status: Accepted

Solution code:
# input
n, q = map(int, input().split())
a = [0 for i in range(n+1)]
s = input()
for i in range(n):
    a[i+1] = a[i] + (1 if s[i:i+2] == 'AC' else 0)
# for m in re.finditer('AC', s):
#    a[m.start()] = 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()
AC_numbers = [0]

# そうか、まず累積和で全体のACのかずを数えるのか
for i in range(1, N):
  if S[i-1] == 'A' and S[i] == 'C':
    AC_numbers.append(AC_numbers[i - 1] + 1)
  else:
    AC_numbers.append(AC_numbers[i-1])

# そこから引いて数を求める
for q in range(Q):
  start, end = map(int, input().split())
  count = AC_numbers[end-1] - AC_numbers[start-1]
  print(count)

Submission status: Accepted

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

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

for l, r in X:
    print(cnt[r - 1] - cnt[l - 1])

Submission status: Accepted

Solution code:
#ABC122C 累積和
from itertools import accumulate
A = []
N, Q = map(int, input().split())
B = [0]*N
S = list(input())
ans = []
for i in range(1, N):
    if S[i-1]=='A' and S[i]=='C':
        B[i] = 1
A = list(accumulate(B))
for j in range(Q):
    l, r = map(int, input().split())
    ans.append(A[r-1]-A[l-1])
print('\n'.join(map(str, ans)))

Submission status: Accepted

Solution code:
import numpy

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

li = [0]*(n+1)
for i in range(n-1):
    if (s[i]=="A" and s[i+1] == "C"):
        li[i+1] = 1
cum = numpy.cumsum(li)
for i in range(q):
    l,r = [int(x) for x in input().split()]
    print(cum[r-1]-cum[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]"):
    table = [0] * (N + 1)
    for i, (s1, s2) in enumerate(zip(S, S[1:]), 1):
        table[i+1] = table[i] + (1 if s1 == 'A' and s2 == 'C' else 0)
    for ll, rr in zip(l, r):
        yield table[rr] - table[ll]

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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))
    for r in solve(N, Q, S, l, r):
        print(r)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

s=input()

check = [0]*n

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

for _ in range(q):
    x,y = map(int,input().split())
    print(check[y-1]-check[x-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = input()
l, r = [0]*Q, [0]*Q
for i in range(Q):
    l[i], r[i] = map(int,input().split())
    l[i] -= 1
    r[i] -= 1
lr = zip(l,r)

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

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

Submission status: Accepted

Solution code:
def main():
  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])

if __name__=='__main__':
  main()

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

for i, k in zip(l, r):
    print(cum_sum[k-1] - cum_sum[i-1])

Submission status: Accepted

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

for i in range(q):
    first, last = map(int, input().split())
    print(table[last - 1] - table[first - 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 = [int(x) for x in input().split()]
S = input()
R = [0]
res = 0
ans = []
for i in range(N - 1):
    if S[i:i+2] == 'AC':
        res += 1
    R.append(res)
for i in range(Q):
    l, r = [int(x) for x in input().split()]
    ans.append(R[r-1] - R[l-1])
for r in ans:
    print(r)

Submission status: Accepted

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

Submission status: Accepted

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

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

ansl=[]
for i in range(q):
    l,r=map(int,input().split())
    if l==1:
        ansl.append(cuml[r-1])
    else:
        ansl.append(cuml[r-1]-cuml[l-1])

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# import bisect
# from collections import Counter, deque
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
import itertools
# from operator import attrgetter, itemgetter
# import math

import sys

# import numpy as np

ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, q = list(map(int,ipti().split()))
    s = input()
    ls = len(s)
    ac = [0] * ls

    for i in range(ls-1):
        if s[i] == 'A':
            if s[i+1] == 'C':
                ac[i+1] += 1

    cs = list(itertools.accumulate(ac))

    for i in range(q):
        left, right = list(map(int,ipti().split()))
        print(cs[right-1] - cs[left-1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
graph = list(input())
ans = [0] * n
sans = [0] * n
for i in range(n-1):
    if graph[i] == "A" and graph[i+1] == "C":
        ans[i] += 1
for j in range(n-1):
    sans[j+1] = sans[j] + ans[j]

for _ in range(m):
    j, k = map(int, input().split())
    print(sans[k-1] - sans[j-1])

Submission status: Accepted

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

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

from bisect import bisect_left
for c in Cs:
  ans = bisect_left(det_idx, c[1]-1) - bisect_left(det_idx, c[0]-1)
  print(ans)

Submission status: Accepted

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

n, q = map(int, input().split())
s = input()
memo = [0] * n
cnt = 0

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

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

Submission status: Accepted

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

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

for q in query:
    print(cum_sum[q[1]] - cum_sum[q[0]])

Submission status: Accepted

Solution code:
N,Q = map(int,input().split())
S = input()
questions = [[i for i in map(int,input().split())] for j 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 questions:
  print(t[q[1]-1] - t[q[0]-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
s = input()
info = [list(map(int, input().split())) for _ in range(q)]
all = s.count('AC')
ans = []
lt = [all]
rt = [all]
# for i in range(n):
#     lt.append(all - s[i:].count('AC'))
#     rt.append(all - s[:n-i].count('AC'))
for i in range(1, n):
    if s[i-1] == 'A' and s[i] == 'C':
        lt.append(lt[i-1] - 1)
    else:
        lt.append(lt[i-1])
    if s[n-i-1] == 'A' and s[n-i] == 'C':
        rt.append(rt[i-1] - 1)
    else:
        rt.append(rt[i-1])

rt.reverse()
# print(lt)
# print(rt)
# print(rt)
for l, r in info:
    ans.append(lt[l-1] + rt[r-1] - all)

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

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

T = [0]*N
U = [0]*N
cnt = 0
for i in range(N-1):
    if S[i]+S[i+1]=="AC":
        T[i+1]=1
        cnt+=1
    U[i+1] = cnt

for i in range(Q):
    L = LR[i][0]-1
    R = LR[i][1]-1
    print(U[R]-U[L])

Submission status: Accepted

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

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

#先に部分話でSの中のACの数を数えておく
ac_wa = [0] #ACの登場回数の累積和を計算 0文字めは先に足しとく 
for i in range(1,N):
  if (S[i] == "C" and S[i-1] == "A"): #その文字がCで前の文字がAの時のみにカウントを1つたす
    ac_wa.append(ac_wa[i-1]+1)
  else:
    ac_wa.append(ac_wa[i-1])
#出力
for i in range(Q):
  r = ac_wa[l_r[i][1]-1] 
  l = ac_wa[l_r[i][0]-1]
  ans = r-l
  print(ans)

Submission status: Accepted

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

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

ans = []
num = 0

for i in range(q):
    l, r = map(int, input().split())
    num = bisect.bisect_right(li, r-2)-bisect.bisect_left(li, l-1)
    ans.append(num)

for i in ans:
    print(i)

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
s = input()
lr = [[0] * 2 for _ in range(q)]
for i in range(q):
    l, r = map(int, input().split())
    lr[i][0], lr[i][1] = l, r

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

for i in lr:
    print(cnt[i[1]-1] - cnt[i[0]-1])

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
N,Q=[int(i) for i in input().rstrip().split()]
S = input().strip()
lr_list=[[int(j) for j in input().split()] for i in range(Q)]

calc_cnt=[0]
for i in range(1,len(S)):
    sub_str = S[(i-1):(i+1)]
    
    if sub_str == "AC":
        calc_cnt += [calc_cnt[i-1] + 1]
    else:
        calc_cnt += [calc_cnt[i-1]]
        

for l,r in lr_list:
    ans = calc_cnt[r-1] - calc_cnt[l-1]
    print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations
    #from itertools import accumulate, product, permutations
    from math import floor, ceil

    #mod = 1000000007

    n,q = map(int, input().split())
    s = input()
    l = [0]*(n+1)
    for i in range(n):
        if s[i]=='A':
          if s[i+1]=='C':
            l[i+1]=l[i] + 1
            continue
        l[i+1]=l[i]

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


if __name__ == '__main__':
    main()