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

def solve(N: int, Q: int, S: str, l: "List[int]", r: "List[int]"):
    A_index = []
    ## ACの場所を全部記録しときたい→Aの場所を全部記録
    for i in range(N-1):
        if S[i] == 'A' and S[i+1] == 'C':
            A_index.append(i)
    
    for j in range(Q):
        if r[j] <= 1:
            print(0)
            continue

        left_index = bisect_left(A_index,l[j]-1)
        right_index = bisect_left(A_index,r[j]-1)
        print(right_index-left_index)
    return


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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

for i in range(q):
  print(g[lis[i][1]-1]-g[lis[i][0]-1])

Submission status: Accepted

Solution code:
import sys
import bisect
input=sys.stdin.readline
n,q=map(int,input().split())
s=input()
ac=[]
for i in range(n-1):
  if s[i]=="A" and s[i+1]=="C":
    ac.append(i+1)
for i in range(q):
  a,b=map(int,input().split())
  print(bisect.bisect_right(ac,b-1)-bisect.bisect_left(ac,a))

Submission status: Accepted

Solution code:
import bisect
n,q=map(int,input().split())
s=input()
ac=[]
for i in range(n-1):
  if s[i]=="A" and s[i+1]=="C":
    ac.append(i+1)
for i in range(q):
  a,b=map(int,input().split())
  print(bisect.bisect_right(ac,b-1)-bisect.bisect_left(ac,a))

Submission status: Accepted

Solution code:
import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, q = list(map(int, input().rstrip('\n').split()))
    s = str(input().rstrip('\n'))
    ls = [0] * n
    for i in range(1, n):
        if s[i] == "C" and s[i-1] == "A":
            ls[i] += 1
        ls[i] += ls[i-1]
    for i in range(q):
        l, r = list(map(int, input().rstrip('\n').split()))
        print(ls[r-1] - ls[l-1])


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]

n, q = ril()
s = rs()
ls = rils(q)
acc = [0] * n
for i in range(1, n):
    if s[i - 1:i + 1] == 'AC':
        acc[i] = acc[i - 1] + 1
    else:
        acc[i] = acc[i - 1]
for l, r in ls:
    print(acc[r - 1] - acc[l - 1])

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]

n, q = ril()
s = rs()
acc = [0] * n
for i in range(1, n):
    if s[i - 1:i + 1] == 'AC':
        acc[i] = acc[i - 1] + 1
    else:
        acc[i] = acc[i - 1]
for _ in range(q):
    l, r = ril()
    print(acc[r - 1] - acc[l - 1])

Submission status: Accepted

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

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

Acc = [0]*(N+1)
for i in range(N):
    Acc[i+1] = Acc[i]+Data[i]

#print(Acc)
for q in QList:
    l = q[0]
    r = q[1]
    ans = Acc[r]-Acc[l-1]
    if l >= 2:
        if S[l-1] == 'C' and S[l-2] == 'A':
            ans -= 1
    print(ans)

Submission status: Accepted

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

for i in l:
    print(m[i[1]-1]-m[i[0]-1])

Submission status: Accepted

Solution code:
n,q=map(int, input().split())
s=input()
num_ac=[0 for i in range(n)]
#num_ac[i]はi+1文字目までのACの数？
for i in range(1,n):
    num_ac[i]=num_ac[i-1]
    if s[i]=='C' and s[i-1]=='A':
        num_ac[i]+=1
for i in range(q):
    l,r=map(int,input().split())
    print(num_ac[r-1]-num_ac[l-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
if sys.platform =='ios':
	sys.stdin=open('input.txt')

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

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

from bisect import bisect_right as br
from bisect import bisect_left as bl
for i in range(q):
    a=bl(AC,lr[i][0]-1)
    #print(i,AC,lr[i][0],a)
    b=br(AC,lr[i][1]-2)
    #print(a,b)
    print(b-a)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import re
import sys
input = sys.stdin.readline
n,q=map(int,input().split())
s=input()
a=[0]*(n+1)
tmp=0
for i in range(n-1):
  if s[i:i+2]=="AC":
    tmp+=1
  a[i+2]=tmp

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

AC=[]
for i in range(n-1):
    if s[i]=="A":
        if s[i+1]=="C":
            AC.append(i)
#print(AC)
from bisect import bisect_right as br
from bisect import bisect_left as bl
for i in range(q):
    a=bl(AC,lr[i][0]-1)
    b=br(AC,lr[i][1]-2)
    #print(a,b)
    print(b-a)

Submission status: Accepted

Solution code:
#累積和
n,q=map(int,input().split())
s=input()
L=[list(map(int,input().split())) for _ in range(q)]

LL=[0]*n
for i in range(1,n):
      if s[i-1:i+1]=="AC":
            LL[i]+=LL[i-1]+1
      else:
            LL[i]+=LL[i-1]
for i in range(q):
      print(LL[L[i][1]-1]-LL[L[i][0]-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import re
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 = list(input())
anslist = [0]*N
count =0
for n in range(N-1):
    if S[n] == 'A' and S[n+1] == 'C':
        count += 1
    anslist[n+1] = count
#print(anslist)    
for m in range(Q):
     l, r = map(int, input().split())
     ans = anslist[r-1]-anslist[l-1]
     print(ans)

Submission status: Accepted

Solution code:
from sys import stdin


def main():
    N, Q = map(int, input().split())
    S = input()
    LR = [int(x) - 1 for x in stdin.read().split()]
    AC = []
    pre = None
    cnt = 0
    for c in S:
        if c == "A":
            pre = "A"
        elif pre == "A" and c == "C":
            cnt += 1
            pre = None
        elif pre == "A":
            pre = None
        AC.append(cnt)
    for l, r in zip(*[iter(LR)] * 2):
        print(AC[r] - AC[l])
    return


main()

Submission status: Accepted

Solution code:
from sys import stdin


def main():
    N, Q = map(int, input().split())
    S = input().strip()
    LR = [int(x) - 1 for x in  stdin.read().split()]
    AC = []
    pre = None
    cnt = 0
    for c in S:
        if c == "A":
            pre = "A"
        elif pre == "A" and c == "C":
            cnt += 1
            pre = None
        elif pre == "A":
            pre = None
        AC.append(cnt)
    for l, r in zip(*[iter(LR)] * 2):
        print(AC[r] - AC[l])
    return


main()

Submission status: Accepted

Solution code:
from sys import stdin


def main():
    read = stdin.read
    N, Q = map(int, input().split())
    S = input().strip()
    LR = [int(x) - 1 for x in  read().split()]
    AC = []
    pre = None
    cnt = 0
    for c in S:
        if c == "A":
            pre = "A"
        elif pre == "A" and c == "C":
            cnt += 1
            pre = None
        elif pre == "A":
            pre = None
        AC.append(cnt)
    for l, r in zip(*[iter(LR)] * 2):
        print(AC[r] - AC[l])
    return


main()

Submission status: Accepted

Solution code:
from sys import stdin


def main():
    readline = stdin.readline
    read = stdin.read
    N, Q = map(int, readline().split())
    S = readline().strip()
    LR = [int(x) - 1 for x in  read().split()]
    AC = []
    pre = None
    cnt = 0
    for c in S:
        if c == "A":
            pre = "A"
        elif pre == "A" and c == "C":
            cnt += 1
            pre = None
        elif pre == "A":
            pre = None
        AC.append(cnt)
    for l, r in zip(*[iter(LR)] * 2):
        print(AC[r] - AC[l])
    return


main()

Submission status: Accepted

Solution code:
from sys import stdin


def main():
    readline = stdin.readline
    read = stdin.read
    N, Q = map(int, readline().split())
    S = readline().strip()
    * LR, = map(lambda x: int(x) - 1, read().split())
    AC = []
    pre = None
    cnt = 0
    for c in S:
        if c == "A":
            pre = "A"
        elif pre == "A" and c == "C":
            cnt += 1
            pre = None
        elif pre == "A":
            pre = None
        AC.append(cnt)
    for l, r in zip(*[iter(LR)] * 2):
        print(AC[r] - AC[l])
    return


main()

Submission status: Accepted

Solution code:
from sys import stdin


def main():
    readline = stdin.readline
    read = stdin.read
    N, Q = map(int, readline().split())
    S = readline().strip()
    *LR, = map(lambda x: int(x) - 1, read().split())
    AC = []
    pre = None
    cnt = 0
    for c in S:
        if c == "A":
            pre = "A"
        elif pre == "A" and c == "C":
            cnt += 1
            pre = None
        elif pre == "A":
            pre = None
        AC.append(cnt)
    for l, r in zip(*[iter(LR)] * 2):
        print(AC[r] - AC[l])
    return


main()

Submission status: Accepted

Solution code:
from sys import stdin


def main():
    readline = stdin.readline
    N, Q = map(int, readline().split())
    S = readline().strip()
    L = []
    R = []
    for i in range(Q):
        *LR, = map(int, readline().split())
        L.append(LR[0] - 1)
        R.append(LR[1] - 1)
    AC = []
    pre = None
    cnt = 0
    for c in S:
        if c == "A":
            pre = "A"
        elif pre == "A" and c == "C":
            cnt += 1
            pre = None
        elif pre == "A":
            pre = None
        AC.append(cnt)
    for l, r in zip(L, R):
        print(AC[r] - AC[l])
    return


main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n,q = list(map(int,input().split()))
s = input()
s2 = s[1::]
d = [list(map(int,input().split())) for i in range(q)]

#AC開始位置を記録する
ac_idx = []

aci_append = ac_idx.append
for i,v in enumerate(zip(s,s2)):
    if v == ("A","C"):
        aci_append(i)

#2分探索, nibuntansaku,二分探索
from bisect import bisect_left

for l,r in d:
    print(bisect_left(ac_idx,r-1) - bisect_left(ac_idx,l-1))

Submission status: Accepted

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

ac_count = [0]*N
temp = 0
for i in range(1,N):
    if S[i] == 'C' and S[i-1] == 'A':
        temp += 1
        ac_count[i] = temp
    else:
        ac_count[i] = temp
#print(ac_count)
for _ in range(Q):
    l,r = map(int,input().split())
    if S[l-1] != 'C':
        print(ac_count[r-1]-ac_count[l-1])
    else:
        print(ac_count[r-1]-ac_count[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)]
a=[0]*n

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

for i in range(q):
  print(a[l[i][1]-1]-a[l[i][0]-1])

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
s = input().replace("AC","aC")
L = [0]*n
cnt = 0
for i in range(1,n):
    if s[i-1] == "a":
        cnt += 1
    L[i]=cnt
        
for i in range(q):
    l,r = map(int,input().split())
    print(L[r-1] - L[l-1])

Submission status: Accepted

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

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

    ans = []
    for i in range(Q):
        l, r = map(int, input().split())
        ans.append(templist[r-1] - templist[l-1])
    for a in ans:
        print(a)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, os
import collections

def solve(input_stream):
  n, q = [int(char) for char in input_stream.readline().strip().split()]
  target = input_stream.readline().strip()
  ans = []

  dp = [0 for i in range(len(target) + 1)]
  is_a = False
  for index, char in enumerate(target):
    dp[index + 1] = dp[index]
    if is_a:
      if char == "C":
        dp[index + 1] += 1
      is_a = False
    if char == "A":
      is_a = True
  for index in range(q):
    l, r = [int(char) for char in input_stream.readline().strip().split()]
    ans.append(str( dp[r] - dp[l] ))
  return ans  

if __name__ == "__main__":
    outputs = solve(sys.stdin)
    for line in outputs:
      print(line)

Submission status: Accepted

Solution code:
import sys
import time
sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

N, Q = MAP()
S = input().rstrip()
LR = [MAP() for _ in range(Q)]

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

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

Submission status: Accepted

Solution code:
from itertools import accumulate


def solve(n, q, s):
    m = [0]*n
    for i in range(1, n):
        if s[i-1:i+1] == 'AC':
            m[i] = 1

    accm = list(accumulate(m))

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


if __name__ == '__main__':
    n, q = map(int, input().split())
    s = input()
    solve(n, q, s)

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())
AC = [None] * N
flag_A = False
cnt = 0
for i, s in enumerate(input()):
    AC[i] = cnt
    if flag_A:
        if s == 'C':
            cnt += 1
            AC[i] = cnt
        flag_A = False

    if s == 'A':
        flag_A = True

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

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
s=input()
cnt=[0 for i in range(n+1)]
for i in range(1,n+1):
    if s[i-1:i+1]=="AC":
        cnt[i]+=1
    cnt[i]+=cnt[i-1]
#print(cnt)
for i in range(q):
    a,b=map(int,input().split())
    print(cnt[b-1]-cnt[a-1])

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,q=map(int,input().split())
s=input().replace("\n","")
cnt=[0 for i in range(n+1)]
for i in range(1,n+1):
    if s[i-1:i+1]=="AC":
        cnt[i]+=1
    cnt[i]+=cnt[i-1]
#print(cnt)
for i in range(q):
    a,b=map(int,input().split())
    print(cnt[b-1]-cnt[a-1])

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = input()
lr_list = [list(map(int, input().split())) for i in range(Q)]
ac_sum = [0]
count = 0
for i, char in enumerate(S):
    if i != 0:
        if char == "C" and buf == "A":
            count += 1
    ac_sum.append(count)
    buf = char

for lr in lr_list:
    print(ac_sum[lr[1]] - ac_sum[lr[0]])

Submission status: Accepted

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

s = input()


lr = [[int(i) for i in input().split()] for i in range(q)]



csum = [0 for i in range(n+1)]



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




for i in range(q):
    print(csum[lr[i][1]-1] - csum[lr[i][0]-1])

Submission status: Accepted

Solution code:
# coding:utf-8

# 入力
N, Q = map(int, input().split(' '))
S = input()
ql = [map(int, input().split(' ')) for _ in range(Q)]

# 累積和の作成
cl = [0, 0]
for i in range(N-1):
    if S[i] + S[i+1] == 'AC':
        cl.append(cl[-1]+1)
    else:
        cl.append(cl[-1])

# クエリに対する出力
for l, r in ql:
    print(cl[r] - cl[l])

Submission status: Accepted

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

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

for l, r in queries:
    print(countl[r] - countl[l])

Submission status: Accepted

Solution code:
class SegmentTree:
    def __init__(self, n, init_val, ide_ele=0):
        self.num = 2 ** (n - 1).bit_length()
        self.seg = [ide_ele] * 2 * self.num
        self.ide_ele = ide_ele
        for i in range(n):
            self.seg[i + self.num - 1] = init_val[i]
        for i in range(self.num - 2, -1, -1):
            self.seg[i] = self.seg_func(self.seg[2 * i + 1], self.seg[2 * i + 2])

    def update(self, k, x):
        k += self.num - 1
        self.seg[k] = x
        while k:
            k = (k - 1) // 2
            self.seg[k] = self.seg_func(self.seg[2 * k + 1], self.seg[2 * k + 2])

    def query(self, p, q):
        if q <= p:
            return self.ide_ele
        p += self.num - 1
        q += self.num - 2
        res = self.ide_ele
        while q - p > 1:
            if p & 1 == 0:
                res = self.seg_func(res, self.seg[p])
            if q & 1 == 1:
                res = self.seg_func(res, self.seg[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        if p == q:
            res = self.seg_func(res, self.seg[p])
        else:
            res = self.seg_func(self.seg_func(res, self.seg[p]), self.seg[q])
        return res

    def seg_func(self, x, y):
        return x + y


def p_c():
    n, q = map(int, input().split())
    s = input().replace("AC", "01")
    li = list(map(lambda x: 1 if x == "0" else 0, s))
    seg = SegmentTree(n, li)
    ans = []
    for _ in range(q):
        l, r = map(int, input().split())
        ans.append(str(seg.query(l - 1, r - 1)))
    print("\n".join(ans))
    
p_c()

Submission status: Accepted

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

count_list = []
bef_str = ''
bef_count = 0

for x in s:
  if bef_str == 'A' and x == 'C':
    bef_count += 1
    
  count_list.append(bef_count)
  bef_str = x
    
for i in range(q):
  l, r = (int(i) for i in input().split())
  print(count_list[r-1] - count_list[l-1])

Submission status: Accepted

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

s = input()

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

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

for i in range(1, len(arr)):
	arr[i] = arr[i-1] + arr[i]

for _ in range(q):
	a, b = [int(x) for x in input().split()]
	print(str(arr[b]-arr[a]))

Submission status: Accepted

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

Submission status: Accepted

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

sum_list = [0]

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

[sum_list.append(sum_list[-1]+1) if s == 'C' and S[i-1] == 'A' else sum_list.append(sum_list[-1]) for i, s in enumerate(S)]

for l, r in lr_list:
    print(sum_list[r] - sum_list[l])

Submission status: Accepted

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

sum_list = [0]

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

# [sum_list.append(sum_list[-1]+1) if s == 'C' and S[i-1] == 'A' else sum_list.append(sum_list[-1]) for i, s in enumerate(S)]

for l, r in lr_list:
    print(sum_list[r] - sum_list[l])

Submission status: Accepted

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

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

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

Submission status: Accepted

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

for i in range(1, n):
    if s[i] == 'C' and s[i-1] == 'A':
        ans_list[i] = ans_list[i-1] + 1
    else:
        ans_list[i] = ans_list[i-1]
#print(ans_list)
for j in range(q):
    l, r = list[j]
    print(ans_list[r-1]-ans_list[l-1])

Submission status: Accepted

Solution code:
import collections

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

new_S = S.replace("AC", "12")


count_one_list = [0] * len(S)
for i in range(len(S)-1):
    if new_S[i] == '1' and i == 0:
        count_one_list[i+1] += 1
    elif new_S[i] == '1':
        count_one_list[i+1] = count_one_list[i] + 1
    else:
        count_one_list[i+1] = count_one_list[i]
# count_one_list = [new_S[:i].count('1') for i in range(len(S))]
# print(count_one_list)

for i in range(Q):
    left, right = map(int, input().split())
    count_one = count_one_list[right-1] - count_one_list[left-1]
    print(count_one)

Submission status: Accepted

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

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

Submission status: Accepted

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

b = [0] * n
cnt = 0
for i in range(n-1):
	if s[i:i+2] == "AC":
		b[i+1] = b[i] + 1
	else:
		b[i+1] = b[i]
for i in a:
	print (b[i[1]-1] - b[i[0]-1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def print_ans(N, Q, S, arr):
    """Test Case
    >>> print_ans(8, 3, "ACACTACG", [[3, 7], [2, 3], [1, 8]])
    2
    0
    3
    """
    t = [0] * (N+1)
    for i in range(N):
        t[i+1] = t[i] + (1 if S[i:i+2] == "AC" else 0)
    for ar in arr:
        print(t[ar[1] - 1] - t[ar[0] - 1] )

if __name__ == '__main__':
    N, Q = map(int, input().rstrip().split())
    S = input().rstrip()
    arr = [list(map(int, input().rstrip().split())) for _ in range(Q)]
    print_ans(N, Q, S, arr)

Submission status: Accepted

Solution code:
def main():
    import sys
    import re
    input = sys.stdin.readline
    N,Q = list(map(int, input().split()))
    S = list(input())
    L = []
    for _ in range(Q):
        temp = list(map(int, input().split()))
        L.append(temp)
    dp = [0] * N
    for i in range(1,N):
        if S[i] == "C" and S[i-1] == "A":
            dp[i] = dp[i-1] + 1
        else:
            dp[i] = dp[i-1]
    for j in range(Q):
        l,r = L[j]
        print(dp[r-1] - dp[l-1])
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = input()
W = [0 for i in range(N + 1)]
AC = [False for b in range(N + 1)]
for i in range(1, N):
    if S[i] == 'C' and S[i - 1] == 'A':
        W[i + 1] = W[i] + 1
        AC[i] = True
    else:
        W[i + 1] = W[i]

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

Submission status: Accepted

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

count_sum_list = [0]*(N+1)
start_A_pointa = [0]*(N+1)

for i in range(1,N+1):
    if i != N and S[i-1] == 'A' and S[i] == 'C':
        count_sum_list[i] = count_sum_list[i-1] + 1
        start_A_pointa[i] = 1
    else:
        count_sum_list[i] = count_sum_list[i-1]
#print(count_sum_list)

output_list = []

for _ in range(Q):
    l,r = map(int,input().split(' '))
    if start_A_pointa[r] == 1:
        output_list.append(count_sum_list[r]-count_sum_list[l-1] -1)
    else:
        output_list.append(count_sum_list[r]-count_sum_list[l-1])

for out in output_list:
    print(out)

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = input()
W = [0 for i in range(N + 1)]

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

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

Submission status: Accepted

Solution code:
import sys
def main():
    n, q = map(int, sys.stdin.readline().split())
    s = sys.stdin.readline().rstrip()
    lr = map(int, sys.stdin.read().split())
    lr = list(zip(lr, lr))

    cumsum = [None] * (n + 1)
    cumsum[0] = 0

    flag = False
    for i in range(n):
        t = s[i]
        if t == 'A':
            flag = True
            cumsum[i+1] = cumsum[i]
        else:
            if t == 'C' and flag:
                cumsum[i+1] = cumsum[i] + 1
            else:
                cumsum[i+1] = cumsum[i]
            flag = False

    for l, r in lr:
        res = cumsum[r] - cumsum[l]
        print(res)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

Submission status: Accepted

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


def main():
    N, Q = [int(x) for x in input().split()]
    S = input().strip()

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

    for _ in range(Q):
        x, y = [int(x) for x in input().split()]
        l = bisect.bisect_left(ac, x - 1)
        r = bisect.bisect_right(ac, y - 2)
        print(r - l)

    
    




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect
n,q=map(int,input().split())
s=list(input())
l=[0]*q
r=[0]*q
for i in range(q):
    l[i],r[i]=map(int,input().split())
cnt=[]
ans=0
a=[]
a1=[]
for j in range(1,n):
    if s[j-1]+s[j]=='AC':
        ans+=1
        a.append(j-1)
        a1.append(j)
        cnt.append([j-1,j,ans])
for k in range(q):
    print(bisect.bisect_right(a1,r[k]-1)-bisect.bisect_left(a,l[k]-1))
    #print(bisect.bisect_right(a1,r[k]-1),bisect.bisect_left(a,l[k]-1))
#print(cnt)
#print(a)
#print(a1)