[問題案] Persistent Range Affine Range Sum

[NachiaVivias]

問題ID: persistent_range_affine_range_sum 問題名: Persistent Range Affine Range Sum

想定アルゴリズム: 遅延セグメント木の path copying 参考資料: https://37zigen.com/persistent-segment-tree/

問題概要

Range Affine Range Sum を永続化 + α

初期状態を X[-1] とする

クエリ 0 t l r c d : X[t] の a[l..r] に x←cx+d を作用して X[i] とする クエリ 1 t s l r : X[t] の a[l..r] を、 X[s] の a[l..r] で置き換えたものを X[i] とする クエリ 2 t l r : X[t] で a[l..r] の総和を出力

入力

N Q
a[0] a[1] ... a[N-1]
0 t l r c d
1 t s l r
2 t l r
 :

出力はクエリ通り

制約

N,Q <= 10^5 とかじゃないと、たぶん RAM 使用量が大きい

[maspypy]

よいと思います。

[maspypy]

作業者募集で。