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:
# -*- coding: utf-8 -*-
"""
Created on Sat Jun 20 10:02:53 2020

@author: NEC-PCuser
"""

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

Submission status: Accepted

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

array = [0]*len(s)

for i in range(1,len(s)):
  if( s[i-1:i+1] == "AC" ):
    array[i] = array[i-1] + 1
  else:
    array[i] = array[i-1]
      

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

Submission status: Accepted

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

for i 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()
cnt = [0]*(N+1)
for i in range(N):
    cnt[i+1] = cnt[i] + (1 if S[i:i+2] == '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()+"d"
#'AC'が見つかったらCのほうに+1
count = [0]*(N+1)
for i in range(N):
    if S[i] == "A":
        if S[i+1] == "C":
            count[i+1] += count[i] + 1
        else:
            count[i+1] = count[i]
    else:
        count[i+1] = count[i]
    
#print(count)

for _ 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,raw_input().split(' '))
s = raw_input()
dp = [0] * len(s)
cumul = 0
for j in range(len(s)):
	if s[j - 1:j + 1] == 'AC': cumul +=1
	dp[j] = cumul 
"""
ac ac
 ^
    ^    
"""
for _ in range(q):
	u,v = map(int, raw_input().split(' '))
	u -=1
	v -=1
	print dp[v] - dp[u]

Submission status: Accepted

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

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()
ac = [0] * (n+1)
num = 0

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

Submission status: Accepted

Solution code:
from itertools import permutations

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def main():
    N, Q = mi()
    S = input()
    lr = [map(int, input().split()) for _ in range(Q)]
    l, r = [list(i) for i in zip(*lr)]

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
s = list(input())
LR = [0]*q
for i in range(q):
    LR[i] = list(map(int,input().split()))
d = [0]*(n+1)
for i in range(n-1):
    if s[i] == "A" and s[i+1] == "C":
        d[i+1] += d[i] + 1
    else:
        d[i+1] = d[i]
for L,R in LR:
    print(d[R-1]-d[L-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n,q=mp()
s=input()
ans=[0]*(n+1)
c=0
for i in range(1,n):
    if s[i-1]=="A" and s[i]=="C":
        c+=1
    ans[i+1]=c
for i in range(q):
    r,l=mp()
    print(ans[l]-ans[r])

Submission status: Accepted

Solution code:
import sys, os, math, bisect, itertools, collections, heapq, queue
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict

# import fractions

sys.setrecursionlimit(10000000)

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

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

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

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


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

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, Q = mapint()
S = list(str(input()))
from itertools import accumulate
lis = [0]*N
for i in range(1, N):
    if S[i-1]=='A' and S[i]=='C':
        lis[i] += 1
cum = list(accumulate(lis))

for _ in range(Q):
    l, r = mapint()
    print(cum[r-1]-cum[l-1])

Submission status: Accepted

Solution code:
from sys import stdin
import numpy as np
N, Q=map(int,input().split())
S=input()
L =[list(map(int, stdin.readline().split())) for _ in range(Q)]
c = [0]*(N)  
s = [0]*(N)  
for i in range(N-1):
  if S[i] == "A" and S[i+1] == "C":
    c[i+1] = 1
s = np.cumsum(c)
for i in range(Q):
  print(s[L[i][1]-1]-s[L[i][0]-1])

Submission status: Accepted

Solution code:
N ,Q = map(int,input().split())
S = input()
lst = []
for i in range(Q):
    s,e = map(int,input().split())
    lst.append([s-1,e-1])
#print(lst)

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

for v in lst:
    print(cum[v[1]] - cum[v[0]])

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
n,q = map(int, input().split())
s = input()
lr = [list(map(int, input().split())) for _ in range(q)]

numbers = []
for i in range(n-1):
    if s[i]+s[i+1] == "AC":
        numbers.append(i+1)
for l,r in lr:
    x,y = bisect_left(numbers, l), bisect_right(numbers, r)
    if x==y: print(0)
    elif numbers[y-1]+1 <= r:print(y-x)
    else: print(y-x-1)

Submission status: Accepted

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

Submission status: Accepted

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

N,Q = map(int,readline().split())
S = readline().rstrip()

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

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
s=input()
a=[0]
current=0
for i in range(n-1):
  if s[i]=='A' and s[i+1]=='C':
    current+=1
  a.append(current)
for i in range(q):
  x,y=map(int,input().split())
  if y==1:
    print(0)
    continue
  print(a[y-1]-a[x-1])

Submission status: Accepted

Solution code:
def Csum(a):
    b,c=[0],0
    for i in range(len(a)-1):
        c+=(a[i]=='A' and a[i+1]=='C')
        b.append(c)
    return b
n,q=map(int,input().split())
s=Csum(input())
for i in range(q):
    a,b=map(int,input().split())
    print(s[b-1]-s[a-1])

Submission status: Accepted

Solution code:
n,q = map(int, input().split())  
a = input() 
l = [0]*n; 

for i in range(2,n+1):
    x = a[(i-2):i]
    l[i-1] = l[i-2]
    if x=='AC':
        l[i-1] += 1

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

Submission status: Accepted

Solution code:
from sys import stdin
import numpy as np
N, Q=map(int,input().split())
S=input()
L =[list(map(int, stdin.readline().split())) for _ in range(Q)]
c = [0]*(N)  #ACのチェック
s = [0]*(N)  #ACの累積和
ans = [0]*Q 

for i in range(N-1):
  if S[i] == "A" and S[i+1] == "C":
    c[i+1] = 1
s = np.cumsum(c)
for i in range(Q):
  ans[i] = s[L[i][1]-1]-s[L[i][0]-1]

for i in ans:
  print(i)

Submission status: Accepted

Solution code:
import numpy as np
N, Q=map(int,input().split())
S=input()
L =[list(map(int,input().split()))for i in range(Q)]
c = [0]*(N)  #ACのチェック
s = [0]*(N)  #ACの累積和
ans = [0]*Q 

for i in range(N-1):
  if S[i] == "A" and S[i+1] == "C":
    c[i+1] = 1
s = np.cumsum(c)
for i in range(Q):
  ans[i] = s[L[i][1]-1]-s[L[i][0]-1]

for i in ans:
  print(i)

Submission status: Accepted

Solution code:
def main():
    n, q = map(int, input().split())
    ss = list(input())
    lrs = [list(map(int, input().split())) for _ in range(q)]
    cum_sum = [0] * n
    for i in range(1, n):
        if ss[i-1] == 'A' and ss[i] == 'C':
            cum_sum[i] += 1
        cum_sum[i] += cum_sum[i-1]
    for l, r in lrs:
        print(cum_sum[r-1]-cum_sum[l-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

N, Q = map(int, sys.stdin.readline().strip().split())
S = sys.stdin.readline().strip()
ls = len(S)

index = [0 for _ in range(len(S)+1)]
for i in range(len(S)):
    if S[i:i+2] == "AC":
        index[i+1] = 1
for i in range(ls):
    index[i+1] += index[i]

# print(index)

for _ in range(Q):
    l, r = map(int, sys.stdin.readline().strip().split())
    print(index[r-1] - index[l-1])

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

def main():
	N,Q=map(int,sys.stdin.readline().split())
	S=input()
	A=[0]*N
	# 累積和
	for i in range(1,N):
		A[i]=S[i-1:i+1]=="AC"
		A[i]=A[i]+A[i-1]
	# [l:r)区間の総和を求める
	for i in range(Q):
		l,r=map(int,sys.stdin.readline().split())
		print(A[r-1]-A[l-1])
if __name__=='__main__':
	main()

Submission status: Accepted

Solution code:
def main():
	N,Q=map(int,input().split())
	S=input()
	A=[0]*N
	# 累積和
	for i in range(1,N):
		A[i]=S[i-1:i+1]=="AC"
		A[i]=A[i]+A[i-1]
	# [l:r)区間の総和を求める
	for i in range(Q):
		l,r=map(int,input().split())
		print(A[r-1]-A[l-1])
if __name__=='__main__':
	main()

Submission status: Accepted

Solution code:
N,Q=map(int,input().split())
S=input()
A=[0]*N
# 累積和
for i in range(1,N):
	if S[i-1:i+1]=="AC":
		A[i]+=1
	A[i]=A[i]+A[i-1]
# [l:r)区間の総和を求める
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]*N
for i in range(1,N+1):
	if S[i-1:i+1]=="AC":
		A[i]+=1
for i in range(1,N):
	A[i]=A[i]+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:
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:
n,q=map(int,input().split())
s=str(input())
a=[0]
a*=n
for i in range(n-1):
    if s[i]=='A' and s[i+1]=='C':
        a[i+1]=a[i]+1
    else:
        a[i+1]=a[i]
#最初に余分な0が一つ入っているため番号はそのまま        
for i in range(q):
    li,ri=map(int,input().split())
    ans=a[ri-1]-a[li-1]
    print(ans)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

input_n = lambda: int(readline())
input_nn = lambda: map(int, readline().split())
input_s = lambda: readline().rstrip().decode('utf-8')
input_ss = lambda: readline().rstrip().decode('utf-8').split()


def main():
    N, Q = input_nn()
    S = list(input_s())

    ac_check = [0] * (N)
    tsum = [0] * (N + 1)

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

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

    ans = []
    for i in range(Q):
        l, r = input_nn()
        count = tsum[r] - tsum[l - 1]
        if ac_check[l - 1] == 2:
            count -= 1
        ans.append(count)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readline_s = sys.stdin.readline
readlines = sys.stdin.buffer.readlines


def main():
    N, Q = map(int, readline().split())
    S = list(readline().rstrip().decode())
    ac_check = [0] * (N)
    tsum = [0] * (N + 1)

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

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

    ans = []
    for i in range(Q):
        l, r = map(int, readline().split())
        count = tsum[r] - tsum[l - 1]
        if ac_check[l - 1] == 2:
            count -= 1
        ans.append(count)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def main():
    N, Q = map(int, readline().split())
    S = list(readline().rstrip().decode())
    ac_check = [0] * (N)
    tsum = [0] * (N + 1)

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

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

    ans = []
    for i in range(Q):
        l, r = map(int, readline().split())
        count = tsum[r] - tsum[l - 1]
        if ac_check[l - 1] == 2:
            count -= 1
        ans.append(count)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys


def main():
    N, Q = map(int, input().split())
    S = list(input())
    ac_check = [0] * (N)
    tsum = [0] * (N + 1)

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

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

    ans = []
    for i in range(Q):
        l, r = map(int, input().split())
        count = tsum[r] - tsum[l - 1]
        if ac_check[l - 1] == 2:
            count -= 1
        ans.append(count)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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


z=[0]*n
count=0
for i in range(n):
    z[i]=count
    if s[i]=="A" and i<=n-2:
        if s[i+1]=="C":
            count+=1
            z[i]+=1

for i in range(q):
    l, r =map(int,input().split())
    #r文字目までのACの数-(l-1)文字目まで
    if l==1:
        ans=z[r-2]
    elif r-l==1:
        if s[l-1]=="A" and s[l]=="C":
            ans=1
        else:
            ans=0
    else:
        ans=z[r-2]-z[l-2]
    print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	C
# CreatedDate:  2020-06-14 14:59:04 +0900
# LastModified: 2020-06-14 15:07:55 +0900
#


import os
import sys
#import numpy as np
#import pandas as pd
from itertools import accumulate as ac

def main():
    n,q = map(int,input().split())
    s = input()
    poly = [0]*len(s)
    for i in range(0,len(s)-1):
        if s[i]=='A' and s[i+1]=='C':
            poly[i]=1
    ans = list(ac(poly))
    ans.insert(0,0)
    for _ in range(q):
        l,r = map(int,input().split())
        print(ans[r-1]-ans[l-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

        s.append(s[i-1]+1)

    else:
        s.append(s[i-1])

for i in range(Q):

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

Submission status: Accepted

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

s=[]
s.append(0)

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

        s.append(s[i-1]+1)

    else:
        s.append(s[i-1])

for i in range(Q):

    l,r=map(int,input().split())

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

Submission status: Accepted

Solution code:
'''
Accepted    　:No
difficult   　: 
ペナルティ　  　:5分
実際の回答時間  :分
WAの回数　     :回
合計時間　　  　:分
'''

def myAnswer(N:int,Q:int,S:str,L:list,R:list) -> None:
   pre = S[0]
   accum = [0]
   for s in S[1:]:
      if(pre == "A" and s =="C"):
         accum.append(accum[-1] + 1)
      else:
         accum.append(accum[-1])
      pre = s
   for l,r in zip(L,R):
      print(accum[r-1] - accum[l-1])


def modelAnswer():
   return
def main():
   N,Q = map(int,input().split())
   S =input()
   L = []
   R = []
   for _ in range(Q):
      l,r = map(int,input().split())
      L.append(l)
      R.append(r)
   myAnswer(N,Q,S,L,R)


if __name__ == '__main__':
   main()

Submission status: Accepted

Solution code:
N, Q, S, *_LR = open(0).read().split()
N = int(N)
Q = int(Q)
LR = list(zip(*[map(int, iter(_LR))]*2))

AC = [0]*(N)

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

    if i == 1:
        AC[i] = is_AC
    else:
        AC[i] = AC[i-1] + is_AC
        
for L,R in LR:
    print(AC[R-1] - AC[L-1])

Submission status: Accepted

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

s = input()

count = [0] * n

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

from itertools import accumulate

accum = list(accumulate(count))

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

Submission status: Accepted

Solution code:
# 累積和の考え方
#   listに積み重ねた数値を出しておくことで特定範囲の数値を求める時間を短縮する
#   例：ABBBBAABBBBAB があるときに(l,r)にAがいくつ含まれるかを求める場合は以下のように(1長い)listを作る
#      BBABBBAABBBBAA
#      000111123333345
#   このリストの文字列のr-lで出せる(3,7)ならstr[7]-str[3]を出すと3-1で2となる

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

# 累積和のリストを作成
cumsum = [0]*(n+1)
for i in range(1, n):
    if s[i-1] == 'A' and s[i] == 'C':
        cumsum[i+1]+=cumsum[i]+1
    else:
        cumsum[i+1]=cumsum[i]

# 012345   index
# 123456   input
# ACACAC   s
# 0011223  cumsum
for left, right in lr:
    print(cumsum[right]-cumsum[left])

Submission status: Accepted

Solution code:
from collections import Counter 
from collections import defaultdict
from collections import deque
from functools import reduce
import math
import itertools
import heapq
import numpy as np
import bisect
import sys
#import sympy
sys.setrecursionlimit(10**6)


def bfs(s,n,node):
    #頂点が探索済みかどうかのチェック配列
    check=[False for _ in range(n)]
    check[s]=True
    #次見る頂点を格納するキュー
    queue=deque([s])
    visited_num=1

    #問題固有の配列
    #color_check=[[True for _ in range(l)] for _ in range(n)]
    color=[-1 for _ in range(n)]
    color[s]=0
    
    while visited_num<n:
        #グラフが全連結ではない場合
        if len(queue)==0:
            #空配列を返す
            #現状までの計算済み配列を返してもいいと思う
            return color

        now_vertex=queue.popleft()
        #インデックスがない場合は
        for next_vertex in node[now_vertex]:


            if check[next_vertex]==True:
                continue

            queue.append(next_vertex)
            check[next_vertex]=True

            #問題固有の計算
            color[next_vertex]=color[now_vertex]+1
            visited_num+=1

    return color

#n=int(input())z
#n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))
ceil=lambda x,y: (x+y-1)//y
input_list = lambda : list(map(int,input().split()))

n,q=input_list()
s=input()
l=len(s)
left=[0 for _ in range(l)]
for i in range(1,l):
    left[i]=left[i-1]
    if s[i-1]+s[i]=="AC":
        left[i]+=1

for _ in range(q):
    l,r=input_list()
    print(left[r-1]-left[l-1])

Submission status: Accepted

Solution code:
from collections import Counter 
from collections import defaultdict
from collections import deque
from functools import reduce
import math
import itertools
import heapq
import numpy as np
import bisect
import sys
#import sympy
sys.setrecursionlimit(10**6)


def bfs(s,n,node):
    #頂点が探索済みかどうかのチェック配列
    check=[False for _ in range(n)]
    check[s]=True
    #次見る頂点を格納するキュー
    queue=deque([s])
    visited_num=1

    #問題固有の配列
    #color_check=[[True for _ in range(l)] for _ in range(n)]
    color=[-1 for _ in range(n)]
    color[s]=0
    
    while visited_num<n:
        #グラフが全連結ではない場合
        if len(queue)==0:
            #空配列を返す
            #現状までの計算済み配列を返してもいいと思う
            return color

        now_vertex=queue.popleft()
        #インデックスがない場合は
        for next_vertex in node[now_vertex]:


            if check[next_vertex]==True:
                continue

            queue.append(next_vertex)
            check[next_vertex]=True

            #問題固有の計算
            color[next_vertex]=color[now_vertex]+1
            visited_num+=1

    return color

#n=int(input())z
#n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))
ceil=lambda x,y: (x+y-1)//y
input_list = lambda : list(map(int,input().split()))

n,q=input_list()
s=input()
l=len(s)
left=[0 for _ in range(l)]
for i in range(1,l):
    left[i]=left[i-1]
    if s[i-1]+s[i]=="AC":
        left[i]+=1
total=left[-1]
right=[0 for _ in range(l)]
for i in range(1,l):
    ii=l-i-1
    right[ii]=right[ii+1]
    if s[ii]+s[ii+1]=="AC":
        right[ii]+=1

for _ in range(q):
    l,r=input_list()
    ri=right[r-1]
    le=left[l-1]
    print(total-le-ri)

Submission status: Accepted

Solution code:
#C
n,q = map(int,input().split())
s = input()
#累積和で考える
cnt = 0
cumsum = []
prev = s[0]
for i in range(n):
    now = s[i]
    if now == "C" and prev == "A":
        cnt += 1
    cumsum.append(cnt)
    prev = now
    
#print(cumsum)
for i in range(q):
    l,r = map(int,input().split())
    print(cumsum[r-1] - cumsum[l-1])

Submission status: Accepted

Solution code:
# 下記ページを参考に実装してる
# https://qiita.com/drken/items/56a6b68edef8fc605821#%E5%95%8F%E9%A1%8C-3-atcoder-abc-122-c---get-ac

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

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

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

Submission status: Accepted

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

C = [0 for _ in range(N)]
count = 0
prev = S[0]
for i, s in enumerate(S[1:]):
    now = s
    if prev + now == 'AC':
        count += 1
    C[i+1] = count
    prev = now
C

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

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = str(input())
cnt = 0
L = []
L.append(0)

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

for x in range(Q):
    f, r = map(int, input().split())
    print(L[r-1] - L[f-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())
c = [0]*(len(s)+1)
for i in range(len(s)-1):
	if s[i] == 'A' and s[i+1] == 'C':
		c[i+1] += c[i] + 1
	else:
		c[i+1] = c[i]
for i in range(q):
	print(c[r[i]-1]-c[l[i]-1])

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import itertools
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n, q = map(int, readline().split())
s = readline().decode().rstrip()

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

a = list(itertools.accumulate(lis))

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

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

for i,j in u:
  print( c[j-1] - c[i-1] )

Submission status: Accepted

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


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

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

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = input()
A = [0] * (N + 1)
for i in range(1, N):
  if S[i - 1] == "A" and S[i] == "C":
    A[i + 1] = A[i] + 1
  else:
    A[i + 1] = A[i]
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()
ans,c=[0]*q,[0]*n
k=0
for i in range(1,n):
    if s[i-1]=="A" and s[i]=="C":
        k+=1
    c[i]=k

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

Submission status: Accepted

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

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


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

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

Submission status: Accepted

Solution code:
from itertools import accumulate


[N, Q], [S], *LR = [s.split() for s in open(0)]
N, Q = map(int, (N, Q))
acc = [0] + list(accumulate([S[i] + S[i + 1] == 'AC' for i in range(N - 1)]))
for l, r in LR:
    l, r = map(lambda x: int(x) - 1, (l, r))
    print(acc[r] - acc[l])

Submission status: Accepted

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

ans = 0
t = [0]
for i in range(1, n):
    if s[i - 1:i + 1] == "AC":
        t.append(t[i - 1] + 1)
    else:
        t.append(t[i - 1])
# print(t)
for l, r in q:
    print(t[r - 1] - t[l - 1])