けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

平衡二分探索木

AtCoder ABC 234 D - Prefix K-th Max (茶色, 400 点)

あまりにも色んな解法がある問題 問題へのリンク 問題概要 の順列 と正の整数 が与えられる。 各 に対して、順列の先頭から 個の値の中での 番目に大きい値を求めよ。 制約 考えたこと 次の問題の下位互換と言える。 drken1215.hatenablog.com この上位互換…

AOJ 3170 Freqs (HUPC 2020 day1-G)

難しかったー!!平方分割かな...とまでは思ったので、もっと粘り強く考えられるようにならないと...! 問題へのリンク 問題概要 長さ の数列 が与えられます。以下の 4 種類のクエリを 回処理してください。 クエリ 1: が与えられるので、 () を に更新する…

AtCoder ARC 033 C - データ構造 (試験管青色)

BinaryTrie を確認した!!! 問題へのリンク 問題概要 数の集合 S に対する以下のクエリ ( 個) を処理してください。 S に数 X を追加する S に含まれる数のうち X 番目に小さい数を答え、その数を S から削除する 制約 考えたこと BIT や priority_queue、…

AOJ 2890 ピボット (AUPC 2018 day3 B)

勉強になった。 問題へのリンク 問題概要 1 〜N の順列 a1, a2, ..., aN が与えられる。 この順列に対して Q 個のクエリが順に与えられる。i 番目のクエリでは次の操作をしなければならない: 値 q が与えられる。順列 {a1, a2,…,aN} において qiの左側の順列…

yukicoder 649 ここでちょっとQK!

yukicoder 649 ここでちょっとQK! K は固定で与えられる。数の集合 S に対する以下の Q 個のクエリを処理してください。i 番目のクエリは以下のいずれかです。 タイプ 1: S に数 v[i] を追加する。 タイプ 2: S に含まれる数のうち K 番目に小さい数を答…