デンソークリエイトプログラミングコンテスト2022（AtCoder Beginner Contest 239） - E - Subtree K-th Max

の場合でも解けるかつ、高度なデータ構造などを用いない解法 (オフラインです)

並列二分探索をします。

並列二分探索を知らない方は、

betrue12.hateblo.jp

などを参考にしてください。

オイラーツアーを用いると、部分木の状態を列で表すことができます。並列二分探索を用いて、1 回の処理につき、値が大きい方からしゃくとり法のように見ていけば、Binary Indexed Tree などを用いて、 で求めることができました。

詳しい処理は、コメントなどもいれたのでコードを読んでください。

提出コード (232 ms)

atcoder.jp