結果

問題 No.2020 Sum of Common Prefix Length
ユーザー navel_tos
提出日時 2025-05-01 20:53:37
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 800 ms / 2,000 ms
コード長 2,990 bytes
コンパイル時間 384 ms
コンパイル使用メモリ 82,712 KB
実行使用メモリ 238,784 KB
最終ジャッジ日時 2025-05-01 20:54:03
合計ジャッジ時間 23,107 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff # 

#yukicoder2020 Sum of Common Prefix Length

#BITを書く
class BinaryTree:
    def __init__(self, N):
        self._N = N
        self._node = [0] * (N + 1)
    def add(self, i, v):  #A[i] += v
        i += 1
        while i <= self._N:
            self._node[i] += v
            i += i & - i
    def sum(self, i):  #A[0, 1, ･･･, i]
        i += 1
        ans = 0
        while i > 0:
            ans += self._node[i]
            i ^= i & - i
        return ans
    def fold(self, Lt, Rt):  #A[Lt, ･･･, Rt]
        ans = 0
        while Lt != Rt:
            if Lt > Rt:
                ans -= self._node[Lt]
                Lt ^= Lt & - Lt
            else:
                ans += self._node[Rt]
                Rt ^= Rt & - Rt
        return ans


#入力受取  英小文字は[0, 26)に置換
N = int(input())
S = [ [ord(s) - ord('a') for s in input()] for _ in range(N) ]
query = [None] * ( Q := int(input()) )
for q in range(Q):
    t, *x = input().split()
    if t == '1':
        query[q] = ( 1, int(x[0]) - 1, ord(x[1]) - ord('a') )
    else:
        query[q] = ( 2, int(x[0]) - 1, 0 )

#初期状態のSの長さをF[i]としておく。SのTrieを構築
F = [len(S[i]) for i in range(N)]
for t, x, c in query:
    if t == 1:
        S[x].append(c)

#S[i]ごとに、各文字を採用後に何番のノードに到達したか記録しておく
#Trie木を構築しながら隣接リストを作成
Trie = [[-1] * 26]
G = [[]]
T = [None] * N
for i, Si in enumerate(S):
    Ti = [0] * len(Si)
    now = 0
    for j, s in enumerate(Si):
        if ( nxt := Trie[now][s] ) == -1:
            G[now].append(len(G))
            G.append([now])
            Trie[now][s] = now = len(Trie)
            Trie.append([-1] * 26)
        else: now = nxt
        Ti[j] = now
    T[i] = Ti
n = len(Trie)
del Trie[:], Trie

#木DPの形になったのでEuler Tour
stack = [0]
visit = [0] * n  #入りがけ << 31 | 出がけ の時刻
mask = ~ ( - 1 << 31)
for t in range(n << 1):
    if ( now := stack.pop() ) >= 0:
        visit[now] |= t << 31
        stack.append(~ now)
        for nxt in G[now]:
            if now < nxt:  #Trie木の構造上、子ノードは常に番号が小さい
                stack.append(nxt)
    else:
        visit[now := ~ now] |= t

#ETの経路上に1を置く。LCPはETの根からの経路和に等しい
#imos法でいいはず  入りがけ時刻に+1 出がけ時刻に-1
BIT = BinaryTree(n << 1)
for Ti, Fi in zip(T, F):
    for f in range(Fi):  #node[Ti][f]について区間加算
        v = visit[ Ti[f] ]
        AD, DC = admission, discharge = v >> 31, v & mask
        BIT.add(AD, + 1)
        BIT.add(DC, - 1)
        
#クエリを処理
for t, x, c in query:
    if t == 1:  #S[x] += c
        v = visit[ T[x][ F[x] ] ]
        AD, DC = v >> 31, v & mask
        F[x] += 1
        BIT.add(AD, + 1)
        BIT.add(DC, - 1)
    if t == 2:  #fold
        AD = ( v := visit[ T[x][ F[x] - 1 ] ] ) >> 31
        print(BIT.sum(AD))
0