010 - Copy&Sum
時間制限 2 秒 / メモリ制限 256 MB / 得点 12 / x 0 /
問題文
長さ$N$の数列$A$と数列$B$がある。$A$と$B$の$i$番目の要素をそれぞれ$a_{i}$と$b_{i}$で表す。ただし、$i$は$1$から$N$までの整数である。これらの数列に対して以下の操作を行う。
$\bullet \ copy(x,y,z):a_{x}, a_{x+a}, \ldots, a_{x+z-1}$の値をそれぞれ、$b_{y}, b_{y+1}, \ldots, b_{y+z-1}$の値に置き換える。
$\bullet \ sum(p,q):a_{p} + a_{p+1} + \ldots + a_{q}$の値を出力する。
課題
数列$A$,$B$と、いくつかの操作が与えられるとき、操作$sum$の結果を出力するプログラムを作成せよ。
入力
入力は以下の形式で与えられる。
$N \ M$ $a_{1} \ a_{2} \ \ldots \ a_{N}$ $b_{1} \ b_{2} \ \ldots \ b_{N}$ $op_{1}$ $op_{2}$ $\vdots$ $op_{M}$
1行目に数列の長さ$N\ (1 \leq N \leq 200,000)$と操作の数$M(1 \leq M \leq 200,000)$が与えられる。
続く1行に数列Aの$i$番目の要素$a_{i}\ (0 \leq a_{i} \leq 1,000,000,000)$が整数で与えらえる。
続く1行に数列$B$の$i$番目の要素$b_{i}\ (0 \leq b_{i} \leq 1,000,000,000)$が整数で与えられる。続く$M$行に、操作を示す情報$op_{i}$が与えられる。各$op_{i}$は以下のいずれかの形式で与えられる。
$0 \ x \ y \ z$
または
$1 \ p \ q$
最初の文字が$0$の場合、操作$copy(x,y,z)$を行うことを示す。ただし、$1 \leq x,y \leq N,1 \leq z,max(x,y) + z-1 \leq N$ である。
$max(x,y)$ は $x,y$ のうち大きい方を表す。最初の文字が1の場合、操作$sum(p,q)$を行うことを示す。ただし、$1 \leq p \leq q \leq N$ である。入力には、操作$sum$が1回以上与えられる。
出力
操作$sum$が与えられるごとに、操作$sum$の結果を1行に出力する。
入出力例
入力例1
5 5 1 3 5 7 9 2 4 6 8 10 1 1 3 1 4 5 0 4 1 2 1 1 3 1 4 5
出力例1
9 16 9 6
入力例2
6 5 1 2 3 4 5 6 2 4 8 16 32 64 1 1 6 0 1 4 3 1 1 6 0 3 1 3 1 1 6
出力例2
21 127 68