P8659 [Lanqiao Cup 2017 National A] Array Operations

Given an array $\{A\}$ of length $n$, indexed from $1$ to $n$, you need to maintain $m$ operations. There are three types of operations, with input formats as follows: `1 L R d`: Add $d$ to all positions in the array with indices from $L$ to $R$. That is, for $L \le i \le R$, perform $A[i]\leftarrow A[i]+d$. `2 L1 R1 L2 R2`: Assign the values of positions $L_2$ to $R_2$ to positions $L_1$ to $R_1$. It is guaranteed that $R_1-L_1=R_2-L_2$. In other words, first perform $B_i\leftarrow A_{L_2+i}$ for $0 \le i \le R_2-L_2$, then perform $A_{L_1+i}\leftarrow B_i$ for $0 \le i \le R_1-L_1$, where $\{B\}$ is a temporary array. `3 L R`: Query the sum of positions in the array with indices from $L$ to $R$, i.e., compute $\sum\limits_{i=L}^{r}A_i$.

Read input from standard input. The first line contains an integer Case, indicating the test point ID. When Case is $0$, it means this test point is the sample. The second line contains two integers $n,m$. It is guaranteed that $1 \le n,m \le 10^5$. The third line contains $n$ integers $A_i$, representing the initial values of the array. It is guaranteed that $0 \le A_i \le 10^5$. The next $m$ lines each describe an operation, in the format shown in the problem description. For every number mentioned in the operations, it holds that $0 \le d \le 10^5$, $1 \le L \le R \le n$, $1 \le L_1 \le R_1 \le n$, $1 \le L_2 \le R_2 \le n$, and $R_1-L_1=R_2-L_2$.

For each operation of type $3$, output one line with one number, representing the sum result.

|Test point|$n$, $m$|Other constraints| |-----|---|-------| |1, 2|$\le10^3$|None.| |3, 4|$\le10^5$|No operation of type $2$.| |5, 6, 7|$\le10^5$|$n$ is even, and all type $2$ operations satisfy $L_1=1$, $R_1=\lfloor\frac{n}{2}\rfloor$, $L_2=\lfloor\frac{n}{2}\rfloor+1$, $R_2=n$.| |8, 9, 10|$\le10^5$|None.| For $100\%$ of the testdata, $1 \le n \le 10^5$, and $0 \le a_i