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

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

Submission status: Accepted

Solution code:
# u+++さんの解放
from itertools import accumulate


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

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

flg2 = [0] + flg
flg2 = list(accumulate(flg2))

for a in A:
    print(flg2[a[1]-1] - flg2[a[0]-1])

Submission status: Accepted

Solution code:
# まずは自力で。
# 次に累積和。

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

L = []
R = []

for i in range(q):
    a,b = map(int, input().split())
    L.append(a)
    R.append(b)


ans = [0]

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

        
for i in range(q):
    print(ans[R[i]-1]-ans[L[i]-1])

Submission status: Accepted

Solution code:
#18:20
n,q = map(int,input().split())
s = input()
ac = [0]
for i in range(1,n):
  if s[i-1:i+1] == 'AC':
    ac.append(ac[-1] + 1)
  else:
    ac.append(ac[-1])
ac.append(0)
#print(ac)
for _ 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()
lr = [tuple(map(int, input().split())) for _ in range(Q)]
ac_indexes = [0]
ac = 0
for i in range(1, N):
    if S[i - 1] == "A" and S[i] == "C":
        ac += 1
    ac_indexes.append(ac)
for l, r in lr:
    print(ac_indexes[r - 1] - ac_indexes[l - 1])

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
s = input()
cumulative_sum = [0]*n
for i in range(1,n,1):
    if s[i-1:i+1]=="AC":
        cumulative_sum[i] = cumulative_sum[i-1]+1
    else:
        cumulative_sum[i] = cumulative_sum[i-1]
for i in range(q):
    li,ri = map(int,input().split())
    print(cumulative_sum[ri-1]-cumulative_sum[li-1])

Submission status: Accepted

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

ac=[0]*n #0番目からn番目までの部分文字列でacがいくつつくれるか
ac[0]=0
def isac(i):
  if s[i]=='A' and s[i+1]=='C':
    return 1
  else:
    return 0
ac[1]=isac(0)
for i in range(n-1):
    ac[i+1] = ac[i] + isac(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())
import bisect
str = list(input())
index = []
for i in range(n-1):
    if str[i] == "A" and str[i+1] == "C":
        index.append(i)
index.sort()
li = []
counter = 0
for i in range(q):
    s,t = map(int, input().split())
    head = bisect.bisect_left(index, s-1)
    tail = bisect.bisect_left(index, t-1)
    print(tail - head)

Submission status: Accepted

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

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

for i in range(q):
      print(L2[L[i][1]-1]-L2[L[i][0]-1])

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = input()
lr = [tuple(map(int, input().split())) for _ in range(Q)]
acindex_list = []
ac = 0
old = ""
for c in S:
    if old == "A" and c == "C":
        ac += 1
    old = c
    acindex_list.append(ac)
for l, r in lr:
    print(acindex_list[r - 1] - acindex_list[l - 1])

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,Q = input().split()
N,Q = int(N),int(Q)
S = input()
l,r = [],[]
for i in range(Q):
    l_,r_ = input().split()
    l_,r_ = int(l_)-1,int(r_)-1
    l.append(l_)
    r.append(r_)
    
A = [0]
sum_ = 0
for i in range(1,N):
    if(S[i-1]=="A" and S[i]=="C"):
        sum_ += 1
    A.append(sum_)

for i in range(Q):
    if(l[i]==0):
        num = r[i]
        print(A[r[i]])
    else:
        sa = A[r[i]]-A[l[i]]
        print(sa)

Submission status: Accepted

Solution code:
import bisect

n,q = map(int,input().split())
s = input()
l=[]
r=[]
a = []
c = []
for i in range(q):
    l1,r1 = map(int,input().split())
    l.append(l1)
    r.append(r1)
for i in range(n-1):
    if s[i] + s[i+1] == 'AC':
        a.append(i+1)
        c.append(i+2)
for i in range(q):
    ans = 0
    ans = bisect.bisect_right(c,r[i]) - bisect.bisect_left(a,l[i])
    print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

cum_counts=[0]*n
for i in range(1,n):
  cum_counts[i]=cum_counts[i-1]+counts[i-1]

#print(counts)
#print(cum_counts)

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

Submission status: Accepted

Solution code:
from itertools import accumulate

N, Q = map(int, input().split())
S = input()
A = [list(map(int, input().split())) for i in range(Q)]
# リストに入れておく
#print(A)

flg = []
for i in range(N-1):
    tmp_S = S[i:i+2]
    if tmp_S == 'AC':
        flg.append(1)
    else:
        flg.append(0)
# print(len(flg)) #N-1になっていることを確認

ans = []
ans = [0] + flg #繋げて
ans = list(accumulate(ans)) #累積和にする
#print(ans)

for li in A:
    print(ans[li[1]-1] - ans[li[0]-1] )

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,Q = [int(i) for i in input().split()]
S = str(input())
lrlist = []
for i in range(Q):
    lrlist.append([int(i)-1 for i in input().split()])

#print(S)
#print(lrlist)

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


for l,r in lrlist:
    print(Asite[r]-Asite[l])

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, Q = map(int,input().split())
S = input()
S_array = [0] * N
for i in range(N):
    S_array[i] = S_array[i-1]
    if S[i-1] == 'A' and S[i] == 'C':
        S_array[i] += 1
for _ in range(Q):
    l, r = map(int,input().split())
    print(S_array[r-1]-S_array[l-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
s = input()
    
ans = 0
ls = [0]
for i in range(len(s)-1):
    if s[i] == "A" and s[i+1] == "C":
        ans += 1
        ls.append(1+ls[i-1])
    else:
        ls.append(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()
lr = [list(map(int, input().split())) for i in range(Q)]
# 1文字目からi文字目までのACの個数
dp = [0]*(N+1)
for i in range(1, N):
    if S[i-1]+S[i] == 'AC':
        dp[i+1] = dp[i]+1
    else:
        dp[i+1] = dp[i]
for l, r in lr:
    print(dp[r]-dp[l])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
l=list(input())
count=0
clist=[0]
for i in range(1,n):
  if l[i-1]=="A" and l[i]=="C":
    count+=1
  clist.append(count)
for i in range(m):
  i1,i2=map(int,input().split())
  if i1==1:
    ans=clist[i2-1]
  elif l[i1-1]=="C" and l[i1-2]=="A":
    ans=clist[i2-1]-clist[i1-2]-1
  else:
    ans=clist[i2-1]-clist[i1-2]
  print(ans)

Submission status: Accepted

Solution code:
N,q=map(int,input().split())
a=input()
n=0
b=[0]
for i in range(1,N):
  if a[i-1]=="A" and a[i]=="C":
    n+=1
  b.append(n)
for _ in range(q):
  l,r=map(int,input().split())
  if l!=1:
    print(b[r-1]-b[l-1])
  else:
    print(b[r-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
tmp = list(map(int, input().split()))
n = tmp[0]
q = tmp[1]
s = input()

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

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# ABC122-C
N, Q = map(int, input().split())
S = input()
lr = [list(map(int, input().split())) for _ in range(Q)]
cnt_list = [0] * N
tmp = 0
for i in range(N-1):
    cnt_list[i] = tmp
    if S[i] == "A" and S[i+1] == "C":
        tmp += 1
cnt_list[N-1] = tmp
##print(cnt_list)
for i in range(Q):
    l = lr[i][0] - 1
    r = lr[i][1] - 1
    print(cnt_list[r] - cnt_list[l])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
s = list(input())
l = []
r = []
for _ in range(q):
    line = list(map(int, input().split()))
    l.append(line[0])
    r.append(line[1])
ac = []
count = 0
for i in range(1, n):
    if s[i-1] == "A" and s[i] == "C":
        count += 1
    ac.append(count)
for i in range(q):
    right = ac[r[i]-2]
    if l[i] < 2:
        left = 0
    else:
        left = ac[l[i]-2]
    print(right-left)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
s = input()
x = [0] * (n + 1)
for i in range(n):
    x[i + 1] = x[i] + 1 * (s[i:i + 2] == 'AC')
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()
Q = [list(map(int ,input().split())) for _ in range(q)]

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

	tmp = S[i-1]

for l,r in Q:
	ans = cnt[r] - cnt[l-1]

	if 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=list(str(input()))
l=[]
r=[]
ans=0
x=[0]
for i in range(q):
  l1,r1=map(int,input().split())
  l.append(l1)
  r.append(r1)

for j in range(0,n-1):
  if s[j]=="A" and s[j+1]=="C":
    ans+=1
    x.append(ans)
  else:
    x.append(ans)

for k in range(0,q):
  print(x[r[k]-1]-x[l[k]-1])

Submission status: Accepted

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

for i in range(1,N):
  if S[i-1:i+1]=="AC":
    cnt=cnt+1
  T.append(cnt)
for j in range(Q):
  print(T[R[j]-1]-T[L[j]-1])

Submission status: Accepted

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

sl = list(input())

pointl = []
point = 0
before_s = ""
for s in sl:
    if before_s == "A" and s=="C":
        point += 1
    before_s = s
    pointl.append(point)
    
for _ in range(q):
    l,r = map(int,input().split())
    print(pointl[r-1] - pointl[l-1])

Submission status: Accepted

Solution code:
n,q= map(int,input().split())
s=input()
dp=[0]*n
k=True
for i in range(1,n):
    dp[i]=dp[i-1]
    if s[i-1]=="A" and s[i]=="C":
        dp[i]+=1
for i in range(q):
    l,r=map(int,input().split())
    print(dp[r-1]-dp[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)]
#print(LR)

C = [0 for _ in range(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]
#print(C)
for l,r in LR:
  print(C[r]-C[l])

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
S = list(input())
num = [0 for _ in range(len(S))]
tmp = 0
for i in range(len(S) - 1):
    if S[i] == 'A' and S[i + 1] == 'C':
        tmp += 1
    num[i + 1] = tmp
ans = [0 for _ in range(q)]
for i in range(q):
    l, r = map(int, input().split())
    ans[i] = str(num[r - 1] - num[l - 1])
print('\n'.join(ans))

Submission status: Accepted

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

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

    prev = buf[i+1]

# print(buf)

for _ in range(Q):
    l, r = list(map(lambda x: int(x), input().split(' ')))
    l -=1
    r -=1
    ans = buf[r] - buf[l]
    print(ans)

Submission status: Accepted

Solution code:
def main():
    n,q = map(int, input().split())
    S = input()
    N = [0]*(n+1)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np

N, Q = map(int, input().split())
S = input()
t = [0] * (N+1)
ans = []

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

for q in range(Q):
    q_l, q_r = map(int, input().split())
    ans.append(t[q_r-1]-t[max(q_l-1, 0)])

for a in range(Q):
    print(int(ans[a]))

Submission status: Accepted

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

for i in range(N):
    if S[i] == 'A':
        cnt = 1
    elif S[i] == 'C':
        if cnt == 1:
            cnt = 0
            num += 1
    else:
        cnt = 0
    check.append(num)

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

Submission status: Accepted

Solution code:
from itertools import accumulate
N, Q =map(int, input().split())
s = input()
AC = [0]*(N-1)
for i in range(N-1):
  if s[i:i+2] == 'AC':
    AC[i] = 1   
B = [0] +AC
B = list(accumulate(B))
for i in range(Q):
  l,r = map(int, input().split())
  print(B[r-1]-B[l-1])

Submission status: Accepted

Solution code:
from itertools import accumulate
N, Q =map(int, input().split())
s = input()

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

AC = [0]*(N-1)

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

B = [0] +AC
B = list(accumulate(B))
for i in lr:
  print(B[i[1]-1]-B[i[0]-1])

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
s = input()
ac = [0] * 100010
for i in range(n):
    if s[i : i + 2] == "AC":
        ac[i + 1] = ac[i] + 1
    else:
        ac[i + 1] = ac[i]

for i 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()
ac_list = [0]*N
for i in range(N-1):
    if S[i] == 'A' and S[i + 1] == 'C':
        ac_list[i+1] = ac_list[i]+1
    else:
        ac_list[i+1] = ac_list[i]
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 = map(int,input().split())
s = list(input())
t = [0]*len(s)
list_q = [list(map(int,input().split())) for i in range(q) ]
count = 0
for i in range(len(s)-1):
    if s[i] == "A" and s[i+1] =="C":
        count += 1
    t[i+1] = count
for i in range(q):
    j,k = list_q[i][0],list_q[i][1]
    print(t[k-1]-t[j-1])

Submission status: Accepted

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

Submission status: Accepted

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

ans = [0] * N

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

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

Submission status: Accepted

Solution code:
from sys import stdin
import bisect

n,q = [int(x) for x in stdin.readline().rstrip().split()]
s = stdin.readline().rstrip()
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(q)]
lin = []
point = 0
for i in range(n-1):
    if s[i] + s[i+1] == "AC":
        lin.append(i+1)
for j in range(q):
    hi = bisect.bisect(lin,li[j][1]-1)
    lo = bisect.bisect(lin,li[j][0]-1)
    print(hi-lo)

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)
# print(t)
for j in range(q):
    l, r = map(int, input().split())
    print(t[r - 1] - t[l - 1])

Submission status: Accepted

Solution code:
import sys

N, Q = map(int, input().split())
S = input()
P = [[int(v) - 1 for v in sys.stdin.readline().split()] for _ in range(Q)]
X = [0] * (N + 1)

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


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

Submission status: Accepted

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

ans = [0 for _ in range(n)]

for i in range(n-1):
    if string[i] == 'A' and string[i+1] == 'C':
        ans[i+1] = ans[i] +1
    else:
        ans[i+1] = ans[i]
        
for x,y in l:
    print(ans[y-1] - ans[x-1])

Submission status: Accepted

Solution code:
#import copy
def main():
    # x,y = map(int,input().split())           x=1,y=2
    # a = input().split()                      a=['1','2','3',...,'n']
    # a = list(map(int,input().split()))       a=[1,2,3,4,5,...,n]
    # li = input().split('T')	              FFFTFTTFF => li=['FFF', 'F', '', 'FF']
    # 複数行の「1 2 3 4」型の入力を一配列に
    # x = sorted([list(map(int, input().split())) for _ in range(n)])
    # ソート x.sort(key=lambda y:y[1])
    # [chr(i) for i in range(97, 97+26)] 英語小文字リスト
    # [chr(i) for i in range(65, 65+26)] 英語大文字リスト
    # ord(c) chr(2) alphabet <=> number
    n,q = map(int,input().split()) 
    s=input()
    cnt=[0 for _ in range(n+1)]
    for i in range(n):
        cnt[i+1]=cnt[i]+(1 if s[i:i+2]=="AC" else 0)
    for _ in range(q):
        l,r = map(int,input().split())
        print(cnt[r-1]-cnt[l-1])
main()

Submission status: Accepted

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

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

Simos = [0] * n
Simos[0] = Sev[0]
for i in range(1, n):
  Simos[i] = Simos[i-1] + Sev[i]
    
for i in range(q):
  l, r = map(int, input().split())
  l = l-1
  r = r-1
  r = r-1
  if l == 0:
    print(Simos[r])
  else:
    print(Simos[r] - Simos[l-1])

Submission status: Accepted

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

t = [0] * (N +1)


for i in range(N):
    t[i+1] = t[i] + (1 if s[i:i+2]=="AC" else 0)



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

Submission status: Accepted

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

# 最初から数えておく
#C=[1 if S[i:i+2]=='AC' else 0 for i in range(N-1)]
C=[0]*(N+1)
for i in range(N):
    C[i+1]=C[i]+(1 if S[i:i+2]=='AC' else 0)
#print(C)
#exit()

#print()
#print("#"*20)
for q in range(Q):
    l,r=map(int,input().split())
    #print(S[l-1:r].count("AC"))
    #print(sum(C[l-1:r-1]))
    print(C[r-1]-C[l-1])

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
s = input()
acl = [0]*n #'AC'のCの個数
for i in range(n-1):
  if s[i] == 'A' and s[i+1] == 'C':
    acl[i+1] = acl[i] + 1
  else:
    acl[i+1] = acl[i]
for i in range(q):
  l,r = map(int,input().split())
  l -= 1
  r -= 1
  count = acl[r] - acl[l]
  print(count)

Submission status: Accepted

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

Submission status: Accepted

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

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


def count_from_first(l, r):
    return from_first[r] - from_first[l]


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

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

Submission status: Accepted

Solution code:
from itertools import accumulate
N, Q = map(int,input().split())
S = [1 if i=='1' else 0 for i in input().replace("AC","10")]
s = list(accumulate(S))
lr = []
for i in range(Q):
    lr.append(tuple(map(int,input().split())))
for i in lr:
    l = s[i[0]-2] if i[0]-2 >= 0 else 0
    r = s[i[1]-2] if i[1]-2 >= 0 else 0
    print(r-l)

Submission status: Accepted

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

a = [0] * n
num = 0

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

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = str(input())
W = [0] * (N+1)
L = []
R = []
for q in range(Q):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)

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

for q in range(Q):
    print(W[R[q]-1]-W[L[q]-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from sys import stdin
import bisect

N,Q = list(map(int,stdin.readline().strip().split()))
S = input().strip()

P = [0]*N
cnt = 0

for i in range(1,N):
    if S[i-1:i+1] == 'AC':
        cnt+=1
    P[i] = cnt

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

Submission status: Accepted

Solution code:
from sys import stdin
import numpy as np
n, q = map(int, stdin.readline().rstrip().split())
s = input()
lr = [list(map(int, stdin.readline().rstrip().split())) for _ in range(q)]
cum = np.array([0 for _ in range(n-1)])
for i in range(n-1):
    if s[i:i+2] == "AC":
        cum[i] = 1
cum2 = np.cumsum(cum)
for l, r in lr:
    if l == 1: print(cum2[r-2])
    else: print(cum2[r-2] - cum2[l-2])

Submission status: Accepted

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

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+1)
cnt=0
for i in range(1,n+1):
    if s[i-1]+s[i]=="AC":
        cnt +=1
    A[i]=cnt

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()
count = [0]*n
for i in range(1, n):
    count[i] = count[i-1]
    if s[i - 1: i + 1] == "AC":
        count[i] += 1

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
s=input()
a=[0 for _ in range(n)]
for i in range(n-1):
  a[i+1]=a[i]+(1 if s[i:i+2]=="AC" else 0)
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()
a = [0]*(len(s)+5)

for i in range(len(s)):
    if s[i:i+2] == 'AC':
        a[i+2] = a[i+1]+1
    else:
        a[i+2] = a[i+1]

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

Submission status: Accepted

Solution code:
import bisect

N,Q = map(int,input().split())
S = input()
a = [input().split() for l in range(Q)]
x = []
for i in range (0,N-1):
  if (S[i] == "A") and (S[i+1] == "C"):
    x.append(i)
for k in range (0,Q):
  l = int(a[k][0]) - 1
  r = int(a[k][1]) - 1
  p = bisect.bisect_left(x,l)
  q = bisect.bisect_left(x,r)
  print(q-p)

Submission status: Accepted

Solution code:
N, Q = [int(x) for x in input().split()]
S = input()
lr = [[int(x)-1 for x in input().split()] for _ in range(Q)]
lst = [0] * N
for i in range(N-1):
    lst[i+1] = lst[i] + (S[i] == 'A' and S[i+1] == 'C')
for l, r in lr:
    print(lst[r]-lst[l])

Submission status: Accepted

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

count_list = [0] * (N+1)
count = 0
for n in range(N-1):
    if (S[n] == 'A' and S[n+1] == 'C'):
        count += 1
    count_list[n+2] = count

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

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

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
s = input()
t = [0 for _ in range(n+1)]
for i in range(n):
    t[i+1] = t[i] + (1 if s[i:i+2] == "AC" else 0)

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

Submission status: Accepted

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

for _ in range(Q):
  start,end = map(int,input().split())
  print(arr[end-1]-arr[start-1])

Submission status: Accepted

Solution code:
n, m = 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 i in range(m):
    a, b = map(int, input().split())
    print(t[b-1] - t[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:

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

Submission status: Accepted

Solution code:
from bisect import bisect_left
import sys
sys.setrecursionlimit(10**9)
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))

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

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

for i in range(Q):
    l, r = inpl()
    Nl = bisect_left(ACs,l-1)
    Nr = bisect_left(ACs,r-1)
    print(Nr-Nl)