Problem:
 Score : 600 points    Problem Statement  In Dwango Co., Ltd., there is a content distribution system named 'Dwango Media Cluster', and it is called 'DMC' for short. The name 'DMC' sounds cool for Niwango-kun, so he starts to define DMC-ness of a string.  Given a string S of length N and an integer k  (k \geq 3) ,
he defines the k -DMC number of S as the number of triples (a, b, c) of integers that satisfy the following conditions:   0 \leq a < b < c \leq N - 1  S[a] = D  S[b] = M  S[c] = C  c-a < k   Here S[a] is the a -th character of the string S . Indexing is zero-based, that is, 0 \leq a \leq N - 1 holds.  For a string S and Q integers k_0, k_1, ..., k_{Q-1} , calculate the k_i -DMC number of S for each i  (0 \leq i \leq Q-1) .      Constraints   3 \leq N \leq 10^6  S consists of uppercase English letters  1 \leq Q \leq 75  3 \leq k_i \leq N  All numbers given in input are integers         Input  Input is given from Standard Input in the following format:  N  S  Q  k_{0}  k_{1}  ...  k_{Q-1}       Output  Print Q lines.
The i -th line should contain the k_i -DMC number of the string S .        Sample Input 1  18
DWANGOMEDIACLUSTER
1
18      Sample Output 1  1  (a,b,c) = (0, 6, 11) satisfies the conditions. Strangely, Dwango Media Cluster does not have so much DMC-ness by his definition.       Sample Input 2  18
DDDDDDMMMMMCCCCCCC
1
18      Sample Output 2  210  The number of triples can be calculated as 6\times 5\times 7 .       Sample Input 3  54
DIALUPWIDEAREANETWORKGAMINGOPERATIONCORPORATIONLIMITED
3
20 30 40      Sample Output 3  0
1
2  (a, b, c) = (0, 23, 36), (8, 23, 36) satisfy the conditions except the last one, namely, c-a < k_i . By the way, DWANGO is an acronym for "Dial-up Wide Area Network Gaming Operation".       Sample Output 4  30
DMCDMCDMCDMCDMCDMCDMCDMCDMCDMC
4
5 10 15 20      Sample Output 4  10
52
110
140

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    s = input()
    q = I()
    K = LI()
    for k in K:
        d = 0
        m = 0
        dm = 0
        ans = 0
        for i in range(n):
            if i >= k:
                j = i-k
                if s[j] == "D":
                    d -= 1
                    dm -= m
                elif s[j] == "M":
                    m -= 1
            if s[i] == "D":
                d += 1
            elif s[i] == "M":
                m += 1
                dm += d
            elif s[i] == "C":
                ans += dm
        print(ans)
    return



if __name__ == "__main__":
    solve()

Solution (Python):
N = int(input())
S = input()
Q = int(input())
*K, = map(int,input().split())

nD = S.count("D")
nC = S.count("C")
if nD < nC:
    S = S[::-1].replace("D","c").replace("C","d").upper()

D = [0]*(N+1)
cntM = [0]*(N+1)
sumM = [0]*(N+1)
ans = [0]*Q
for i,s in enumerate(S):
    D[i+1] = D[i]
    cntM[i+1] = cntM[i]
    sumM[i+1] = sumM[i]
    if s=="D":
        D[i+1] += 1
    elif s=="M":
        cntM[i+1] += 1
        sumM[i+1] += D[i]
    elif s=="C":
        for j,k in enumerate(K):
            ik = max(0,i-k+1)
            d = D[ik]
            ans[j] += (sumM[i]-sumM[ik]) - d*(cntM[i]-cntM[ik])
for out in ans:
    print(out)

Solution (Python):
import sys
input = sys.stdin.readline

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

    for K in Ks:
        
        dp = [0]*4
        for i in range(N):
            if i-K >= 0:
                sk = S[i-K]
                if sk == 'D':
                    dp[0] -= 1
                    dp[2] -= dp[1]
                elif sk == "M":
                    dp[1] -= 1
            s = S[i]
            if s == "D":
                dp[0] += 1
            elif s == 'M':
                dp[1] += 1
                dp[2] += dp[0]
            elif s == 'C':
                dp[3] += dp[2]
        
        print(dp[3])
    

if __name__ == "__main__":
    main()

Solution (Python):
N=int(input())
D,M,C=map(ord,'DMC')
import numpy as np
S=np.array([ord(c) for c in input()])
input()
K=map(int,input().split())
iD=S==D
iM=S==M
iC=S==C
cD=np.cumsum(iD,dtype=np.int64)
cM=np.cumsum(iM,dtype=np.int64)
for k in K:
    cD2=cD-np.concatenate((np.zeros(k,dtype=np.int64),cD[:-k]))
    cM2=cM-np.concatenate((np.zeros(k,dtype=np.int64),cM[:-k]))
    DM=np.cumsum(cD2*iM-np.concatenate((np.zeros(k,dtype=np.int64),cM2[k-1:-1]*iD[:-k])))
    print(np.sum(iC*DM))

Solution (Python):
e=enumerate
n,s,q,*k=open(0).read().split()
n=int(n)
m,c,x=eval('[0]*-~n,'*3)
for i,t in e(s,1):
  m[i]=m[i-1]+('M'==t)
  f='C'==t
  c[i]=c[i-1]+f
  x[i]=x[i-1]+f*m[i]
for k in map(int,k):
  a=0
  for i,t in e(s):
    j=min(n,i+k)
    if'D'==t:a+=x[j]-x[i]-(c[j]-c[i])*m[i]
  print(a)

Solution (Python):
e=enumerate
n,s,q,*k=open(0).read().split()
n=int(n)
m,c,x=eval('[0]*-~n,'*3)
for i,t in e(s,1):
  m[i]=m[i-1]+(t=='M')
  f=t=='C'
  c[i]=c[i-1]+f
  x[i]=x[i-1]+f*m[i]
for k in map(int,k):
  a=0
  for i,t in e(s):
    j=min(n,i+k)
    if t=='D':
      a+=x[j]-x[i]-(c[j]-c[i])*m[i]
  print(a)

Solution (Python):
from numpy import*
_,s,_,k=open(0)
s=array(list('='+s[:-1]))
d,m,c=[s==t for t in'DMC']
x,y=map(cumsum,(d,m))
for k in int32(k.split()):
  t=copy(x)
  t[k:]-=x[:-k]
  t*=m
  t[k+1:]-=d[1:-k]*(y[k:-1]-y[:~k])
  print(sum(cumsum(t)*c))

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np
N = int(readline())
S = np.zeros(N+1,'U1')
S[1:] = list(readline().rstrip().decode('utf-8'))
Q = int(readline())
query = map(int,readline().split())

isD = S == 'D'
isM = S == 'M'
isC = S == 'C'

cumD = isD.cumsum(dtype=np.int64)
cumM = isM.cumsum(dtype=np.int64)

for K in query:
    x = cumD.copy(); x[K:] -= cumD[:-K]
    x *= isM
    x[K+1:] -= isD[1:-K] * (cumM[K:-1] - cumM[:-K-1])
    print((x.cumsum() * isC).sum())

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np
N = int(readline())
S = np.empty(N+1,'S1')
S[1:] = np.frombuffer(readline(),dtype='S1')[:N]
Q = int(readline())
query = map(int,readline().split())

isD = S == b'D'
isM = S == b'M'
isC = S == b'C'

cumD = isD.cumsum(dtype=np.int64)
cumM = isM.cumsum(dtype=np.int64)

for K in query:
    x = cumD.copy(); x[K:] -= cumD[:-K]
    x *= isM
    x[K+1:] -= isD[1:-K] * (cumM[K:-1] - cumM[:-K-1])
    print((x.cumsum() * isC).sum())

Solution (Python):
import sys
readline = sys.stdin.readline
import numpy as np
N = int(input())
S = np.array(list('-'+readline()),dtype='U1')
Q = int(input())
query = map(int,input().split())

isD = S == 'D'
isM = S == 'M'
isC = S == 'C'

cumD = isD.cumsum(dtype=np.int64)
cumM = isM.cumsum(dtype=np.int64)

for K in query:
    x = cumD.copy(); x[K:] -= cumD[:-K]
    x *= isM
    x[K+1:] -= isD[1:-K] * (cumM[K:-1] - cumM[:-K-1])
    print((x.cumsum() * isC).sum())

Solution (Python):
import numpy as np
N = int(input())
S = np.array(list('-'+input()),dtype='U1')
Q = int(input())
query = map(int,input().split())

isD = S == 'D'
isM = S == 'M'
isC = S == 'C'

cumD = isD.cumsum(dtype=np.int64)
cumM = isM.cumsum(dtype=np.int64)

for K in query:
    x = cumD.copy(); x[K:] -= cumD[:-K]
    x *= isM
    x[K+1:] -= isD[1:-K] * (cumM[K:-1] - cumM[:-K-1])
    print((x.cumsum() * isC).sum())

Solution (Python):
import numpy as np
I=input
N = int(I())
S = np.array(list('-'+I()),dtype='U1')
Q = int(I())
query = map(int,I().split())

isD = S == 'D'
isM = S == 'M'
isC = S == 'C'

cumD = isD.cumsum(dtype=np.int64)
cumM = isM.cumsum(dtype=np.int64)

for K in query:
    x = cumD.copy(); x[K:] -= cumD[:-K]
    x *= isM
    x[K+1:] -= isD[1:-K] * (cumM[K:-1] - cumM[:-K-1])
    print((x.cumsum() * isC).sum())

Solution (Python):
import numpy as np
I=input
N = int(I())
S = np.fromiter('-'+I(),dtype='U1')
Q = int(I())
query = map(int,I().split())

isD = S == 'D'
isM = S == 'M'
isC = S == 'C'

cumD = isD.cumsum(dtype=np.int64)
cumM = isM.cumsum(dtype=np.int64)

for K in query:
    x = cumD.copy(); x[K:] -= cumD[:-K]
    x *= isM
    x[K+1:] -= isD[1:-K] * (cumM[K:-1] - cumM[:-K-1])
    print((x.cumsum() * isC).sum())

Solution (Python):
import numpy as np

N = int(input())
S = np.fromiter('-'+input(),dtype='U1')
Q = int(input())
query = map(int,input().split())

isD = S == 'D'
isM = S == 'M'
isC = S == 'C'

cumD = isD.cumsum(dtype=np.int64)
cumM = isM.cumsum(dtype=np.int64)

for K in query:
    x = cumD.copy(); x[K:] -= cumD[:-K]
    x *= isM
    x[K+1:] -= isD[1:-K] * (cumM[K:-1] - cumM[:-K-1])
    print((x.cumsum() * isC).sum())

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from numpy import *

N = int(readline())
S = frombuffer(b'-'+readline().rstrip(),'S1')
Q = int(readline())
query = map(int,read().split())

isD = S == b'D'
isM = S == b'M'
isC = S == b'C'

cumD = isD.cumsum(dtype=int64)
cumM = isM.cumsum(dtype=int64)

for K in query:
    x = cumD.copy(); x[K:] -= cumD[:-K]
    x *= isM
    x[K+1:] -= isD[1:-K] * (cumM[K:-1] - cumM[:-K-1])
    print((x.cumsum() * isC).sum())

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N = int(readline())
S = np.frombuffer(b'-'+readline().rstrip(),'S1')
Q = int(readline())
query = map(int,read().split())

isD = S == b'D'
isM = S == b'M'
isC = S == b'C'

cumD = isD.cumsum(dtype=np.int64)
cumM = isM.cumsum(dtype=np.int64)

for K in query:
    x = cumD.copy(); x[K:] -= cumD[:-K]
    x *= isM
    x[K+1:] -= isD[1:-K] * (cumM[K:-1] - cumM[:-K-1])
    print((x.cumsum() * isC).sum())

Solution (Python):
from numpy import *
I=input
N=int(I())
S=array(list('-'+I()))
Q=int(I())
query = map(int,I().split())
D=S=='D';M=S=='M';C=S=='C'
d=D.cumsum(dtype=int64);m=M.cumsum(dtype=int64)
for K in query:
  x=d.copy();x[K:]-=d[:-K];x*=M
  x[K+1:]-=D[1:-K]*(m[K:-1]-m[:-K-1])
  print(sum(cumsum(x)*C))

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N = int(readline())
S = np.frombuffer(b'-'+readline().rstrip(),'S1')
Q = int(readline())
query = map(int,read().split())

isD = S == b'D'
isM = S == b'M'
isC = S == b'C'

cumD = isD.cumsum(dtype=np.int64)
cumM = isM.cumsum(dtype=np.int64)

def F(K):
    x = cumD.copy(); x[K:] -= cumD[:-K]
    x *= isM
    x[K+1:] -= isD[1:-K] * (cumM[K:-1] - cumM[:-K-1])
    return (x.cumsum() * isC).sum()

print('\n'.join(str(F(K)) for K in query))

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N = int(readline())
S = np.frombuffer(readline().rstrip(),'S1')
Q = int(readline())
query = map(int,read().split())

isD = S == b'D'
isM = S == b'M'
isC = S == b'C'

cumD = isD.cumsum(dtype=np.int64)
cumM = isM.cumsum(dtype=np.int64)

def F(K):
    """
    ・Cごとに数える。
    ・そのためには(i-K,i] 内のDMの個数を調べる（負インデックスには関係ない文字があると思っておく）
    ・区間内のDの個数、Mの個数が取得できれば、差分が取得できるので最後に累積和
    """
    
    D = cumD.copy(); D[K:] -= cumD[:-K]
    M = cumM.copy(); M[K:] -= cumM[:-K]
    
    DM = D; DM *= isM
    
    DM[K:] -= isD[:-K] * M[K-1:-1]
    np.cumsum(DM,out=DM)
    
    return (DM*isC).sum()

print('\n'.join(str(F(K)) for K in query))

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N = int(readline())
S = np.frombuffer(readline().rstrip(),'S1')
Q = int(readline())
query = map(int,read().split())

isD = S == b'D'
isM = S == b'M'
isC = S == b'C'

cumD = isD.cumsum(dtype=np.int64)
cumM = isM.cumsum(dtype=np.int64)

def F(K):
    """
    ・Cごとに数える。
    ・そのためには(i-K,i] 内のDMの個数を調べる（負インデックスには関係ない文字があると思っておく）
    ・区間内のDの個数、Mの個数が取得できれば、差分が取得できるので最後に累積和
    """
    
    D = cumD.copy(); D[K:] -= cumD[:-K]
    M = cumM.copy(); M[K:] -= cumM[:-K]
    
    DM = isM * D
    
    DM[K:] -= isD[:-K] * M[K-1:-1]
    np.cumsum(DM,out=DM)
    
    return (DM*isC).sum()

print('\n'.join(str(F(K)) for K in query))

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N = int(readline())
S = np.frombuffer(readline().rstrip(),'S1')
Q = int(readline())
query = map(int,read().split())

isD = S == b'D'
isM = S == b'M'
isC = S == b'C'

cumD = isD.cumsum(dtype=np.int64)
cumM = isM.cumsum(dtype=np.int64)

def F(K):
    """
    ・Cごとに数える。
    ・そのためには(i-K,i] 内のDMの個数を調べる（負インデックスには関係ない文字があると思っておく）
    ・区間内のDの個数、Mの個数が取得できれば、差分が取得できるので最後に累積和
    """
    
    D = cumD.copy(); D[K:] -= cumD[:-K]
    M = cumM.copy(); M[K:] -= cumM[:-K]
    
    DM = isM * D
    
    DM[K:] -= isD[:-K] * M[K-1:-1]
    np.cumsum(DM,out=DM)
    
    return DM[isC].sum()

print('\n'.join(str(F(K)) for K in query))

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

def solve(k):
    cnt_d = 0
    cnt_m = 0
    ptn_dm = 0
    ans = 0
    for i in range(n):
        if s[i] == "D":
            cnt_d += 1
        if s[i] == "M":
            cnt_m += 1
            ptn_dm += cnt_d
        if s[i] == "C":
            ans += ptn_dm
        
        if i-k+1 >= 0:
            if s[i-k+1] == "D":
                cnt_d -= 1
                ptn_dm -= cnt_m
            if s[i-k+1] == "M":
                cnt_m -= 1
    return ans

for i in k:
    print(solve(i))

Solution (Python):
N =int(input())
S = input()
Q = int(input())
k = list(map(int, input().split()))
D = []
C = []
Sm = [0]*N
S1 = [0]*N

Sc = [0]*N
for i in range(N):
    if S[i] == 'D':
        D.append(i)
    elif S[i] == 'M':
        Sm[i] = 1
    elif S[i] == 'C': 
        C.append(i)
        S1[i] = 1
for i in range(1, N):
    Sm[i] = Sm[i-1]+Sm[i]
    S1[i] = S1[i-1]+S1[i]
for i in C:
    Sc[i] = Sm[i]
for i in range(1, N):
    Sc[i] = Sc[i-1]+Sc[i]
for ki in k:
    res = 0
    for d in D:
        end = min(d+ki-1,N-1)
        res+=Sc[end]-Sc[d]-(S1[end]-S1[d])*Sm[d]
    print(res)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())
    s = input()
    _q = int(input())
    
    for k in map(int,input().split()):
        res = 0
        p = 0
        cnt = 0
        q = 0
        for i in range(n):
            if i >= k:
                if s[i-k] == 'D':
                    cnt -= 1
                    p -= q
                elif s[i-k] == 'M':
                    q -= 1

            if s[i] == 'D':
                cnt += 1
            elif s[i] == 'M':
                p += cnt
                q += 1
            elif s[i] == 'C':
                res += p
        print(res)

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys,bisect
    input = sys.stdin.readline

    n = int(input())
    s = input()
    q = int(input())
    k_list = tuple(map(int,input().split()))
    
    for k in k_list:
        res = 0
        p = 0
        cnt = 0
        q = 0
        for i in range(n):
            if i >= k:
                if s[i-k] == 'D':
                    cnt -= 1
                    p -= q
                elif s[i-k] == 'M':
                    q -= 1

            if s[i] == 'D':
                cnt += 1
            elif s[i] == 'M':
                p += cnt
                q += 1
            elif s[i] == 'C':
                res += p
        print(res)



if __name__ == '__main__':
    main()

Solution (Python):
def main():
    n = int(input())
    s = input()
    q = int(input())
    k = list(map(int, input().split()))
    for ki in k:
        ans = 0
        DMC = [0]*3
        for i in range(n):
            if s[i] == "D":
                DMC[0] += 1
            elif s[i] == "M":
                DMC[1] += 1
                DMC[2] += DMC[0]
            if i >= ki:
                j = i-ki
                if s[j] == "D":
                    DMC[0] -= 1
                    DMC[2] -= DMC[1]
                elif s[j] == "M":
                    DMC[1] -= 1
            if s[i] == "C":
                ans += DMC[2]
        print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
def main():
    n = int(input())
    s = input()
    q = int(input())
    k = list(map(int, input().split()))
    for ki in k:
        ans = 0
        DMC = [0]*3
        for i in range(n):
            c = s[i]
            if c == "D":
                DMC[0] += 1
            elif c == "M":
                DMC[1] += 1
                DMC[2] += DMC[0]
            elif c == "C":
                ans += DMC[2]
            if i >= ki-1:
                j = i-ki+1
                if s[j] == "D":
                    DMC[0] -= 1
                    DMC[2] -= DMC[1]
                elif s[j] == "M":
                    DMC[1] -= 1
        print(ans)
if __name__ == "__main__":
    main()

Solution (Python):
def main():
    n = int(input())
    s = input()
    q = int(input())
    k = list(map(int, input().split()))
    for ki in k:
        D=M=DM=C=0
        for i in range(n):
            if s[i] == "D":
                D += 1
            elif s[i] == "M":
                M += 1
                DM += D
            elif s[i] == "C":
                C += DM
            if i >= ki-1:
                j = i-ki+1
                if s[j] == "D":
                    D -= 1
                    DM -= M
                elif s[j] == "M":
                    M -= 1
        print(C)

if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
s = input()
q = int(input())
k = list(map(int, input().split()))
for ki in k:
    ans = 0
    DMC = [0]*3
    for i in range(n):
        if s[i] == "D":
            DMC[0] += 1
        elif s[i] == "M":
            DMC[1] += 1
            DMC[2] += DMC[0]
        elif s[i] == "C":
            ans += DMC[2]
        if i >= ki-1:
            j = i-ki+1
            if s[j] == "D":
                DMC[0] -= 1
                DMC[2] -= DMC[1]
            elif s[j] == "M":
                DMC[1] -= 1
    print(ans)

Solution (Python):
n = int(input())
s = input()
q = int(input())
k = list(map(int, input().split()))
for ki in k:
    D=M=DM=C=0
    for i in range(n):
        if s[i] == "D":
            D += 1
        elif s[i] == "M":
            M += 1
            DM += D
        if i >= ki:
            j = i-ki
            if s[j] == "D":
                D -= 1
                DM -= M
            elif s[j] == "M":
                M -= 1
        if s[i] == "C":
           C += DM
    print(C)

Solution (Python):
n = int(input())
s = input()
q = int(input())
k = list(map(int, input().split()))
def solve(ki):
    D=M=DM=C=0
    for i in range(n):
        if s[i] == "D":
            D += 1
        elif s[i] == "M":
            M += 1
            DM += D
        elif s[i] == "C":
            C += DM
        if i >= ki-1:
            j = i-ki+1
            if s[j] == "D":
                D -= 1
                DM -= M
            elif s[j] == "M":
                M -= 1
    return C
for ki in k:
    print(solve(ki))

Solution (Python):
n = int(input())
s = input()
q = int(input())
k = list(map(int, input().split()))
for ki in k:
    ans = 0
    DMC = [0]*3
    
    for i in range(n):
        if s[i] == "D":
            DMC[0] += 1
        elif s[i] == "M":
            DMC[1] += 1
            DMC[2] += DMC[0]
        if i >= ki:
            j = i-ki
            if s[j] == "D":
                DMC[0] -= 1
                DMC[2] -= DMC[1]
            elif s[j] == "M":
                DMC[1] -= 1
        if s[i] == "C":
            ans += DMC[2]
    print(ans)

Solution (Python):



n=int(input())
s=input()
q=int(input())
for i in list(map(int,input().split())):
    a=0
    v=[0,0,0]
    for j in range(n):
        if s[j]=="D":
            v[0]+=1
        elif s[j]=="M":
            v[1]+=1
            v[2]+=v[0]
        if j>=i:
            if s[j-i]=="D":
                v[0]-=1
                v[2]-=v[1]
            elif s[j-i]=="M":
                v[1]-=1
        if s[j]=="C":
            a+=v[2]
    print(a)

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

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

DM_total = [(0,0,0)]
C_list = []

for i in range(N):
	if S[i] == "D":
		DM_total.append((DM_total[-1][0] + 1, DM_total[-1][1], DM_total[-1][2]))
	elif S[i] == "M":
		DM_total.append((DM_total[-1][0], DM_total[-1][1] + 1, DM_total[-1][2] + DM_total[-1][0]))
	else:
		DM_total.append(DM_total[-1])
	if S[i] == "C":
		C_list.append(i)


for q in range(Q):
	ans = 0
	for c in C_list:
		if k[q] > c:
			ans += DM_total[c + 1][2]
		else:
			ans += DM_total[c + 1][2] - DM_total[c + 1 - k[q]][2]
			ans -= DM_total[c + 1 - k[q]][0] * (DM_total[c + 1][1] - DM_total[c + 1 - k[q]][1])

	print(ans)

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

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

DM_total = [(0,0,0)]
C_list = []

for i in range(N):
	if S[i] == "D":
		DM_total.append((DM_total[-1][0] + 1, DM_total[-1][1], DM_total[-1][2]))
	elif S[i] == "M":
		DM_total.append((DM_total[-1][0], DM_total[-1][1] + 1, DM_total[-1][2] + DM_total[-1][0]))
	else:
		DM_total.append(DM_total[-1])
	if S[i] == "C":
		C_list.append(i)

ans_list = [0]*Q
for q in range(Q):
	for c in C_list:
		if k[q] > c:
			ans_list[q] += DM_total[c + 1][2]
		else:
			ans_list[q] += DM_total[c + 1][2] - DM_total[c + 1 - k[q]][2]
			ans_list[q] -= DM_total[c + 1 - k[q]][0] * (DM_total[c + 1][1] - DM_total[c + 1 - k[q]][1])

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

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

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

DM_total = [(0,0,0)]
C_list = []

for i in range(N):
	if S[i] == "D":
		DM_total.append((DM_total[-1][0] + 1, DM_total[-1][1], DM_total[-1][2]))
	elif S[i] == "M":
		DM_total.append((DM_total[-1][0], DM_total[-1][1] + 1, DM_total[-1][2] + DM_total[-1][0]))
	else:
		DM_total.append(DM_total[-1])
	if S[i] == "C":
		C_list.append(i)


for q in range(Q):
	ans = 0
	for c in C_list:
		if k[q] > c:
			ans += DM_total[c + 1][2]
		else:
			ans += DM_total[c + 1][2] - DM_total[c + 1 - k[q]][2]
			ans -= DM_total[c + 1 - k[q]][0] * (DM_total[c + 1][1] - DM_total[c + 1 - k[q]][1])

	print(ans)

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

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

DM_total = [(0,0,0)]
C_list = []

for i in range(N):
	if S[i] == "D":
		DM_total.append((DM_total[-1][0] + 1, DM_total[-1][1], DM_total[-1][2]))
	elif S[i] == "M":
		DM_total.append((DM_total[-1][0], DM_total[-1][1] + 1, DM_total[-1][2] + DM_total[-1][0]))
	else:
		DM_total.append(DM_total[-1])
	if S[i] == "C":
		C_list.append(i)

ans_list = [0]*Q
for q in range(Q):
	for c in C_list:
		if k[q] > c:
			ans_list[q] += DM_total[c + 1][2]
		else:
			ans_list[q] += DM_total[c + 1][2] - DM_total[c + 1 - k[q]][2]
			ans_list[q] -= DM_total[c + 1 - k[q]][0] * (DM_total[c + 1][1] - DM_total[c + 1 - k[q]][1])

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

Solution (Python):

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

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

DM_total = [(0,0,0)]
C_list = []

for i in range(N):
	if S[i] == "D":
		DM_total.append((DM_total[-1][0] + 1, DM_total[-1][1], DM_total[-1][2]))
	elif S[i] == "M":
		DM_total.append((DM_total[-1][0], DM_total[-1][1] + 1, DM_total[-1][2] + DM_total[-1][0]))
	else:
		DM_total.append(DM_total[-1])
	if S[i] == "C":
		C_list.append(i)

ans_list = [0]*Q

for c in C_list:
	for q in range(Q):
		if k[q] > c:
			ans_list[q] += DM_total[c + 1][2]
		else:
			ans_list[q] += DM_total[c + 1][2] - DM_total[c + 1 - k[q]][2]
			ans_list[q] -= DM_total[c + 1 - k[q]][0] * (DM_total[c + 1][1] - DM_total[c + 1 - k[q]][1])

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

Solution (Python):
n=int(input())
s=input()
q=int(input())
for i in list(map(int,input().split())):
    a=0
    v=[0,0,0]
    for j in range(n):
        if s[j]=="D":
            v[0]+=1
        elif s[j]=="M":
            v[1]+=1
            v[2]+=v[0]
        if j>=i:
            if s[j-i]=="D":
                v[0]-=1
                v[2]-=v[1]
            elif s[j-i]=="M":
                v[1]-=1
        if s[j]=="C":
            a+=v[2]
    print(a)

Solution (Python):
import os
import sys

import numpy as np

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

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
S = sys.stdin.readline().rstrip()
Q = int(sys.stdin.readline())
K = list(map(int, sys.stdin.readline().split()))

S = np.array(list(S), dtype='S1')
SD = S == b'D'
SM = S == b'M'
SC = S == b'C'
RD = SD.cumsum()
RM = SM.cumsum()


def solve(k):
    D = RD.copy()
    D[k:] -= RD[:-k]
    M = RM.copy()
    M[k:] -= RM[:-k]

    DM = D * SM
    DM[k:] -= M[k - 1:-1] * SD[:-k]
    DM = DM.cumsum()
    return (DM * SC).sum()


for k in K:
    ans = solve(k)
    print(ans)

Solution (Python):
import os
import sys

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

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
S = sys.stdin.readline().rstrip()
Q = int(sys.stdin.readline())
K = list(map(int, sys.stdin.readline().split()))


def solve(k):
    ret = 0
    d = 0
    m = 0
    dm = 0
    l = 0
    r = 0
    while r < N:
        if k <= r:
            if S[l] == 'D':
                d -= 1
                dm -= m
            if S[l] == 'M':
                m -= 1
            l += 1

        if S[r] == 'D':
            d += 1
        if S[r] == 'M':
            m += 1
            dm += d
        if S[r] == 'C':
            ret += dm
        r += 1
    return ret


for k in K:
    ans = solve(k)
    print(ans)

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

M_cum = [0] * (N+1)
for i in range(1, N+1):
    M_cum[i] = M_cum[i-1] + (S[i-1] == 'M')

for q in range(Q):
    k = k_list[q]
    ans = 0
    lose_D = [0] * N
    current_D = 0
    current_DM = 0
    for i in range(N):
        if lose_D[i] == 1:
            current_D -= 1
            current_DM -= (M_cum[i] - M_cum[i-k+1])
        if S[i] == 'D':
            current_D += 1
            if i + k < N:
                lose_D[i+k] = 1
        elif S[i] == 'M':
            current_DM += current_D
        elif S[i] == 'C':
            ans += current_DM
    print(ans)

Solution (Python):
from itertools import accumulate
N = int(input())
S = input()
Di = list(accumulate([1 if s == 'D' else 0 for s in S]))
Mi = list(accumulate([1 if s == 'M' else 0 for s in S]))

dp = [0]*N
for i, s in enumerate(S):
    if s == 'M':
        dp[i] = dp[i-1] + Di[i]
    else:
        dp[i] = dp[i-1]

Q = int(input())
K = list(map(int, input().split()))

for k in K:
    ans = 0
    for i, s in enumerate(S):
        if s == 'C':
            if i - k < 0:
                ans += dp[i]
            else:
                ans += dp[i] - dp[i-k] - Di[i-k]*(Mi[i]-Mi[i-k])
    print(ans)

Solution (Python):
import sys
N = int(sys.stdin.readline())
S = sys.stdin.readline()
Q = int(sys.stdin.readline())
K = list(map(int, sys.stdin.readline().split()))
for i in range(Q):
    k = K[i]
    D = 0
    M = 0
    DM = 0
    num = 0
    for j in range(N):
        if S[j] == 'D':
            D += 1
        elif S[j] == 'M':
            DM += D
            M += 1
        elif S[j] == 'C':
            num += DM
        if j >= k - 1:
            if S[j - k + 1] == 'D':
                D -= 1
                DM -= M
            elif S[j - k + 1] == 'M':
                M -= 1
    print(num)

Solution (Python):
N=int(input())
S=input()
dp_D,dp_M=[0]*(N+1),[0]*(N+1)
dp_DM=[0]*(N+1)
C=[]

for i in range(N):
  dp_D[i+1]=dp_D[i]
  dp_M[i+1]=dp_M[i]
  dp_DM[i+1]=dp_DM[i]
  if S[i]=="D":
    dp_D[i+1]+=1
  if S[i]=="M":
    dp_M[i+1]+=1
    dp_DM[i+1]+=dp_D[i]
  if S[i]=="C":
    C.append(i+1)
    
Q=int(input())
K=[int(k) for k in input().split()]
for k in K:
  ans=0
  for c in C:
    ans+=dp_DM[c-1]-dp_D[max(c-k,0)]*(dp_M[c-1]-dp_M[max(c-k,0)])-dp_DM[max(c-k,0)]
  print(ans)

Solution (Python):
N=int(input())
import sys
input=sys.stdin.readline
S=input()
C_stack=[]
D=[0]*(N+1)
M=[0]*(N+1)
DM=[0]*(N+1)
m=0
for i in range(1,N+1):
  if S[i-1]=="D":
    D[i]=D[i-1]+1
  else:
    D[i]=D[i-1]
  if S[i-1]=="C":
    C_stack.append(i)
  if S[i-1]=="M":
    DM[i]=DM[i-1]+D[i-1]
    M[i]=M[i-1]+1
  else:
    DM[i]=DM[i-1]
    M[i]=M[i-1]

Q=int(input())
K=[int(i) for i in input().split()]
for q in range(Q):
  ans=0
  k=K[q]
  for c in C_stack:
    ans+=DM[c]-DM[max(0,c-k)]-D[max(0,c-k)]*(M[c]-M[max(0,c-k)])
  print(ans)

Solution (Python):
N=int(input())
S=input()
Q=int(input())
K=[int(i) for i in input().split()]
def f(k):
    num=0
    L=[0,0,0]
    for i in range(N):
        if i-k>=0:
            if S[i-k]=='D':
                L[0]-=1
                L[2]-=L[1]
            elif S[i-k]=='M':
                L[1]-=1
        if S[i]=='D':
            L[0]+=1
        elif S[i]=='M':
            L[1]+=1
            L[2]+=L[0]
        elif S[i]=='C':
            num+=L[2]
        
    return num
for k in K:
    print(f(k))

Solution (Python):
import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n = ni()
s = " " + ns()
q = ni()
k = list(li())

def find_ans(k:int):
    cnt = [0,0,0]
    ans = 0
    
    for i in range(1, n+1):
        
        if s[i] == 'C':
            ans += cnt[2]

        if i-k+1 > 0:
            if s[i-k+1] == 'D':
                cnt[0] -= 1
                cnt[2] -= cnt[1]
                
            elif s[i-k+1] == 'M':
                cnt[1] -= 1
                
        if s[i] == 'D':
            cnt[0] += 1    
        
        elif s[i] == 'M':
            cnt[2] += cnt[0]
            cnt[1] += 1

            
    return ans
        
for ki in k:
    print(find_ans(ki))