[問題案] Range Reverse Range Sum

[ageprocpp]

(任意) 問題ID: {ID} 問題名: {RMQ and Reversing}

(任意) 想定アルゴリズム: {平衡二分木} (任意) 参考資料: {https://www.slideshare.net/iwiwi/2-12188757}

問題概要

数列がある. 一点変更, 区間の reverse, 区間の最小値取得を実現せよ.

入力

N Q
a_0 a_1 ... a_{N-1}
query_0
query_1
.
.
.
query_{N-1}

制約

N,Qは5*10^5くらい

HLDが終わったあとにいきなり実装が重くて平衡二分木を使う動的木が要求されるのは辛いと思うので、一般的な平衡二分木のverify用問題が欲しかったです

[yosupo06]

提案ありがとうございます！　見落としていました、すいません…

平衡二分探索木は https://github.com/yosupo06/library-checker-problems/issues/242 が準備待ちで、これだと大変すぎるでしょうか？

[ageprocpp]

平衡二分木で実現できる操作とその他のデータ構造で実現できない操作の最大公約数をとったつもりです（ #242 はちょっとハードルが高いと、自分は感じました）

[yosupo06]

なるほど、minはケース制作が難しいので、区間の総和か区間の1次関数の合成( https://judge.yosupo.jp/problem/point_set_range_composite )がいいと思います。

IDは前者ならRange Reverse Range Sum でしょうか

[ageprocpp]

ありがとうございます。 区間の総和が楽でよさそうですね、そうします。 かくいう私が平衡二分木を書いたことがない（書こうとして使える問題を探していたらここになかったので提案しました）ので、書いて PR 送ろうと思います。

[maspypy]

作業されなさそうなので、作業者募集にしておきます。

[noshi91]

準備します