読者です 読者をやめる 読者になる 読者になる

今日の典型データ構造②(解答編)

与えられたデータの文字列についてTrie木を構築します

そのTrie木をEuler-TourしてBITを構築します
Trie木の頂点ごとに、BITで対応する範囲[l, r]がどこなのかも一緒に計算しておきます

その後、文字列ごとに、もう一度Trie木を潜ってその文字列の最後の頂点がBITのどこに対応するかを計算します

クエリ1は、その文字列の最後の頂点に対応するBITの値を+xする

クエリ2は、その文字列の最後の頂点に対応するBITの範囲のsumを取る(対応する頂点がない場合は0)


おまけ

クエリ3として、文字列Sが与えられるから

全部のデータについて(Sとの共通しているprefixの長さ)*値 の sum を求める

というクエリが追加される

例えば

{kitayuta, 100}
{kitakita, 10}
{kitsune, 30}
{kansai, -10}

にS=kitaが与えられたら

(4 * 100)(kita) + (4 * 10)(kita) + (3 * 30)(kit) + (-10 * 1)(k) = 520

となる

クエリ3で与えられる文字列の長さも総和は10^6以下