ABC174F
考えたこと
範囲内に色ciが存在するかどうかを対数オーダーで判定できれば間に合う
二分探索
実装
7分で実装、提出、TLE
あ、全然ダメだ、各色ごとN件につき対数オーダーで範囲内にあるかどうか判定できてもO(QNlogN)だ
改めて考察
それでも最悪O(QN)か
玉の色の集合を2^nのブロックごとに作る
集合は全部で2N-1個
logN回のマージで要求された区間の色の集合ができる
しかし普通にやるとマージが重くて結局O(QN)
マージが軽い二項ヒープを使う？
公式解説
区間クエリといえばセグメント木だが、マージが重い
各時点での各色の「最も右の球の場所」をメンテする
これがLより大きければ、範囲内にその色がある、定数オーダー
しかしこれでもO(QN)
各色の「最も右の球の場所」をフェニック木に入れる
個数を数えることが範囲和で対数オーダー
なるほど、ここがポイントか
3TLE
from ABC174
ARC174F
Related Pages
- →数え上げ×degwer×状態をまとめる×dpは全探索の高速化×arc059f×codefestival_2016_final_f×aoj2439×探索順の変更×大きい順に並べる×aoj2333×順列は挿入dp×bit_dp×区間は終点でソート×条件の言い換え×操作は多いが産物は少ない×agc013d×線形和への分解×演算順序の変更×ビット演算を桁ごとに分解×部分群×操作が可逆で全域→部分群×ラグランジュの定理×再帰的定義→dp×arc037d×桁dp×aoj0570×累積和×フェニック木×高速フーリエ変換×ntt×高速ゼータ変換×and_と_add_の畳み込み×二分累乗×agc013e×行列木定理×全域木の個数×lgv公式×非交叉経路の個数×小さい確率を無視する×二項係数の公式×経路数×45度回転×xとyにわける×カタラン数×包除原理×agc005d×約数系包除×arc064f→
- →atcoder×abc168×abc169×abc170×abc171×abc172×abc173×ABC174×abc175×abc176×abc177×abc178×abc179×abc180×abc181×abc182×abc183→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]