の場合でも解けるかつ、高度なデータ構造などを用いない解法 (オフラインです)
並列二分探索をします。
並列二分探索を知らない方は、
betrue12.hateblo.jp
などを参考にしてください。
オイラーツアーを用いると、部分木の状態を列で表すことができます。並列二分探索を用いて、1 回の処理につき、値が大きい方からしゃくとり法のように見ていけば、Binary Indexed Tree などを用いて、
で求めることができました。
詳しい処理は、コメントなどもいれたのでコードを読んでください。
提出コード (232 ms)
atcoder.jp
