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

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right


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


[N, Q] = ii()
S = input()
Q_list = [ii() for _ in range(Q)]

AC_idx = []
try:
    start_idx = 0
    while True:
        found_idx = S.index("AC", start_idx)
        AC_idx.append(found_idx)
        start_idx = found_idx + 1
except ValueError as e:
    pass

for q in Q_list:
    left_idx = bisect_left(AC_idx, q[0] - 1)
    right_idx = bisect_right(AC_idx, q[1] - 2)
    print(right_idx - left_idx)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

N, Q = map(int, raw_input().split())
S = raw_input()
cnt = [0] * (N + 1)
for i in range(N - 1):
    cnt[i + 2] = cnt[i + 1]
    if S[i] == 'A' and S[i + 1] == 'C':
        cnt[i + 2] += 1
for _ in range(Q):
    l, r = map(int, raw_input().split())
    ans = cnt[r] - cnt[l - 1]
    if cnt[l] != cnt[l - 1]:
        ans -= 1
    print ans

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
# coding:utf-8

import sys
# from collections import Counter, defaultdict

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

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    n, q = LI()
    s = 'X' + SI()
    Q = [LI() for _ in range(q)]

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

    for l, r in Q:
        print(ac[r] - ac[l])
    # return res


main()

Submission status: Accepted

Solution code:
nums = list(map(int, input().split()))
N, Q = nums[0], nums[1]
S = input()
ls = []
rs = []
for i in range(Q):
    nums = list(map(int, input().split()))
    ls.append(nums[0])
    rs.append(nums[1])

pattern = 'AC'

import re

results = re.finditer(pattern, S)
S_cum = [0 for _ in range(N)]
for r in results:
    S_cum[r.span()[1]-1] = S_cum[r.span()[0]] + 1
import numpy as np
S_cum = np.cumsum(S_cum)
for i in range(Q):
    print(S_cum[rs[i]-1] - S_cum[ls[i]-1])

Submission status: Accepted

Solution code:
from itertools import accumulate
N, Q = map(int, input().split())
S = input()
res = [0] * N
for i in range(N - 1):
    if S[i] + S[i + 1] == "AC":
        res[i + 1] = 1
resm = [0] + list(accumulate(res))
for i in range(Q):
    ans = 0
    l, r = map(int, input().split())
    if S[l] == "C":
        ans -= 1
    ans = resm[r] - resm[l]
    print(ans)

Submission status: Accepted

Solution code:
N, Q = list(map(int, input().split()))
S = input()
w = [0]
v = 0
for a in range(len(S)-1):
    if S[a] == 'A' and S[a+1] == 'C':
        v += 1
    w.append(v)
for n in range(Q):
    l, r = list(map(int, input().split()))
    print(w[r-1] - w[l-1])

Submission status: Accepted

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

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

#print(countlist)
for i in range(Q):
    #print(i)
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    ans = countlist[r] - countlist[l - 1]
    if S[l] == "C" and S[l - 1] == "A":
        #print(S[r], r)
        #print(100)
        ans -= 1
    if l == 0:
        ans = countlist[r]
    print(ans)
#print(countlist)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

S=input()
old=''
count=0
data=[0]*len(S)

for i  in range(len(S)):
    if old =='A' and S[i] =='C':
        count+=1
    data[i]=count
    old=S[i]

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

Submission status: Accepted

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

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

for j, k in Prob:
    print(numlist[k-1]-numlist[j-1])

Submission status: Accepted

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

Submission status: Accepted

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

la=[0 for i in range(n)]
lc=[0 for i in range(n)]
x=0
y=0
for i in range(n-1):
    if s[i]=="A" and s[i+1]=="C":
        x+=1
        y+=1
        
    la[i]=x
    lc[i+1]=y
        
for i in range(q):
    print(min(la[lr[i][1]-2]-la[lr[i][0]-2],lc[lr[i][1]-1]-lc[lr[i][0]-1]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
N, Q = map(int, input().split())
S = input()
cumsum = [0] * (N + 1)
for i in range(1, N):
    cumsum[i + 1] = cumsum[i] + (S[i - 1:i + 1] == 'AC')

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

Submission status: Accepted

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


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

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

cums = [0 for _ in range(N)]

s0 = None
cum = 0
for i,s in enumerate(S):
    s1 = s
    if s0=="A":
        if s1=="C":
            cum += 1
    s0 = s1
    cums[i] = cum

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

Submission status: Accepted

Solution code:
import bisect
N, Q = map(int, input().split())
S = input()
qlist = []
for i in range(Q):
    l, r = map(int, input().split())
    qlist.append((l,r))
Alist = [i for i, x in enumerate(S) if x == 'A']
Clist = [i for i, x in enumerate(S) if x == 'C']
AClist = []
for c in Clist:
    if Alist[bisect.bisect_left(Alist, c)-1] == c-1:
        AClist.append(Alist[bisect.bisect_left(Alist, c)-1])

for l, r in qlist:
    idxa = bisect.bisect_left(AClist, l-1)
    idxb = bisect.bisect_left(AClist, r-1)
    print(idxb - idxa)

Submission status: Accepted

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

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

S = S.replace("AC", "-+")
Sl = [0]
Sr = [0]
l = 0
r = 0
for i in range(N):
    if S[i] == "-":
        l += 1
    if S[i] == "+":
        r += 1
    Sl.append(l)
    Sr.append(r)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
ri = lambda: int(input())
rl = lambda: list(map(int,input().split()))
rr = lambda N: [ri() for _ in range(N)]
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')
OE = lambda x: print('Odd') if x%2 else print('Even')
INF = 10**18

N,Q=rl()
S=input()
L,R=[0]*Q,[0]*Q
for i in range(Q):
    L[i],R[i] = rl()
s = [0]*(N+2)
ss = [0]*(N+2)
for i in range(N-1):
    if S[i] == 'A' and S[i+1] == 'C':
        s[i] = 1
        s[i+1] = 1

ss[0] = s[0]
for i in range(1,N):
    ss[i] = ss[i-1] + s[i]

for i in range(Q):
    l,r = L[i],R[i]
    l -= 1
    r -= 1
    res = (ss[r] - ss[l-1])//2
    if s[r]==1 and s[l]==1 and S[r]=='A' and S[l]=='C':
        res -= 1
    print(res)

Submission status: Accepted

Solution code:
import sys

N,Q=map(int,sys.stdin.readline().rstrip().split())
S=list(sys.stdin.readline().rstrip())
count = [0 for i in range(N)]
phase=0
csum=0
for i,c in enumerate(S):
    if c=='A' and phase==0:
        phase=1
    elif c=='C' and phase==1:
        csum+=1
        phase=0
    elif c=='G' or c=='T':
        phase=0
    count[i]=csum
#print(count)
ans=[]
for i in range(Q):
    l,r=map(int,sys.stdin.readline().rstrip().split())
    ans.append(count[r-1]-count[l-1])
for a in ans:
    print(a)

Submission status: Accepted

Solution code:
# 1からn文字目までの部分文字列にACがいくつ含まれるか？

def main():
    N, Q = [int(n) for n in input().split()]
    cnt = [0] * N
    S = input()
    ans = [0] * Q

    cnt[0] = 0
    is_prev_a = S[0] == "A"
    for index in range(1, N):
        char = S[index]
        if char == "A":
            is_prev_a = True
            cnt[index] = cnt[index - 1]
        elif is_prev_a and char == "C":
            is_prev_a = False
            cnt[index] = cnt[index - 1] +  1
        else:
            is_prev_a = False
            cnt[index] = cnt[index - 1]
    for q in range(Q):
        l, r = [int(n) for n in input().split()]
        ans[q] = (cnt[r - 1] - cnt[l - 1])
    
    for i in ans:
        print(i)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def c_get_ac(N, Q, S, I):
    dp = [0] * N
    count = 0
    for k, c in enumerate(S):
        if c == 'C':
            if k != 0 and S[k - 1] == 'A':
                count += 1
                dp[k] += count
    for i in range(1, N):
        dp[i] = max(dp[i], dp[i - 1])

    ans_tmp = []
    for l, r in I:
        ans_tmp.append(dp[r - 1] - dp[l - 1])
    ans = '\n'.join(map(str, ans_tmp))
    return ans

N, Q = [int(i) for i in input().split()]
S = input()
I = [[int(i) for i in input().split()] for j in range(Q)]
print(c_get_ac(N, Q, S, I))

Submission status: Accepted

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

cumsum = [0]

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

for l, r in zip(ls, rs):
    print(cumsum[r-1] - cumsum[l-1])

Submission status: Accepted

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

c_array = [0 for x in range(n)]
a_array = [0 for x in range(n)]

for index, char in enumerate(s):
    if s[index] == "C" and s[index-1] == "A":
        tmp = a_array[index-1] + 1
    else:
        tmp = a_array[index-1]
    a_array[index] = tmp
for l, r in lr_array:
    print(abs(a_array[l-1]-a_array[r-1]))

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
s=input()
ls=[0]*n
i=1
while i < len(s):
  if s[i-1]+s[i]=="AC":
    ls[i]=1
  i+=1
for i in range(len(ls)-1):
  ls[i+1]=ls[i+1]+ls[i]

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

ac_accumulate = [0] * n
preva = False

for i, c in enumerate(s):
  if preva:
    if c == 'C':
      ac_accumulate[i] = ac_accumulate[i-1]+1
      preva = False
      continue
  preva = False
  if c == 'A': preva = True
  if i == 0: ac_accumulate[i] = 0
  else: ac_accumulate[i] = ac_accumulate[i-1]

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

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
s = input()
ac_cum_list = []
ac_cum = 0
ex_a = False
for c in s:
    if ex_a and c == "C":
        ac_cum += 1
    if c == "A":
        ex_a = True
    else:
        ex_a = False
    ac_cum_list.append(ac_cum)

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

Submission status: Accepted

Solution code:
import bisect
import sys
N, Q = [int(i) for i in input().split()]
S = input()
ind_ls = list()
for i in range(len(S) - 1):
    if S[i:i+2] == "AC":
        ind_ls.append(i)
        i += 1
        continue
    if S[i+1] != "A":
        i += 1
for i in range(Q):
    l, r = [int(i) for i in sys.stdin.readline().split()]
    l -= 1
    r -= 1
    print(bisect.bisect_left(ind_ls, r) - bisect.bisect_left(ind_ls, l))

Submission status: Accepted

Solution code:
def main():
    n, q = map(int, input().split())
    s = input()
    acs = [0] * len(s)
    for i in range(1, len(s)):
        acs[i] += acs[i - 1]
        if s[i - 1 : i + 1] == "AC":
            acs[i] += 1
    for _ in range(q):
        l, r = map(int, input().split())
        print(acs[r - 1] - acs[l - 1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N,Q=map(int,input().split())
S=input()
query=[[int(i) for i in input().split()]for i in range(Q)]
K=[0]*(N)
t=0
for i in range(N):
    a=0
    if t==1 and S[i]=='C':
        a=1
        t=0
    elif S[i]=='A':
        t=1
    else:
        t=0
    K[i]=a
L=[0]*(N+1)
for i in range(N):
    L[i+1]=L[i]+K[i]
#print(L,K)
for a,b,in query:
    a,b=a-1,b-1
    t=L[b+1]-L[a]
    if a>=1 and S[a]=='C' and S[a-1]=='A':
        t-=1
    print(t)

Submission status: Accepted

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

S = str(input())

L = []
for i in range(Q):
    l,r = map(int, input().split())
    L.append((l-1,r-1))
    
check = []
for i in range(N-1):
    if S[i:i+2] == "AC":
        check.append(i)
        
from bisect import bisect_left,bisect_right
for i in L:
    print(bisect_right(check, i[1]-1)-bisect_left(check, i[0]))

Submission status: Accepted

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

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

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

    print(w[l[1] - 1] - w[l[0] - 1])

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = input()
cnt = 0
last = ' '
x = []

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

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

Submission status: Accepted

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

at =[0]
for i in range(n-1):
    if s[i] == "A" and s[i+1] == "C":
        at.append(at[-1] + 1)
    else:
        at.append(at[-1])
for i in range(q):
    print(at[lr[i][1]-1] - at[lr[i][0]-1])

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
s = input()
cl = [0 for _ in range(N + 1)]

flg = False
cnt = 0
for i in range(N):
    if s[i] == 'A':
        flg = True
    elif flg:
        if s[i] == 'C':
            cnt += 1
        flg = False
    cl[i + 1] = cnt

for _ in range(Q):
    l, r = map(int, input().split())
    # [1,N]
    p = cl[r] - cl[l - 1]
    if l > 1:
        if s[l- 1] == 'C' and s[l - 2] == 'A':
            p -= 1
    print(p)

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = input()
S = S.replace('AC', 'ac')
ans = [0] * N
LR = [list(map(int, input().split())) for _ in range(Q)]

flag = False
count = 0
for num, s in enumerate(S):
    if flag is False:
        if s == 'a':
            flag = True
            ans[num] = count
            continue
        else:
            ans[num] = count
    else:
        if s == 'c':
            count += 2
            ans[num] = count
            flag = False
            continue
        else:
            ans[num] = count
            flag = False

for lr in LR:
    l, s = lr[0], lr[1]
    print((ans[s - 1] - ans[l - 1]) // 2)

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = input()
query = [list(map(int, input().split())) for _ in range(Q)]
counter = [0]
for i in range(1, N):
    if S[i - 1] == 'A' and S[i] == 'C':
        counter.append(counter[-1] + 1)
    else:
        counter.append(counter[-1])
for left, right in query:
    print(counter[right - 1] - counter[left - 1])

Submission status: Accepted

Solution code:
a = list(map(int,input().split()))
N = a[0]
Q = a[1]
numofac = [0 for i in range(N)]
S = input()
appear = 0
index = 1
while index < N:
    if S[index-1] == "A" and S[index] == "C":
        appear += 1
        numofac[index] = appear
        if index != N-1:
            numofac[index+1] = appear
        index += 2
    else:
        numofac[index] = appear
        index += 1
for i in range(Q):
    q = list(map(int,input().split()))
    print(str(numofac[q[1]-1] - numofac[q[0]-1]))

Submission status: Accepted

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


import sys

input = sys.stdin.readline

# 空白区切り2整数
n, q = list(map(int, input().split()))

# 1文字ずつのリスト
s = list(input())
s.append('Z')
count = []
cc = 0
count.append(0)
for i in range(1, len(s)):
    if s[i - 1] == 'A' and s[i] == 'C':
        cc += 1
    count.append(cc)
# print(count)

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

    print(count[r - 1] - count[l - 1])

Submission status: Accepted

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

N,Q=[int(x) for x in input().strip().split()]
S=input().strip()
n=[]
cnt=0
p=''
for s in S:
    if p=='A' and s =='C':
        cnt+=1
        p=''
    else:
        p=s
    n.append(cnt)

for _ in range(Q):
    l,r=[int(x) for x in input().strip().split()]
    ans = n[r-1]-n[l-1]
    print(ans)

Submission status: Accepted

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

def m():
    t = [0] * len(S)
    ans = [0] * len(S)
    prev = S[0]
    for i in range(1, len(S)):
        if prev != 'A':
            prev = S[i]
            continue
        if S[i] == 'C':
            t[i] += 1
        prev = S[i]
    ans[0] = t[0]
    for i in range(1, len(t)):
        ans[i] = ans[i-1] + t[i]

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

m()

Submission status: Accepted

Solution code:
def main():
    q = int(input().split()[1])
    s = input()
    a = make_array(s)
    for i in range(q):
        l, r = [int(x) - 1 for x in input().split()]
        print(a[r] - a[l])

def make_array(s):
    array = []
    ac_count = 0
    a_flag = False
    for c in s:
        if c == "A":
            a_flag = True
        elif c == "C":
            if a_flag:
                ac_count += 1
                a_flag = False
        else:
            a_flag = False

        array.append(ac_count)

    return array


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
import sys

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

ac_counter = np.zeros(len(S),dtype=np.int)
for i in range(len(S)-1):
    if S[i]=="A" and S[i+1]=="C":
        ac_counter[i+1] = ac_counter[i]+1
    else:
        ac_counter[i+1] = ac_counter[i]


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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# https://qiita.com/_-_-_-_-_/items/34f933adc7be875e61d0
# abcde	s=input()	s='abcde'
# abcde	s=list(input())	s=['a', 'b', 'c', 'd', 'e']
# 5(1つだけ)	a=int(input())	a=5
# 1 2	| x,y = s_inpl()   |	x=1,y=2
# 1 2 3 4 5 ... n 　	li = input().split()	li=['1','2','3',...,'n']
# 1 2 3 4 5 ... n 　	li = inpl()	li=[1,2,3,4,5,...,n]
# FFFTFTTFF 　	li = input().split('T')	li=['FFF', 'F', '', 'FF']

# INPUT
# 3
# hoge
# foo
# bar
# ANSWER
# n=int(input())
# string_list=[input() for i in range(n)]

import math
import numpy as np
import copy
from collections import defaultdict, Counter
from itertools import product
from bisect import bisect_left, bisect_right

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

N, Q = s_inpl()
S = input()
l, r = [], []
for _ in range(Q):
    li, ri = s_inpl()
    l.append(li)
    r.append(ri)

ls = []
for i in range(N-1):
    ls.append(S[i]+S[i+1] == "AC")

res = list(np.cumsum(ls))
res.insert(0, 0)

for li, ri in zip(l, r):
    print(res[ri-1] - res[li-1])

Submission status: Accepted

Solution code:
import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, Q] = [int(input_raw[0]), int(input_raw[1])]

    input_raw = read_func().strip().split()
    S = input_raw[0]
    AC_count = [0 for i in range(len(S) + 1)]
    for i in range(1, len(S)):
        if S[i - 1] + S[i] == "AC":
            AC_count[i] = AC_count[i - 1] + 1
        else:
            AC_count[i] = AC_count[i - 1]
    for i in range(Q):
        input_raw = read_func().strip().split()
        [L, R] = [int(input_raw[0]), int(input_raw[1])]
        print AC_count[R - 1] - AC_count[L - 1]


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

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

for x in X:
    print(L[x[1]-1]-L[x[0]-1])

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = input()
wa = [0] * (N + 1)
flag = "X"
for i in range(N):
    if S[i] == "A":
        flag = "A"
        wa[i+1] = wa[i]
    elif flag == "A" and S[i] == "C":
        wa[i+1] = wa[i] + 1
        flag = "X"
    else:
        flag = "X"
        wa[i+1] = wa[i]
        
for q in range(Q):
    left,  right = map(int, input().split())
    print(wa[right] - wa[left])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a="AC"
arr=[0]*(n+1)
s=input()
for i in range(1,n+1):
    arr[i]=arr[i-1]+s[i-1:i+1].count(a)
for _ in range(m):
    x,y=map(int,input().split())
    print(arr[y-1]-arr[x-1])

Submission status: Accepted

Solution code:

n, q = map(int, input().split())
s = input()
start = [0]
count = 0
for i in range(len(s)-1):
    if s[i]+s[i+1] == "AC":
        count += 1

    start.append(count)


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

Submission status: Accepted

Solution code:

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

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

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

Submission status: Accepted

Solution code:


n, q = map(int, input().split())
s = input()
start = [0]
count = 0
for i in range(len(s)-1):
    if s[i]+s[i+1] == "AC":
        count += 1

    start.append(count)


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

Submission status: Accepted

Solution code:
n, q = [int(i) for i in input().split(" ")]
s = input()
ss = [0] * (n + 1)

for i in range(2, n + 1):
    ss[i] = ss[i - 1] + (1 if s[i - 2:i] == "AC" else 0)

l = [0] * q
r = [0] * q

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

Submission status: Accepted

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

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

for i in range(n - 2):
    cnt[i + 1] += cnt[i]

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

Submission status: Accepted

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

num = [0] * N

pre = ''
n = 0
for i in range(N):
    if pre == 'A' and S[i] == 'C':
        n += 1
    num[i] = n

    pre = S[i]


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

Submission status: Accepted

Solution code:
def main():
  N, Q = list(map(int, input().split()))
  S = input()
  
  #ACをカウントし、累積和を求める
  C = [0]
  c = 0
  for i in range(N-1):
    if ('A' == S[i]):
      if ('C' == S[i+1]):
        c += 1
    C.append(c)
  for i in range(Q):
    l, r = list(map(int, input().split()))
    print(C[r-1] - C[l-1])
main()

Submission status: Accepted

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

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

    # print(a)
    ans = 0
    for l, r in lr:
        ans = a[r] - a[l]
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
query = []
n,q = map(int,input().split())
s = input()
for i in range(q):
    l,r = map(int,input().split())
    query.append([l-1,r-1])

flag = False
loc = [0 for i in range(n)]
tot  = 0

for i in range(n):
    if flag and s[i] == "C":
        tot += 1
        loc[i]=tot

    if s[i] == "A":
        flag = True
    else:
        flag = False
    loc[i] = tot

for qs in query:
    print(loc[qs[1]]-loc[qs[0]])

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import bisect

N, Q = list(map(int, input().split()))
S = input() + ' '
x, y = [], []

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

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

    idx = [-1, -1]

    idx[0] = bisect.bisect_left(x, l)
    idx[1] = bisect.bisect_right(y, r)

    print(idx[1] - idx[0])

Submission status: Accepted

Solution code:
import bisect
N, Q = [int(x) for x in input().split()]
S = str(input())

ac_list = []
for (idx, (s1, s2)) in enumerate(zip(S[:-1], S[1:])):
  if s1 == 'A' and s2 == 'C':
    ac_list.append(idx+1)

for _ in range(Q):
  l, r = [int(x) for x in input().split()]
  index_l = bisect.bisect_left(ac_list, l)
  index_r = bisect.bisect_left(ac_list, r)
  print(index_r - index_l)

Submission status: Accepted

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

AC  = [0 for _ in range(N)]
lastA=False

for i, s in enumerate(S):
  if lastA and s=='C':
    AC[i] = AC[i-1] +1 
    lastA=False
    continue
  elif s=='A':
    AC[i] = AC[i-1]
    lastA=True
    continue
  else:
    AC[i] = AC[i-1]
    lastA=False

for i in range(Q):
  print(AC[R[i]-1] - AC[L[i]-1])