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:
# 解説
# 「右隣がCであるようなA」を数えた方が単純

def main():
    import sys
    input = sys.stdin.readline

    N, Q = map(int, input().split())
    s = input().rstrip()

    imos = [0] * (N + 1)
    for i in range(N - 1):
        if s[i:i + 2] == 'AC':
            imos[i + 1] += 1  # Aの位置に加算
    for i in range(N):
        imos[i + 1] += imos[i]

    ans = []
    for _ in range(Q):
        l, r = map(int, input().split())
        t = imos[r - 1] - imos[l - 1]
        # rの端から1文字手前までの右にCを持つAの個数を調べる
        # r-1==そのようなAのときr==C
        ans.append(t)
    print(*ans, sep='\n')


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    N, Q = map(int, input().split())
    s = input().rstrip()

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

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


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n, q = map(int,input().split())
s = input()

tmp = [0 for _ in range(n)]
for i in range(1, n):
    if s[i-1] == 'A' and s[i] == 'C':
        tmp[i] = 1 + tmp[i-1]
    else:
        tmp[i] = tmp[i-1]
#print(tmp)

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

Submission status: Accepted

Solution code:
n,q=map(int, input().split())
s=input()
sn=""
ans=[0]*(n+1)

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):
    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 = list(input())
lr = [list(map(int,input().split())) for i in range(Q)]
ans = ''
a = [0]
count = 0
for i in range(N-1):
  if S[i] + S[i+1] == 'AC':
    ans += '1'
  else:
    ans += '0'
  if i == N - 2:
    ans += '0'
else:
  for i in range(N):
    if ans[i] == '1':
      count += 1
      a.append(count)
    else:
      a.append(count)
  else:
    for i in range(Q):
      l = lr[i][0]
      r = lr[i][1]
      print(a[r-1]-a[l-1])

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
#template
def inputlist(): return [int(k) for k in input().split()]
#template
N,Q = inputlist()
S = list(input())
sumac = [0]*N
li = [0]*Q
for i in range(1,N):
    if S[i-1] == 'A' and S[i] == 'C':
        sumac[i] = sumac[i-1]+1
        continue
    sumac[i] = sumac[i-1]
for i in range(Q):
    l,r = inputlist()
    l-=1
    r-=1
    li[i] = sumac[r]-sumac[l]
for i in range(Q):
    print(li[i])

Submission status: Accepted

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

Submission status: Accepted

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

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


for l, r in lr:
    l -= 1
    r -= 1
    if S[l] == 'C':
        print(s[r] - s[l])
    else:
        print(s[r] - s[max(0, l - 1)])

Submission status: Accepted

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

Submission status: Accepted

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

s = input()

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

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

Submission status: Accepted

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

l = [0]*N
count = 0

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

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

Submission status: Accepted

Solution code:
N,Q = list(map(int, input().split()))
S = list(input())
l = []
r = []
for _ in range(Q):
    L,R = list(map(int, input().split()))
    l.append(L)
    r.append(R)
flag = False
ac = [0]*N
count = 0

for j in range(N):
        if S[j] == 'A':
            flag = True
            ac[j] = count
            continue
        if S[j] == 'C' and flag:
            count += 1
        ac[j] = count
        flag = False


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

Submission status: Accepted

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

accA = [0] * (N + 1)
for i in range(1, N + 1):
    accA[i] = accA[i - 1] + A[i - 1]

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

Submission status: Accepted

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

AC=[]

for i,s in enumerate(S):
    if i>=1:
        if s=="C" and S[i-1]=="A":
            AC.append(i-1)
#print(AC)
for i in range(Q):
    l,r=map(int,input().split())
    left=bisect.bisect_left(AC,l-1)
    right=bisect.bisect_right(AC,r-2)
    #print("----")
    print(right-left)

Submission status: Accepted

Solution code:
N,Q = map(int,input().split())
S = str(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()
c=[0]*n
for i in range(1,n):
  if s[i]=="C" and s[i-1]=="A":
    c[i]+=1
from itertools import accumulate as acc
c=list(acc(c))
for i in range(q):
  l,r=map(int,input().split())
  print(c[r-1]-c[l-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    N, Q = (int(i) for i in input().split())
    S = input()
    LR = [[int(i) for i in input().split()] for j in range(Q)]
    AC = [0]*N
    for i, s in enumerate(S):
        AC[i] = AC[i-1]
        if i > 0 and S[i-1] == "A" and s == "C":
            AC[i] += 1
    S = list([0] + AC)
    for le, ri in LR:
        print(S[ri] - S[le])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect
n, q = map(int, input().split())
S = list(input())
X = []
for i in range(n-1):
    if S[i] == 'A' and S[i+1] == 'C':
        X.append(i)
for j in range(q):
    l, r = map(int, input().split())
    a = bisect.bisect_left(X, l-1)
    b = bisect.bisect_left(X, r-1)
    print(b-a)

Submission status: Accepted

Solution code:
from collections import *
from heapq import *
import sys

sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]
dij = [(1, 0), (-1, 0), (0, 1), (0, -1)]


def main():
    n,q=MI()
    s=SI()
    cs=[0]*(n+1)
    for i in range(n-1):
        if s[i:i+2]=="AC":cs[i+2]+=1
    for i in range(n):cs[i+1]+=cs[i]
    for _ in range(q):
        l,r=MI()
        l,r=l-1,r-1
        ans=cs[r+1]-cs[l]
        if s[l-1:l+1]=="AC":ans-=1
        print(ans)

main()

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
from decimal import Decimal
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,q = inpl()
s = input()
a = [0]*(n+1)
for i in range(1,n):
    if s[i-1] == 'A' and s[i] == 'C':
        a[i+1] = a[i] + 1
    else:
        a[i+1] = a[i]
# print(a)
for _ in range(q):
    x,y = inpl()
    print(a[y] - a[x])

Submission status: Accepted

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

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

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, acos, atan, asin, log, log10
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 debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(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()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]
debugmode = True

n, q = MAP()
s = STR()
t = [0 for _ in range(n)]
for i in range(1, n):
    t[i] = t[i - 1]
    if s[i - 1:i + 1] == 'AC':
        t[i] += 1
for _ in range(q):
    l, r = MAP()
    print(t[r - 1] - t[l - 1])

Submission status: Accepted

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

Submission status: Accepted

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

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

for 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()
k = 0
sum_c = [0 for _ in range(n)]
cnt = 0
for i in range(n-1):
    if s[i:i+2] == 'AC':
        cnt += 1
    sum_c[i+1] = cnt

while True:
    l, r = map(int, input().split())
    print(sum_c[r-1]-sum_c[l-1])
    k += 1
    if q <= k:
        break

Submission status: Accepted

Solution code:
import numpy as np
n,q=map(int,input().split())
s=list(input())
t=np.zeros(n+1,dtype=int)
for i in range(n-1):
    if s[i]+s[i+1]=="AC":
        t[i+1]=1
t=t.cumsum()
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]*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 i in range(Q):
    l, r = map(int, input().split())
    print(cnt[r-1]-cnt[l-1])

Submission status: Accepted

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

for _ in range(Q):
    l, r = map(int,input().split())
    ans = cnt[r] - cnt[l-1]
    if 2 <= l and (S[l-2] == 'A' and S[l-1] == 'C'):
        ans -= 1
    print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

for i in range(N):
    s[i+1] = s[i] + ac[i]

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

Submission status: Accepted

Solution code:
from itertools import accumulate 
n,q = map(int,input().split())
s = input()
l = [list(map(int,input().split())) for _ in range (q)]
flg =[]
for i in range(n-1):
  if s[i:i+2]=="AC":
    flg.append(1)
  else:
    flg.append(0)
flg2 = [0]+flg
flg2 = list(accumulate(flg2))
for i in l:
  print(flg2[i[1]-1]-flg2[i[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()
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 _ 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())
lr = [list(map(int, input().split())) for i in range(Q)]

mark = [0]*(N+1)

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

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

Submission status: Accepted

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

mark = [0]*(N+1)

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

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
import os
import math

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

MOD = 10 ** 9 + 7


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, Q = il()
    S = iss()
    ret = [0] * N
    for n in range(N - 1):
        if S[n] == 'A' and S[n + 1] == 'C':
            ret[n] += ret[n - 1] + 1
        else:
            ret[n] += ret[n - 1]

    for _ in range(Q):
        l, r = il()
        print(ret[r - 2] - ret[l - 2])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


# -------------------------------------------------------------
# main
# -------------------------------------------------------------
N,Q = map(int,input().split())
S = input().rstrip() + "Z"
LR = [map(int,input().split()) for _ in range(Q)]

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

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N,Q=map(int,input().split())
s=input()
A=[0]
for i in range(N-1):
  if s[i]+s[i+1]=="AC":
    A.append(A[i]+1)
  else:
    A.append(A[i])
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_number=[0 for _ in range(N+1)]
cnt=0
for i in range(1,N):
    if S[i]=="C" and S[i-1]=="A":
        cnt+=1
    AC_number[i+1]=cnt

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

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

output_ls = [0] * q
for i in range(q):
    l, r = map(int,input().split())
    output_ls[i] = csum[r] - csum[l]

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

Submission status: Accepted

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

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

s = [0]*(N+1)
for i in range(N):
    s[i+1] = s[i] + a[i]

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
IS = lambda: sys.stdin.readline().rstrip()
II = lambda: int(IS())
MII = lambda: list(map(int, IS().split()))
from bisect import bisect_left, bisect_right

def main():
    n, q = MII()
    s = IS()
    lr = [(MII()) for _ in range(q)]
    ac_index = []
    for i in range(n-1):
        if s[i:i+2] == 'AC': ac_index.append(i)
    cnt = 0
    for l, r in lr:
        i = bisect_left(ac_index, l-1)
        j = bisect_left(ac_index, r-1)
        print(j-i)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
s = input()
lr = [list(map(int, input().split())) for _ in range(Q)]
ac_sum = [0] * (N + 1)
s = list(s)
i = 0
while i < N:
    if s[i : i + 2] == ['A', 'C']:
        #print(i)
        ac_sum[i + 2] += ac_sum[i] + 1
        ac_sum[i + 1] += ac_sum[i] + 1
        i += 2
    else:
        ac_sum[i + 1] = ac_sum[i]
        i += 1
for l, r in lr:
    l -= 1
    r -= 1
    print(ac_sum[r] - ac_sum[l])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
s = input()
sl = len(s)
ac_cnts = [0]
cnt = 0
for i in range(0, sl-1):
    if s[i] == 'A' and s[i+1] == 'C':
        cnt += 1
    ac_cnts.append(cnt)
for i 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()
ans = [int(s[i:i+2]=='AC') for i in range(n)]
ans = [0] + ans
from itertools import accumulate
ans = list(accumulate(ans))
for _ in range(q):
  l,r = map(int,input().split())
  print(ans[r-1]-ans[l-1])

Submission status: Accepted

Solution code:
import numpy as np
import sys
readline = sys.stdin.readline
read = sys.stdin.read

import bisect
n, q = map(int, readline().split())
s = readline().rstrip()
a = []
for i in range(len(s) - 1):
	if s[i] == 'A' and s[i + 1] == 'C':
		a.append(i)
for _ in range(q):
	l, r = map(int, readline().split())
	l -= 1
	r -= 2
	print(bisect.bisect_right(a, r) - bisect.bisect_left(a, l))

Submission status: Accepted

Solution code:
# 累積和
n, q = map(int, input().split())
s = input()
arr = [0] * (2 * 10**5 + 10)
idx = 1
while idx < len(s):
    if s[idx - 1] == "A" and s[idx] == "C":
        arr[idx] += 1
    idx += 1
for i in range(1, len(arr)):
    arr[i] += arr[i - 1]
for _ in range(q):
    l, r = map(int, input().split())
    print(arr[r - 1] - arr[l - 1])

Submission status: Accepted

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

for i in range(n):
    p = x[i]
    if s[i:i+2] == "AC":
        p += 1
    x[i+1] =  p

for i in range(q):
    a, b = map(int,input().split())
    print(x[b-1] - x[a-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 numpy as np

N, Q = map(int, input().split())
S = "0" + input()
q = list()
for _ in range(Q):
    l, r = map(int, input().split())
    q.append((l, r))

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

cumsum = np.cumsum(cnt)
for l, r in q:
    print(cumsum[r] - cumsum[l])

Submission status: Accepted

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

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

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:
mod = 10 ** 9 + 7
mod2 = 2**61+1
from collections import deque
import heapq
from bisect import bisect_left, insort_left, bisect_right

_NUMINT_ALL = list(range(10))

def main():
    ans = solve()
    if ans is not None:
        print(ans)

def solve():
    N, Q = iip(False)
    S = input()
    LR = iipt(Q)

    #print(S)

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

    #print(A)

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








#####################################################ライブラリ集ここから

def iip(listed=True, num_only = True):
    if num_only:
        ret = [int(i) for i in input().split()]
    else:
        ret = [int(i) if i in _NUMINT_ALL else i for i in input().split()]

    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iipt(l, listed=False, num_only = True):
    ret = []
    for i in range(l):
        ret.append(iip(listed=listed, num_only=num_only))
    return ret

def iip_ord():
    return [ord(i) - ord("a") for i in input()]

def YesNo(s):
    if s:
        print("Yes")
    else:
        print("No")

def fprint(s):
    for i in s:
        print(i)

def bitall(N):
    ret = []
    for i in range(2**N):
        a = []
        for j in range(N):
            a.append(i%2)
            i //= 2
        ret.append(a)
    return ret

def split_print_space(s):
    print(" ".join([str(i) for i in s]))

def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side="left"):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p, mod_= mod):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
N, Q  = map(int, input().split())
S = list(input())
Lsub = [0]
Rsub = [0]
L = 0
R = 0


for k in range(1,N):
  if S[k-1] == "A" and S[k] == "C":
    L += 1
  Lsub.append(L)

for j in range(0,N-1)[::-1]:
  if S[j] == "A" and S[j+1] == "C":
    R += 1
  Rsub.append(R)


for i in range(Q):
  L, R = map(int, input().split())
  print(Rsub[N-1] - Lsub[L-1] - Rsub[N-R])