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()
lr = []
S_temp = []
S_temp.append(0)
for i in range(1,N):
    if S[i-1] == "A" and S[i] == "C":
        S_temp.append(S_temp[i-1] + 1)
    else:
        S_temp.append(S_temp[i-1])
for i in range(Q):
    a,b = map(int,input().split())
    lr.append([a-1,b-1])

for i in range(Q):
    print(S_temp[lr[i][-1]] - S_temp[lr[i][0]])

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = input()
a = [0]
total = 0
for k in range(1,N, 1):
	if S[k - 1] == 'A':
		if S[k] == 'C':
			total = total + 1
	a.append(total)
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()
memo = [0]*(N+1)
for i in range(N-1):
    if S[i] == 'A' and S[i+1] == 'C':
        memo[i+1] = memo[i]+1
    else:
        memo[i+1] = memo[i]
ans = []
for _ in range(Q):
    l, r = map(int, input().split())
    ans.append(memo[r-1]-memo[l-1])

print('\n'.join(map(str, ans)))

Submission status: Accepted

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

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 = str(input())
SD = {}

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

for q in range(1, Q+1):
    l, r = map(int, input().split())
    print(SD.get(r-1, 0)-SD.get(l-1, 0))

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
N,Q = map(int,input().split())
S = input()
Slist = [0 for x in range(0,N)]
L = list()
R = list()
number = 0

for x in range(0,N-1):
    if S[x] is 'A' and S[x+1] is 'C':
        number += 1
    Slist[x+1] = number

for x in range(0,Q):
    l,r = map(int,input().split())
    L.append(l)
    R.append(r)

for x in range(0,Q):
    answer = Slist[R[x]-1] - Slist[L[x]-1]
    print(answer)

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon Apr  8 10:49:27 2019

@author: adachi-lab
"""


input_1 = input()
S = input()
l = []
r = []

N = input_1.split()[0]
Q = input_1.split()[1]

for i in range(int(Q)):
    input_3 = input()
    l.append(int(input_3.split()[0]))
    r.append(int(input_3.split()[1]))
    
s_1 = []
x = 0
for w in range(len(S)-1):
    if S[w] == 'A' and S[w+1] == 'C':
        x += 1
        s_1.append(x)
    else:
        s_1.append(x)
        
s_1.insert(0,0)
w = []

for j in range(len(l)):
    p = s_1[r[j]-1]-s_1[l[j]-1]
    w.append(p)
    
for t in range(len(w)):
    print(w[t])

Submission status: Accepted

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

rightmax = [0 for i in range(N+1)]
before = S[0]
nowAC = 0
for i, c in enumerate(S):
    if before == "A" and c == "C":
        nowAC += 1
    before = c
    rightmax[i+1] = nowAC
for query in LR:
    l, r = map(int, query.split(" "))
    print(rightmax[r] - rightmax[l])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
N,Q = map(int,sys.stdin.readline().rstrip().split())
S = sys.stdin.readline().rstrip()
D = [0]
DD = 0
for i in range(1,len(S)):
  if S[i-1] + S[i] == "AC":
    DD += 1
  D.append(DD)
for _ in range(Q):
  l,r  = map(int,sys.stdin.readline().rstrip().split())
  print(D[r-1]- D[l-1])
  del l
  del r

Submission status: Accepted

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

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

for l,r in qs:
    print(cums[r] - cums[l])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#c
N,Q = list(map(int,input().split()))
S = input()
L = []
R = []
for i in range(Q):
    a = list(map(int,input().split()))
    L.append(a[0])
    R.append(a[1])

S_count = []
count = 0
A_flag = False

for i in range(len(S)):
    if A_flag == True:
        if S[i] == "C" :
            count += 1
   
    if S[i] == "A" :
        A_flag = True
    else:
        A_flag = False
    S_count.append(count)

for i in range(Q):
    print(S_count[R[i] - 1] - S_count[L[i] - 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)]
a=[0]*n
for i in range(n-1):
    if s[i]=='A' and s[i+1]=='C':
        a[i]=1
        a[i+1]=1
S=[0]*n
S[0]=a[0]
for i in range(1, n):
    S[i]=S[i-1]+a[i]
S=[0]+S
for l, r in lr:
    print(S[r]//2-(S[l-1]+1)//2)

Submission status: Accepted

Solution code:
N, Q = (int(i) for i in input().split())
S = input()

counts = 0
totals = [0]
for i in range(1, N):
  if S[i-1] == 'A' and S[i] == 'C':
    counts += 1
  totals.append(counts)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
L, R = [None] * Q, [None] * Q

S = input()

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

counts = [0] * N
count_tmp = 0
is_before_char_A = False

for i in range(N):
    if S[i] == 'A':
        is_before_char_A = True
        counts[i] = count_tmp
        continue
    if S[i] == 'C' and is_before_char_A:
        count_tmp += 1

    counts[i] = count_tmp
    is_before_char_A = False
    #if S[i-1] == 'A' and S[i] == 'C':
    #    count_tmp += 1

# print(counts)

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

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
L, R = [None] * Q, [None] * Q

S = input()

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

counts = [0] * N
count_tmp = 0

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

# print(counts)

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

Submission status: Accepted

Solution code:
length, quests = map(int, input().rstrip().split())
string = input()
totals = [0]

count = 0
for i in range(1, len(string)):
    if string[i-1] == "A" and string[i] == "C":
        count += 1
    totals.append(count)

for i in range(quests):
    left, right = map(int, input().rstrip().split())
    print(totals[right-1] - totals[left-1])

Submission status: Accepted

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

n = [0]
c = 0
for i in range(1, len(s)):
    if s[i-1:i+1] == 'AC':
        c += 1
    n.append(c)

for (l, r) in l_r:
    print(n[r - 1] - n[l - 1])

Submission status: Accepted

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

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

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

for i in list_lr:
    l, r = i[0], i[1]
    print(t[r-1]-t[l-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:


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

    # maeshori
    count = [0] * len(S)

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

    # calc cumsum
    for i in range(len(S)-1):
        count[i+1] += count[i]

    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:
nq = list(map(int,input().split()))
q=nq[1]
s=list(input())
lr=[0 for i in range(q)]
for i in range(q):
    lr[i]=list(map(int,input().split()))
c=[0 for i in range(len(s))]
for i in range(len(s)):
    if i ==0:
        c[i]=0
    else:
        if s[i-1]=='A' and s[i]=='C':
            c[i] = c[i-1]+1
        else:
            c[i] = c[i-1]
for i in range(q):
    print(c[lr[i][1]-1]-c[lr[i][0]-1])

Submission status: Accepted

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

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

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

Submission status: Accepted

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

f = [0]
for i in range(1,int(N)):
  if (s[i-1]== 'A')&(s[i] == 'C'):
    f.append(f[i-1]+1)
  else :
    f.append(f[i-1])
  
for i in range(int(Q)):
  a,b = map(int,input().split(' '))
  print(f[b-1]-f[a-1])

Submission status: Accepted

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

c = [0] * (n + 1)

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

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

Submission status: Accepted

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

count = 0
counts = []
prev = ''
for c in list(s):
    if prev + c == 'AC':
        count += 1
    counts.append(count)
    prev = c

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

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

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

Submission status: Accepted

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

atgc_list= []

flag = 0
memo =0

for i in range (len(S)):
    if S[i]=='A':
        flag = 1
    elif flag == 1 and S[i] == 'C':
        memo+=1
        flag = 0
    elif S[i] in ['T','G','C']:
        flag = 0
    atgc_list.append(memo)
        

for j in range (Q):
    l, r = map(int,input().split())
    low = atgc_list[l-1]
    high = atgc_list[r-1]
    print(high - low)

Submission status: Accepted

Solution code:
import sys

n, q = map(int, sys.stdin.readline().split())
s = sys.stdin.readline()

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

for i in range(q):
    l, r = map(int, sys.stdin.readline().split())
    print(elist[r] - elist[l])

Submission status: Accepted

Solution code:
import sys

n, q = map(int, sys.stdin.readline().split())
s = sys.stdin.readline()

mlist = [0] * q
for i in range(q):
    mlist[i] = list([int(i) for i in sys.stdin.readline().split()])

elist = [0] * (n+1)

for i in range(n - 1):
    tmp = s[i:i+2]
    if 'AC' in tmp:
        elist[i + 2] = elist[i+1] + 1
    else:
        elist[i + 2] = elist[i+1]

for i in range(q):
    l, r = mlist[i]
    print(elist[r] - elist[l])

Submission status: Accepted

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

acn=[0 for i in range(N)]
count=0
for i in range(1,N):
  if S[i-1]+S[i]=="AC":
    count+=1
  acn[i]=count
for i in range(Q):
  l=lr[i][0]
  r=lr[i][1]
  print(acn[r-1]-acn[l-1])

Submission status: Accepted

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

result = 0
for i in range(q):
	num = counter[a[i][1]] - counter[a[i][0]]
	result += num
	print(num)

Submission status: Accepted

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

for i in range(Q):
    lq,rq = map(int,input().split())
    s = S[lq-1:rq]
    count = 0
    while(s.find('A') != -1):
        j = s.find('A')
        if(s[j:j+2] == 'AC'):
            count+=1
            s = s[j+2:]
        else:
            s = s[j+1:]
    print(count)
"""
#愚直なやり方だとTLEになってしまう。
#累積和とよばれるテクニックを使う
#https://qiita.com/drken/items/56a6b68edef8fc605821#問題-3-atcoder-abc-122-c---get-ac

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

#区間配列
a = [0] * len(S)
#累積和配列
s = [0] * (len(S) +1)

#左がAである文字Cは何番目にあるか求める
for i in range(len(S)):
    if S[i] == 'C':
        if S[i-1] == 'A':
            a[i] = 1 #i番目に'AC'のCがある (添字が0から始まるため実際にはi-1番目 i番目は'A')

#累積和を計算する
for i in range(1,len(a)+1):
    s[i] = s[i-1] + a[i-1]

#区間内にその文字があるか求める

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

Submission status: Accepted

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

c = [0]
n = 0

for i in range(1,len(S)):
    if S[i-1:i+1] == 'AC':
        n += 1
    c.append(n)

for x in lr:
    print(c[x[1]-1]-c[x[0]-1])

Submission status: Accepted

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

List.append(0)   
for i in range(Q):
  l, r = map(int, input().split())
  if List[l-2] == List[l-1]:
    print(List[r-1] - List[l-2])
  else:
    print(List[r-1] - List[l-1])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

cnt=[0 for i in range(N+1)]
s=0
f=False
for i in range(N):
    if f and S[i]=='C':
        s+=1
    if S[i]=='A':
        f=True
    else:
        f=False
    cnt[i]=s
for i in range(Q):
    l,r=map(int,input().split())
    print(cnt[r-1]-cnt[max(0,l-1)])

Submission status: Accepted

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

check = []
for i in range(len(s)-1):
    temp = s[i:i+2]
    if temp == "AC":
        check.append(i)

check_begin = [0 for i in range(len(s))]
check_num = 0
for i in range(len(s)):
    if check_num != len(check) and (check[check_num]+1) == i :
        check_num += 1
    check_begin[i] = check_num

#print(check_begin)

check_end = [len(check)-i for i in check_begin]

for quest in quests:
    begin = quest[0]-1
    end = quest[1]-1
    cnt = len(check) - check_begin[begin] - check_end[end]
    print(cnt)

Submission status: Accepted

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

# cum = [1 if (S[i] == "A" and S[i+1] == "C") else 0 for i in range(N-1)]
for i in range(Q):
    l, r = map(int, input().split())
    if l != 1:
        num = cum[r-2] - cum[l-2]
    else:
        num = cum[r-2]
    ans_lst.append(num)

for ans in ans_lst:
    print(ans)

Submission status: Accepted

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

loc = [0 for i in range(N+1)]
for i in range(N) :
    if S[i:i+2] == "AC" :
        loc[i+1] = loc[i]+1
    else :
        loc[i+1] = loc[i]
for l,r in L :
    l -= 1
    r -= 1
    ans = loc[r] - loc[l]
    print(ans)

Submission status: Accepted

Solution code:
n,q=map(int, input().split())
S=input()
lr=[list(map(int, input().split())) for _ in range(q)]
t=[0]*(n+1)
for i in range(n):
    #i桁目までに登場するACを計算する
    t[i+1]=t[i]+(1 if S[i:i+2] == "AC" else 0)
for i in range(q):
    l,r=lr[i][0]-1,lr[i][1]-1
    print(t[r]-t[l])

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
s = input()
ac = [0]
prev = ''
for c in s:
    if prev + c == 'AC':
        ac.append(ac[-1]+1)
    else:
        ac.append(ac[-1])
    prev = c

queries = [tuple(map(int, input().split())) for _ in range(q)]
for query in queries:
    print(ac[query[1]] - ac[query[0]])

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = input()
qs = [list(map(int, input().split())) for i in range(Q)]
t =[0] * N
for i in range(N-1):
    t[i+1] = t[i] + (1 if S[i:i+2] == 'AC' else 0)
def ans(l, r):
    return t[r-1] - t[l-1]
for l, r in qs:
    print(ans(l,r))

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right

N,Q = map(int,input().split())
S = input()
A = []
L = []

for i  in range(N-1):
    if S[i]=='A' and S[i+1]=='C':
        A.append(i)
        
for i in range(Q):
    L=list(map(int,input().split()))
    minA=bisect_left(A,L[0]-1)
    maxA=bisect_left(A,L[1]-1)
    print(maxA-minA)

Submission status: Accepted

Solution code:
import re
n = int(input().split()[1])
s = input()

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

s=[0]

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

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

Submission status: Accepted

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

Submission status: Accepted

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

count_list = [0]*(N+1)

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

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

Submission status: Accepted

Solution code:
N,Q = map(int,input().split())
S = str(input())
l,r = [0]*Q,[0]*Q
for i in range(Q):
    l[i],r[i] = map(int,input().split())
count_list = []
count = 0
count_list.append(0)
for i in range(1,N):
    if S[i-1] == "A" and S[i] == "C":
        count += 1
        count_list.append(count)
    else:
        count_list.append(count)   
for j in range(Q):
    print(count_list[r[j]-1]-count_list[l[j]-1])

Submission status: Accepted

Solution code:
N,Q = map(int,input().split())
S = str(input())
l,r = [0]*Q,[0]*Q
for i in range(Q):
    l[i],r[i] = map(int,input().split())
    
count_list = []
count = 0
count_list.append(0)
for i in range(1,N):
    if S[i-1] == "A" and S[i] == "C":
        count += 1
        count_list.append(count)
    else:
        count_list.append(count)
    
for j in range(Q):
    print(count_list[r[j]-1]-count_list[l[j]-1])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
s = ' ' + input()
heap = [0] * (n + 1)
cnt = 0
for i in range(2, n + 1):
    if s[i - 1] == 'A' and s[i] == 'C':
        cnt += 1;
    heap[i] = cnt
ans = []
for i in range(q):
    l, r = map(int, input().split())
    ans.append(heap[r] - heap[l])
for i in ans:
    print(i)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
s = str(input())
d = [list(map(int, input().split())) for i in range(q)]
a = [0,0]
cnt = 0
for i in range(1, n):
    if s[i-1]+s[i] == 'AC':
        cnt += 1
    a.append(cnt)

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
 
N, Q = map(int,input().split())
S = input()
nums = [0] * (N + 1)
for i in range(N):
  nums[i+1] = nums[i] + (1 if S[i:i+2]=='AC' else 0)
    
for j in range(Q):
  l, r = map(int,input().split())
  print(nums[r-1] - nums[l-1])

Submission status: Accepted

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

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


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

#0 1 2 3 4 5 6
# A C A C A C
# 1 2 3 4 5 6

for i in range(q):
    ans = sum[r[i]]-sum[l[i]]
    print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from itertools import accumulate
a,b = map(int, input().split())
c = str(input())
d = [list(map(int, input().split())) for i in range(0,b)]

flg = []
for i in range(a-1):
    moji = c[i:i+2]
    if moji == "AC":
        flg.append(1)
    else:
        flg.append(0)

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

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