提出 #70612858

---

ソースコード 拡げる

import sys
import bisect

input = sys.stdin.readline

class FenwickTree:
    def __init__(self, n):
        self._n = n
        self.data = [0] * n

    def add(self, k, v):
        k += 1
        while k <= self._n:
            self.data[k - 1] += v
            k += k & -k

    def query(self, k):
        k += 1
        s = 0
        while k > 0:
            s += self.data[k - 1]
            k -= k & -k
        return s


N, A, B = map(int, input().split())
S = input().strip()

count_a = [0] * (N + 1)
for i in range(N):
    count_a[i + 1] = count_a[i] + (1 if S[i] == 'a' else 0)

X = count_a
Y = [count_a[i] - i for i in range(N + 1)]


sorted_Y = sorted(list(set(Y)))
M = len(sorted_Y) 
events = []

for j in range(N + 1):
    x_j = X[j]
    y_j = Y[j]
    y_idx = bisect.bisect_left(sorted_Y, y_j)
    events.append((x_j, j, 1, y_idx))

for r in range(1, N + 1):
    x_q = X[r] - A
    y_q_val = Y[r] + B - 1
    
    y_q_idx = bisect.bisect_right(sorted_Y, y_q_val) - 1
    
    events.append((x_q, r, 0, y_q_idx))


events.sort()

#平面走査 (BIT を使って処理)
bit = FenwickTree(M)
ans = 0

for x, t, type, y_idx in events:
    if type == 1:

        bit.add(y_idx, 1)
    else:
        if y_idx >= 0:
            #区間 [0, y_q_idx] の和を求める
            ans += bit.query(y_idx)

print(ans)

提出情報

ジャッジ結果