2015-03-31から1日間の記事一覧

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

与えられたデータの文字列についてTrie木を構築しますそのTrie木をEuler-TourしてBITを構築します Trie木の頂点ごとに、BITで対応する範囲[l, r]がどこなのかも一緒に計算しておきますその後、文字列ごとに、もう一度Trie木を潜ってその文字列の最後の頂点が…

今日の典型データ構造②

今日の典型データ構造です。N個のpairが与えられます ただしstringの長さは合計して10^6以下ですQ個の以下のクエリが与えられる k(int), x(int) が与えられる k番目のデータのintを+xする s(string) が与えられる s をprefixに持つ文字列を持つデータのintの…

最小カットについて

わっけわかんねえほど沢山の制約ドパァな問題を解く一般的なテクとして、なんかいい感じのグラフを作ったらなんかそれの最小カットが答えというのがあります最小カットで解ける問題はどんなのなのか考えてみました 頂点がたくさんあって、それを赤と青に塗り…

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

今日の典型データ構造 - よすぽの日記yosupo.hatenablog.com長さNの、bool列(全部の要素が0 or 1)に対して以下のクエリがQ個飛んでくるl, rが与えられるから, l番目~r番目の数列を切り出した時、それの転倒数を求める l, rが与えられるから, l番目~r番目の要…