問題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 使用量が大きい