ABC 401-500/ABC417F - Random Gathering - 競技プログラミング用 知識集積所

---

問題

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木※でも解けるらしい。

後で書く。