yosupo https://blog.hatena.ne.jp/yosupo/ よすぽの日記 https://yosupo.hatenablog.com/ 与えられたデータの文字列についてTrie木を構築しますそのTrie木をEuler-TourしてBITを構築します Trie木の頂点ごとに、BITで対応する範囲[l, r]がどこなのかも一緒に計算しておきますその後、文字列ごとに、もう一度Trie木を潜ってその文字列の最後の頂点がBITのどこに対応するかを計算しますクエリ1は、その文字列の最後の頂点に対応するBITの値を+xするクエリ2は、その文字列の最後の頂点に対応するBITの範囲のsumを取る(対応する頂点がない場合は0) おまけ クエリ3として、文字列Sが与えられるから全部のデータについて(Sとの共通しているprefixの長さ)*値 の s… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fyosupo.hatenablog.com%2Fentry%2F2015%2F03%2F31%2F222811" title="今日の典型データ構造②(解答編) - よすぽの日記" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2015-03-31 22:28:11 rich https://yosupo.hatenablog.com/entry/2015/03/31/222811 1.0 100%