Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()
Q = int(input())
*k, = map(int, input().split())

lc = [1 if s=="C" else 0 for s in S]
ld = [1 if s=="D" else 0 for s in S]

ac = [0]*(N+1)
for i in range(1, N+1):
    ac[i] = ac[i-1] + lc[i-1]

ans = 0

for a in k:
    ans = 0
    for i, s in enumerate(S):
        if s!="M":
            continue
        for j in range(max(i-a, 0), i):
            ans += ld[j]*(ac[min(a+j, N)]-ac[i])
    print(ans)

Fixed submission:
N = int(input())
S = input()
Q = int(input())
*k, = map(int, input().split())

acd = [0]*(N+1)
acm = [0]*(N+1)
acc = [0]*(N+1)
acmc = [0]*(N+2)

for i in range(1, N+1):
    acd[i] = acd[i-1] + (S[i-1]=="D")
    acm[i] = acm[i-1] + (S[i-1]=="M")
    acc[i] = acc[i-1] + (S[i-1]=="C")

ans = 0
for i in range(1, N+1):
    if S[i-1]=="M":
        ans += acd[i-1]*(acc[N]-acc[i])

for i in range(1, N)[::-1]:
    acmc[i] += acmc[i+1]
    if S[i-1]=="M":
        acmc[i] += acc[N]-acc[i]

for i in k:
    v = 0
    for j in range(1, N+1):
        if S[j-1]=="D":
            v += (acm[min(N, i+j-1)]-acm[j]) * (acc[N]-acc[min(N, i+j-1)]) + acmc[min(i+j, N)]
    print(ans-v)

Buggy python submission (verdict: Time Limit Exceeded):
from operator import add


class SegTree():
    def __init__(self, N, e, operator_func=add):
        self.e = e # 単位元
        self.size = N
        self.node = [self.e] * (2*N)
        self.operator_func = operator_func # 処理(add or xor max minなど)

    def set_list(self, l):
        for i in range(self.size):
            self.node[i+self.size-1] = l[i]
        for i in range(self.size-1)[::-1]:
            self.node[i] = self.operator_func(self.node[2*i+1], self.node[2*i+2])
    
    def update(self, k, x):
        k += self.size-1
        self.node[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.node[k] = self.operator_func(self.node[2*k+1], self.node[2*k+2])

    def get(self, l, r):
        # [l, r) についてqueryを求める
        x = self.e
        l += self.size
        r += self.size

        while l<r:
            if l&1:
                x = self.operator_func(x, self.node[l-1])
                l += 1
            if r&1:
                r -= 1
                x = self.operator_func(x, self.node[r-1])
            l >>= 1
            r >>= 1
        return x


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

l = [1 if s=="C" else 0 for s in S]
tree = SegTree(N, 0)
tree.set_list(l)

ans = 0

for a in k:
    ans = 0
    for i, s in enumerate(S):
        if s!="M":
            continue
        for j in range(max(i-a, 0), i):
            if S[j]=="D":
                ans += tree.get(i, min(a+j, N))
    print(ans)

Fixed submission:
N = int(input())
S = input()
Q = int(input())
*k, = map(int, input().split())

acd = [0]*(N+1)
acm = [0]*(N+1)
acc = [0]*(N+1)
acmc = [0]*(N+2)

for i in range(1, N+1):
    acd[i] = acd[i-1] + (S[i-1]=="D")
    acm[i] = acm[i-1] + (S[i-1]=="M")
    acc[i] = acc[i-1] + (S[i-1]=="C")

ans = 0
for i in range(1, N+1):
    if S[i-1]=="M":
        ans += acd[i-1]*(acc[N]-acc[i])

for i in range(1, N)[::-1]:
    acmc[i] += acmc[i+1]
    if S[i-1]=="M":
        acmc[i] += acc[N]-acc[i]

for i in k:
    v = 0
    for j in range(1, N+1):
        if S[j-1]=="D":
            v += (acm[min(N, i+j-1)]-acm[j]) * (acc[N]-acc[min(N, i+j-1)]) + acmc[min(i+j, N)]
    print(ans-v)