2012-09-23から1日間の記事一覧
問題文 : タコヤキオイシクナール解法 : Nに対してMが小さいので, Nの座標圧縮を前もって行なっておく. (こうしても正しい結果が得られることは, 美味しさrのたこ焼きが(1, 0)と書かれたタコヤキオイシクナールを通っても美味しさrが保たれることから分かる.…
問題文 : Frequent values解法 : 各ノードは昇順になっているため、各数字の出現頻度をノードとして持つセグメント木を構築する. 各クエリについて, a[s] = a[t]であればt - s + 1を, そうでなければa[s]とa[t]を適切なだけ削り, RMQの処理を行う.コード : #…