結果

問題 No.3239 Omnibus
ユーザー detteiuu
提出日時 2025-09-30 21:50:27
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,316 ms / 10,000 ms
コード長 2,523 bytes
コンパイル時間 314 ms
コンパイル使用メモリ 82,292 KB
実行使用メモリ 191,712 KB
最終ジャッジ日時 2025-09-30 21:51:24
合計ジャッジ時間 56,655 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

from bisect import bisect_left, bisect_right

class BIT:
    def __init__(self, A):
        self.size = len(A)
        self.bit = [0]*(len(A)+1)
        for i in range(len(A)):
            self.add(i, A[i])

    def sum(self, i):
        i += 1
        ans = 0
        while i > 0:
            ans += self.bit[i]
            i -= -i&i
        return ans
    
    def query(self, l, r):
        if l == 0:
            return self.sum(r-1)
        else:
            return self.sum(r-1)-self.sum(l-1)
    
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.bit[i] += x
            i += -i&i

def compress(A):
    S = sorted(set(A))
    D = dict()
    for i in range(len(S)):
        D[S[i]] = i
    return D, S

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

def code(s):
    return ord(s)-ord("a")
def codeR(n):
    return chr(ord("a")+n)

def encode(s):
    return 26**2*code(s[0])+26*code(s[1])+code(s[2])

F = [set() for _ in range(26**3)]
for i in range(N-2):
    F[encode(S[i:i+3])].add(i)

S2 = S[:]
for i in range(Q):
    if query[i][0] == "1":
        k, x = query[i][1:]
        k = int(k)-1
        S2[k] = x
        for j in range(max(k-2, 0), min(k, N-3)+1):
            F[encode(S2[j:j+3])].add(j)

D = [[] for _ in range(26**3)]
SI = [[] for _ in range(26**3)]
FC = [[] for _ in range(26**3)]
for i in range(26**3):
    if len(F[i]) == 0:
        F[i] = []
        continue
    D[i], SI[i] = compress(F[i])
    L = len(F[i])
    F[i] = BIT([0]*L)
    FC[i] = BIT([0]*L)

for i in range(N-2):
    idx = encode(S[i:i+3])
    F[idx].add(D[idx][i], i)
    FC[idx].add(D[idx][i], 1)

for i in range(Q):
    if query[i][0] == "1":
        k, x = query[i][1:]
        k = int(k)-1
        for j in range(max(k-2, 0), min(k, N-3)+1):
            idx = encode(S[j:j+3])
            F[idx].add(D[idx][j], -j)
            FC[idx].add(D[idx][j], -1)
        S[k] = x
        for j in range(max(k-2, 0), min(k, N-3)+1):
            idx = encode(S[j:j+3])
            F[idx].add(D[idx][j], j)
            FC[idx].add(D[idx][j], 1)
    else:
        l, r, a = query[i][1:]
        l, r = int(l)-1, int(r)-1
        if r-l+1 < 3:
            print(0)
            continue
        idx = encode(a)
        if type(F[idx]) == list:
            print(0)
            continue
        b, c = bisect_left(SI[idx], l), bisect_right(SI[idx], r-2)
        SUM = F[idx].query(b, c)
        cnt = FC[idx].query(b, c)
        print((SUM+cnt)-l*cnt)
0