drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ AtCoder AtCoder500点 ABC-E 水色diff K番目を求める priority_queue データ構造テク：全体に反映させる値を別にもつ(遅延評価) BinaryTrie BIT BIT上二分探索 データ構造 クエリ処理問題 WaveletMatrix setの上手な使い方 座標圧縮 データ構造テク：差分更新 セグメント木 数列 区間 各kに対して クエリ先読み 典型要素を詰め合わせた教育的問題 削除可能priority_queue 操作:挿入 操作:削除 取得:K番目に小さい値 セグメント木上の二分探索 NoviSteps1D 区間window問題 よくあるデータ構造問題！！ めっちゃ色んな解法がある！ 問題へのリンク 問題概要 長さ の整数列 と整数 が与えられる (0-indexed で表している)。 各 に対して、次の問題に答えてください。 個の整数 を小さい順に並び替えたときの先頭 個の総和を求めよ。 制約 考えたこと 要は次のクエリを高速に処理できるデータ構造があればよい。 値 を挿入する 値 を削除する (複数個ある場合は 1 個だけ削除する) 小さい方から数えて 番目の値を求める このデータ構造を用いて、「値 を push する」「値 を pop する」という処理 (後述) をそれぞれ実装しておくことで、今回の問題は次のよう… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2022%2F12%2F14%2F185200" title="AtCoder ABC 281 E - Least Elements (1D, 水色, 500 点) - けんちょんの競プロ精進記録" 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 2022-12-14 18:52:00 rich https://drken1215.hatenablog.com/entry/2022/12/14/185200 1.0 100%