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: Time Limit Exceeded

Solution code:
N, Q = [int(i) for i in input().split()]
S = input()
ind_ls = list()
for i in range(len(S) - 1):
    if S[i:i+2] == "AC":
       ind_ls.append(i)
for i in range(Q):
    l, r = [int(i) for i in input().split()]
    l -= 1
    r -= 1
    print(len([i for i in ind_ls if l <= i < r]))

Submission status: Time Limit Exceeded

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

for i in range(Q):
	count = 0
	j = l[i][0] - 1
	while j < l[i][1]-1:
		if S[j] == "A":
			if S[j+1] == "C":
				count += 1
				j += 2
			else:
				j += 2
		else:
			j += 1
	print(count)

Submission status: Time Limit Exceeded

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

li = []

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

for x in e:
    print(s[x[0]:x[1]+1].count("AC"))

Submission status: Time Limit Exceeded

Solution code:
n,q =map(int,input().split())
S = input()
LR = [list(map(int,input().split())) for _ in range(q)]
flag = True
Ans = [0]*q
count = -1

for l,r in LR:
    count += 1
    temp = ""
    for s in S[l-1:r]:
        if temp =="A" and s =="C":
            Ans[count] += 1
        temp = s
print(*Ans,sep = "\n")

Submission status: Time Limit Exceeded

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

for i, j in Prob:
    print(S[i-1:j].count("AC"))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def check(s):
    a_bit=0
    count=0
    for i in s:
        if i=="A":
            a_bit=1
        elif i=="C" and a_bit==1:
            a_bit=0
            count+=1
        else:
            a_bit=0
    print(count)



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

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
s = input()
for _ in range(m):
    l, r = map(int, input().split())
    tmps = s[l - 1:r]
    print(tmps.count("AC"))

Submission status: Time Limit Exceeded

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

for test in range(q):
	l, r = map(int, input().split())
	sub = s[l-1: r]

	print(sub.count("AC"))

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin
read_int = lambda : list(map(int,stdin.readline().split()))
read_str = lambda : stdin.readline().rstrip()

n,q = read_int()
S = read_str()
lr = [read_int() for _ in range(q)]


def solve():
    for i in range(q):
        l,r = lr[i]
        res = 0
        for j in range(l,r):
            # print(S[j-1:j +1])
            if S[j - 1: j + 1] == 'AC':
                res += 1
        print(res)


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
S = input()
l_list, r_list = [], []
for _ in range(Q):
    l, r = map(int, input().split())
    l_list.append(l)
    r_list.append(r)
    
    
for l, r in zip(l_list, r_list):
    target = S[l-1:r]
    ans = 0
    A_flag = False
    for char in target:
        if char == "A":
            A_flag = True
        elif char == "C" and A_flag:
            ans += 1
        else:
            A_flag = False
    print(ans)

Submission status: Time Limit Exceeded

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

for i in range(q):
  ans = 0
  l, r = map(int, input().split())
  c = s[l-1: r]
  for j in range(r-l):
    if c[j] == "A" and c[j+1] == "C":
      ans +=1
  print(ans)

Submission status: Time Limit Exceeded

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

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

for _ in range(Q):
  l, r = [int(x) for x in input().split()]
  print(len([x for x in ac_list if l<=x<r]))

Submission status: Time Limit Exceeded

Solution code:
def count_AC(s):
  ans=0
  for i in range(len(s)):
    if s[i:i+2]=="AC":ans+=1
  return ans
n,q=map(int,input().split())
s=input()
for i in range(q):
  a,b=map(int,input().split())
  print(count_AC(s[a-1:b]))

Submission status: Time Limit Exceeded

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

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

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
N, Q = (int(x) for x in input().split())
S = input()
l = []
r = []
for i in range(Q):
    a, b = (int(x) for x in input().split())
    l.append(a)
    r.append(b)
    
for i in range(Q):
    this_s = S[l[i]-1:r[i]]
    #print(this_s)
    print(this_s.count("AC"))

Submission status: Time Limit Exceeded

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

N, Q = LI()
S = input()
LR = []
for i in range(Q):
    LR.append(LI())
#  N, Q = 10**5, 10**5
#  S = 'ACTCTTCGTG'*10**4
#  LR = []
#  for i in range(Q):
#      LR.append([3,9000])

for l, r in LR:
    tmp = S[l-1:r]
    print(tmp.count('AC'))

Submission status: Time Limit Exceeded

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

result = []
for l, r in qlist:
    target = S[l-1:r]
    cache = 0
    for i,j in zip(range(r-l+1), range(1,r-l+1)):
        if target[i] == 'A' and target[j] == 'C':
            cache +=1
    result.append(cache)

for c in result:
    print(c)

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
s=input()
for _ in range(q):
    l,r=map(int,input().split())
    x=s[l-1:r]
    v=len(x)
    y=x.replace("AC","")
    w=len(y)
    print((v-w)//2)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

s = input()

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

Submission status: Time Limit Exceeded

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

LR = [list(map(int, input().split())) for _ in range(Q)]

for lr in LR:
    l, s = lr[0], lr[1]
    string = S[l - 1:s]
    print(string.count('ac'))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())
S=input()
for _ in range(Q):
    l,r=map(int,input().split())
    L=S[l-1:r]
    ans=0
    f=False
    for s in L:
        if f:
            if s=='C':
                ans+=1
                f=False
                continue
        if s=='A':
            f=True
            continue
        f=False
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
listS = list(input())
index=0
listA=[]
while index < q:
    l, r = map(int, input().split())
    listQ = listS[l-1: r]
    index2=0
    count=0
    while index2 < len(listQ)-1:
        if listQ[index2]=="A" and listQ[index2+1]=="C":
            count+=1
        index2+=1
    listA.append(count)
    index+=1
for ans in listA:
    print(ans)

Submission status: Time Limit Exceeded

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

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

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

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

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

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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

for _ in range(Q):
    l,r=[int(x) for x in input().strip().split()]
    print(S[l-1:r].count('AC'))

Submission status: Time Limit Exceeded

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

import bisect

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

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

Submission status: Time Limit Exceeded

Solution code:
""" AtCoder """

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

for i in range(Q):
    print(S[lr[i][0] -1:lr[i][1]].count("AC"))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
_ = input()
S = input().strip()
for line in sys.stdin:
  l,r = line.strip().split(' ')
  l,r = int(l), int(r)
  print(S[l-1:r].count('AC'))

Submission status: Time Limit Exceeded

Solution code:
hajime = input().split(" ")
num = int(hajime[1])
word = input()

for i in range(num):
  wakeru = input().split(" ")
  count = 0
  a = int(wakeru[0])
  b = int(wakeru[1])
  tmp = word[a-1:b]
  for j in range(len(tmp)-1):
    if tmp[j]=="A":
      if tmp[j+1]=="C":
        count+=1
  print(count)

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
S = input()
for _ in range(Q):
    l, r = map(int, input().split())
    print(S[l-1:r].count('AC'))

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())
S=input()
ans=[]
for _ in range(Q):
    l,r=map(int,input().split())
    ans.append(S[l-1:r].count('AC'))
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

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

for _ in range(Q):
    l, r = map(int, input().split())
    QS.append((l, r))

ans = []
for l, r in QS:
    s = S[l - 1: r]
    print(s.count("AC"))

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,input().split())
S = input()
count = []
for i in range(Q):
    l,r = map(int,input().split())
    count.append(S[l-1:r].count('AC'))

for i in count:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
p=input().split()
l,n=int(p[0]),int(p[1])
s=input()
for i in range(n):
    p=input().split()
    a,b=int(p[0]),int(p[1])
    k=s[a-1:b]
    c=0
    for j in range(len(k)-1):
        if k[j]=="A" and k[j+1]=="C":
            c+=1
    print(c)

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
S = list(input())
qs = [list(map(int, input().split())) for _ in range(Q)]
for q in qs:
    count = 0
    string = S[q[0]-1:q[1]]
    for i in range(q[1]-q[0]):
        if string[i] == 'A' and string[i+1] == 'C':
            count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,q = na()
s = ns()

for i in range(q):
  l,r = na()
  a = s[l-1:r].count('AC')
  print(a)

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
s = input()
for _ in range(Q):
  l, r = map(int, input().split())
  print(s[l-1:r].count('AC'))

Submission status: Time Limit Exceeded

Solution code:
import re
n, q = [int(i) for i in input().split()]
S = input()
for _ in range(q):
    l, r = [int(i) for i in input().split()]
    s = S[l-1:r]
    ans = sum(True for _ in re.findall('AC', s))
    print(ans)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

for i in range(Q):
    l,r = P[i]
    s = S[l-1:r]
    print(s.count('AC'))

Submission status: Time Limit Exceeded

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

ans = []
for _ in range(Q):
    a,b = [int(i) for i in input().split()]
    ans.append(S[a-1:b].count('AC'))

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
a, b = map(int, input().split())

A = list(input())

for i in range(b):
    x, y = map(int, input().split())
    B = A[x-1:y]
    ans = 0
    for j in range(len(B)-1):
        if(B[j] == 'A' and B[j+1] == 'C'):
            ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
a,b=map(int,input().split())
s=input()
for i in range(b):
    c,d=map(int,input().split())
    print(s[c-1:d].count("AC"))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
moji = str(input())
ans = [0]
for i in range(N-1):
    if moji[i] == "A" and moji[i+1] == "C":
        ans.append(ans[i]+1)
    else:
        ans.append(ans[i])

        
for i in range(K):
    st,sp = map(int,input().split())
    print(ans[sp-1]-ans[st-1])

Submission status: Accepted

Solution code:
#n = int(input())
n, q = map(int, input().split())
#bl = list(map(int, input().split()))
#al=[list(input()) for i in range(n)]
s = input()
acnum = [0]*(n+1)
for i in range(2, n+1):
    if s[i-2:i] == 'AC':
        acnum[i] += acnum[i-1]+1
    else:
        acnum[i] += acnum[i-1]

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect
n,q = map(int, input().split(" "))
s = input()
lr = [list(map(int, input().split(" "))) for i in range(q)]
a = []
for i in range(n-1):
  if s[i] +s[i+1]== 'AC':
    a.append(i+1)
for l, r in lr:
  print(bisect.bisect(a, r-1) - bisect.bisect(a, l-0.1))

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
s = input()
ls = [list(map(int, input().split())) for i in range(q)]
d = [0]
pre = 0
c = 0

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



for start, end in ls:
    print(d[end-1]-d[start-1])

Submission status: Accepted

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

result=[0]
cnt=0
for i in range(1,len(s)):
	if s[i-1]+s[i]=="AC":
		cnt+=1
		result.append(cnt)
	elif s[i-1]+s[i]!="AC":
		result.append(cnt)
        

for a,b in arr:
	print(result[b-1]-result[a-1])

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

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

S = input()
S = S.replace('\n','')
s_list = list(S)

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

ac_sum_list = [0 for i in range(len(s_list))]
tmp = ""
ac_sum = 0
for i,s in enumerate(s_list):
    if tmp + s == "AC":
        ac_sum += 1
    ac_sum_list[i] = ac_sum
    tmp = s


for i in range(q):
    l_index = l[i]
    r_index = r[i]
    l_ac = ac_sum_list[l_index-1]
    r_ac = ac_sum_list[r_index-1]
    print(r_ac - l_ac)

Submission status: Accepted

Solution code:
##初期値設定##
N, Q = map(int, input().split())
S = input()
dl=[]
dr=[]
for i in range(Q):
    line = list(map(int, input().split()))
    dl.append(line[0])
    dr.append(line[1])

##ACの個数配列計算##
a=[]
for i in range(N-1):
    tmp_S = S[i:i+2]
    if tmp_S == "AC":
        a.append(1)
    else:
        a.append(0)

##累積和計算##
s = [0]
for i in range(len(a)):
    s.append(s[i]+a[i])

##解答算出##
ans=[]
for l, r in zip(dl, dr):
    ans.append(s[r-1]-s[l-1])

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

Submission status: Accepted

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

class bit:
  def __init__(self, N):
    self.__N = N
    self.__a = [0] * N
  def add_(self, x, v):
    x += 1
    while x < self.__N:
      self.__a[x] += v
      x += x & -x
  def show_(self):
    print(self.__a[1:])
    
  def sum_(self, x):
    ans = 0
    while x > 0:
      ans += self.__a[x]
      x -= x & -x
    return ans
  def sub_sum_(self, x, y):
    return self.sum_(y) - self.sum_(x)
prev = "0"
BIT = bit(N)
for i, val in enumerate(S):
  if prev == "A" and val == "C":
    BIT.add_(i-1, 1)
  prev = val
for i in range(Q):
  x, y = map(int, input().split())
  x -= 1
  y -= 1
  print(BIT.sub_sum_(x,y))

Submission status: Accepted

Solution code:
def main():
    # n = int(input())
    n, q = map(int, input().split())
    # a = list(map(int, input().split()))
    s = input()
    # h = [int(input()) for _ in rane(n)]
    lr = []
    for i in range(q):
        l, r = list(map(int, input().split()))
        lr.append([l-1, r-1])

    count = [0] * (10**6)
    for i in range(1, n):
        if s[i-1] == "A" and s[i] == "C":
            count[i] = count[i-1] + 1
        else:
            count[i] = count[i-1]

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# C - GeT AC
N,Q = map(int,input().split())
S = input()
L = []
R = []
for _ in range(Q):
    l,r = map(int,input().split())
    l -= 1;r -= 1
    L.append(l)
    R.append(r)

# 右隣に 'C' が存在する 'A' の個数をカウント
cnt = [0]*N
for i in range(N-1):
    if S[i] == 'A' and S[i+1] == 'C':
        cnt[i] = 1

# s[i]: i 番目までに出てくる右隣に 'C' が存在する 'A' の個数
s = [0]*(N+1)
for i in range(N):
    s[i+1] = s[i] + cnt[i]

for l,r in zip(L,R):
    ans = s[r] - s[l]
    print(ans)

Submission status: Accepted

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

s=[0]*(N+1)
for i in range(N):
  if i+1<N and S[i]=="A" and S[i+1]=="C":
    s[i+1]=s[i]+1
  else:
    s[i+1]=s[i]

for q 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()
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+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()

cs = [0] * N
cnt = 0
for i in range(1, N):
    if S[i-1:i+1] == "AC":
        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 = [int(i) for i in input().split()]
S = input()

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

for l, r in ([int(i) for i in input().split()] for _ in range(Q)):
  print(cs[r - 1] - cs[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)]

csum = [0]
for i in range(1, N):
    if S[i-1:i+1] == 'AC':
        csum.append(csum[-1]+1)
    else:
        csum.append(csum[-1])
for l, r in lr:
    print(csum[r-1]-csum[l-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from sys import stdin
def input():
    return stdin.readline().strip()

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

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

    ans = [0] * q
    for lap in range(q):
        l, r = map(int, input().split())
        ans[lap] = cs[r-1] - cs[l-1]

    for i in ans:
        print(i)

main()

Submission status: Accepted

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

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

for x in a:
  print(c[x[1]-1]-c[x[0]-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]
    if s[i-1:i+1] == "AC":
        cnt[i]+=1
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()
cnt=[0,0]
for i in range(1,N):
    cnt.append(cnt[-1]+S[i-1:i+1].count("AC"))
for _ in range(Q):
    l,r=map(int,input().split())
    print(cnt[r]-cnt[l])

Submission status: Accepted

Solution code:
from itertools import accumulate

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

ac_list = [0]*n

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

ac_sum = list(accumulate(ac_list))

for l, r in lr:
    l -= 1
    r -= 1
    if l == 0:
        print(ac_sum[r-1])
        continue
    print(ac_sum[r-1] - ac_sum[l-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon Sep 14 00:57:13 2020

@author: liang
"""

N, Q = map(int, input().split())
S = input()
S += "a"
d = [0]*(N+1)
count = 0
for i in range(len(S)-1):
    if S[i:i+2] == "AC":
        count += 1
    #print(i)
    d[i+1] = count
#print(lis)
#print(d)
for i in range(Q):
    l, r = map(int, input().split())
    ans = d[r-1] - d[l-1]
    print(ans)

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
S = input()
t = [0 for _ in range(len(S)+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:
import sys
input = sys.stdin.readline

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# author:  Taichicchi
# created: 12.09.2020 19:26:19

import sys

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

S = input()

cum_ls = [0]

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

# print(cum_ls)

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

Submission status: Accepted

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

count = [0] * N

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

accum = count.copy()
for i in range(1, N):
	accum[i] += accum[i-1]

for i in range(Q):
	l, r = map(int, input().split())
	l -= 1; r -= 1;
	if l == 0:
		res = accum[r]
	else:
		res = accum[r] - accum[l-1]
	if count[r] == 1:
		res -= 1
	print(res)

Submission status: Accepted

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

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

for i in range(q):
    st,fn = map(int,input().split())
    print(lr[fn-1] - lr[st-1])

Submission status: Accepted

Solution code:
class SegmentTree:
    def __init__(self, data, default=0, func=max):
        """initialize the segment tree with data"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()

        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __delitem__(self, idx):
        self[idx] = self._default

    def __getitem__(self, idx):
        return self.data[idx + self._size]

    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1

    def __len__(self):
        return self._len

    def query(self, start, stop):
        """func of data[start, stop)"""
        start += self._size
        stop += self._size

        res_left = res_right = self._default
        while start < stop:
            if start & 1:
                res_left = self._func(res_left, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res_right = self._func(self.data[stop], res_right)
            start >>= 1
            stop >>= 1

        return self._func(res_left, res_right)

    def __repr__(self):
        return "SegmentTree({0})".format(self.data)


def f(tup1,tup2):
    tot=tup1[1]+tup2[1]
    if tup1[2]==1 and tup2[0]==1:
        tot+=1
    a=tup1[0]
    b=tup2[2]
    return (a,tot,b)



n,q=map(int,input().strip().split(" "))
s=input()
ar=[]
for i in s:
    if i=="A":
        ar.append((0,0,1))
    elif i=="C":
        ar.append((1, 0, 0))
    else:
        ar.append((0,0,0))
defa=(0,0,0)
seg=SegmentTree(ar,defa,f)
for _ in range(q):
    a,b=map(int,input().strip().split(" "))
    k=seg.query(a-1,b)
    print(k[1])