[問題案] Sequence Insert Erase Reverse Range Affine Range Sum

[kmyk]

(任意) 問題ID: {ID} 問題名: {名前}

問題概要

配列上の完全二分木の上でなく赤黒木とかの上で遅延伝播セグ木をやるやつです

長さNの整数列a_0, a1, ..., a{N - 1}が与えられる。Q個のクエリを処理

• 0 l r c d: a_l, ..., a_r-1それぞれについて、a_i = c * a_i + bをする
• 1 l, r: a_l ~ a_r-1の総和を出力
• 2 i, k, b_0, ..., b_{k-1}: 位置 i に整数 b0, ..., b{k-1} を挿入 (新しい列は a0, ..., a{i - 1}, b0, ..., b{k-1}, ai, ..., a{N-1} になる)
• 3 l, r: a_l ~ a_r-1 を削除 (新しい列は a0, ..., a{l - 1}, ar, ..., a{N-1} になる)
• 4 l, r: a_l ~ a_r-1 を反転 (新しい列は a0, ..., a{l - 1}, a_{r-1,}, ..., a_l, ar, ..., a{N-1} になる)

全てmod 998244353

入力

出力

制約

• insert クエリで挿入される列の長さの合計は 500,000 (?) を越えない
• https://judge.yosupo.jp/problem/range_affine_range_sum とだいたい同じ

検討事項

1. 問題IDについて。
   • 拡張性の問題がない中で一番ましそうなのは Sequence Insert Erase Reverse Range Affine Range Sum だと思う
   • Sequence Insert Sequence Erase Sequence Reverse Range Affine Range Sum はさすがに長い
   • Dynamic Sequence Range Affine Range Sum とまとめるのはよさそうだが、将来的に Dynamic Sequence (反転あり) と Dynamic Sequence (反転なし) が混在しちゃうと嫌な気がする
   • Dynamic Sequence Sequence Reverse Range Affine Range Sum とまとめるのはあるが、中途半端で結局長い
2. 上に乗せるモノイドについて。
   • Range Affine Range Sum はとりあえず標準的な中で一番つよいやつのはず
   • Range Add Range Min でもいいかも？ 可換性を仮定しちゃうけど Range Sum もなので変わらない
   • 遅延伝播部分を蛇足だと判断するなら Range Composite になりそう
3. 反転を入れるかどうか。
   • どうせだしほしい。反転ありバージョンと反転なしバージョンをふたつ問題を作りたくはない
   • insert/erase だけの方が問題がシンプルでよいという意見はありそう
4. クエリはこの形の insert/erase でいいか。
   • merge/split の方向はどういうクエリにするか難しい
   • 1点 insert でも変わらないけど、erase は区間にしたい気がするし揃えたさがある
5. 永続化について。
   • たぶんすぐに永続化したバージョンの問題もほしくなる予定です

[yosupo06]

提案ありがとうございます！　いろいろ考えてたのと、新年の諸々で返信が遅れました

2. 上に乗せるモノイドについて。

Range Affine Range Sum(か、非可換をテストしたいならRange Composite)でいいと思います　Range Add Range Minは有名なのですがテストケースが作りにくいなどがあり

3. 反転を入れるかどうか。

入れていいと考えてます

(insert / erase)だけの方がシンプルでいいというか、reverseが出来ない木が存在するんですが(AA-Treeなど)、k番目が取得できるstd::setの需要の高まりを感じるんで、そっちでうまいことベリファイできるかなと思ってます。

4. クエリはこの形の insert/erase でいいか。

素直に考えるとinsert / eraseは1個ずつの方が自然なはずで、任意個数にしたい理由を確認しておきたいです(iteratorかな？と考えてます)？

5. 永続化について。

range copyか操作ごとに操作後の木にID降るかかなぁと考えてます

1. 問題IDについて。

順番が入れ替わりましたが最後に

マイナーチェンジ版を作らないならDynamic Sequenceでいいかなと思ってます　今のところ反転なしはstd::setの拡張の方でやるつもりなので(ただ平衡二分木が深淵ということはわかってきたので、後で破綻する確率も高く

[windows-server-2003]

これ仕様固まってたらやりたいんですが、うさぎさんからの返信がなくてどうも固まってなさそうに見えます

[yosupo06]

ID: Dynamic Sequence Range Affine Range Sum 反転: あり Insert / Erase : 1個ずつ

という気分です

[windows-server-2003]

やります

[windows-server-2003]

やります !

[yosupo06]

了解です