ABC 401-500/ABC450F - Strongly Connected 2 - 競技プログラミング用 知識集積所

---

問題

ABC450F

必要知識

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

• lazy segment木※
• 動的計画法
• 剰余類環

考え方

強連結にする問題ではあるが、番号が大きい方から小さい方に移動する辺は固定で保証されている。
そのため、0スタートで到達できる最大番号がXである場合、0以上X以下全て到達可能ということになる。
ということで、M個の辺全てについて、ON/OFFの2択で合計2^Mパターンそれぞれ最大何番まで到達できるかを考え、N-1番まで到達できる個数を答えればいい。

そのためには動的計画法を用いる。
最初に全ての辺を仮にOFF/OFFの疑似2択にしておく。
そこから1辺ずつON/OFFの本当の2択に変更し、何番まで到達できるものが何個あるかの情報をvector的な構造で持ち、更新していけばよい。

このとき、L1→R1、L2→R2（L1<L2）という2つの辺について、L2→R2を先に処理すると後でL1→R1の方を処理したときにそこから続けてL2の辺を利用することでもっと遠くに行ける可能性がありややこしい。
始点番号が小さい方から順に処理していくこと。
この順を守れば、L→Rを処理するときに、最高到達点がLより左になっているものが後でLより右になることは絶対ないし、すでにRより右になっているものがRより左に戻ってくることもない。
よって、単にL以上R未満のところが限界点になっているもののうち半分をRに移せばよい。
（スタートが2^M個あったので、割り切れないことは絶対にない）

ということで、vector的な構造には「区間全体を半分にする」「区間の合計を出す」「1点に値を加算する」という操作が必要。
lazy segment木※ならこれら全てが可能である。

答えは998244353で割った余りを要求されているので、剰余類環の考えに従って処理する。

解答例

解答例

注意点

別解