P2710 Sequence

Maintain a sequence with a total of $7$ operations: I. `INSERT x n a1 a2 .. an` Insert $n$ numbers $a_1 \dots a_n$ after the $x$-th number. II. `DELETE x n` Delete $n$ numbers starting from the $x$-th number. III. `REVERSE x n` Reverse the interval of $n$ numbers starting from the $x$-th number. IV. `MAKE-SAME x n t` Set the $n$ numbers starting from the $x$-th number all to $t$. V. `GET-SUM x n` Output the sum of the $n$ numbers starting from the $x$-th number. VI. `GET x` Output the value of the $x$-th number. VII. `MAX-SUM x n` Output the maximum subarray sum within the $n$ numbers starting from the $x$-th number.

The first line contains $N$, $M$, where $N$ is the number of elements in the initial sequence, and $M$ is the number of operations. The second line contains $N$ numbers $A_1 \dots A_N$, representing the initial sequence. From the third line to line $M+2$, each line contains one operation.

Output the result of each `GET-SUM`, `GET`, and `MAX-SUM` operation.

There are $20$ groups of testdata, each randomly generated. It is guaranteed that at any time the sequence contains at most $200000$ numbers. Every input integer is in $[-1000, 1000]$, and any result does not exceed $2^{30}$. Groups 1–2: $1 \le N \le 5$, $1 \le M \le 10$. Groups 3–4: $1 \le N \le 10$, $1 \le M \le 20$. Groups 5–6: $1 \le N \le 20$, $1 \le M \le 50$. Groups 7–8: $1 \le N \le 50$, $1 \le M \le 100$. Groups 9–10: $1 \le N \le 100$, $1 \le M \le 500$. Groups 11–12: $1 \le N \le 1000$, $1 \le M \le 1000$. Groups 13–14: $1 \le N \le 5000$, $1 \le M \le 2000$. Groups 15–16: $1 \le N \le 10^4$, $1 \le M \le 5000$. Groups 17–18: $1 \le N \le 10^5$, $1 \le M \le 10^4$. Groups 19–20: $1 \le N \le 2 \times 10^5$, $1 \le M \le 2 \times 10^4$. Translated by ChatGPT 5