ABC 401-500/ABC417F - Random Gathering - 競技プログラミング用 知識集積所【8/3更新】

---

問題

ABC417F

必要知識

B以下レベルの内容は省略

• ランレングス圧縮（未作成）
• 剰余類環
• 繰り返し二乗法（未作成）

考え方

期待値と平均は、意味こそ違えど計算はほぼ同じ。
つまり、やっていることはただ範囲内を全部平均化しているだけである。

この場合、同じデータが大量に並ぶことになるので、set（未作成）上でランレングス圧縮（未作成）っぽい構造を使うことで高速化できる。
すなわち、tuple（未作成）で例えば{3,5,10}だったら、「3番目から5番目までは10」という意味にして、set（未作成）に詰め込んでおく。

操作ごとに、

• set（未作成）から、区間[l,r]に一部でも重なるものをゴッソリdeque（未作成）に取り出し、取り出した分を削除する
• 端について、deque（未作成）内に取りすぎた場合、圧縮を2つに分けて、[l,r]に重なる部分はdeque（未作成）に戻し、はみ出る部分はset（未作成）に戻す
• deque（未作成）内の総計を出し、和を取った個数で割り平均値にする
• 平均化した部分を圧縮されたデータとして元に戻す

をやればよい。

一度でも参照されたデータはset（未作成）から消え、戻すのは毎回最大3個なので、計算量はO( (N+Q)log(N+Q) )（……たぶん）で、十分間に合う。

答えは998244353で割った余りを要求されているので、剰余類換（未作成）の考えに従って処理する。
何か足し算や掛け算をするたびに結果を%998244353し、割り算は代わりに998244353-2乗したものを掛ける。
累乗計算を何度も行うため、繰り返し二乗法（未作成）のアルゴリズムも用意しておくこと。

解答例

解答例

注意点

別解

lazy regment木（未作成）でも解けるらしい。

後で書く。