P4756 Added Sequence

　　

Xiao $L$ invented a new data structure and named it the $L$ array. An $L$ array can add or subtract a number to the entire array in $O(1)$ time. Now you are given an array $a$ of length $N$. He wants to use the $L$ array to challenge your computing ability. Define $f(i,j)=|\sum_{p=i}^{j} a_p|$, where $|x|$ denotes the absolute value of $x$. Define the beauty of an array as $\max_{1 \le i \le j \le N} f(i,j)$. Each time he adds $x$ to the entire array, you need to answer the beauty at that moment. Note that your algorithm must be online.

The first line contains two integers $N,M$, representing the array length and the number of queries. The second line contains $N$ integers, representing the initial array $a$. The next $M$ lines each contain one integer $x_i$. Let the previous answer be $pre$. Then for the $i$-th query, it means adding $[(x_i+pre)\%(4n+1)-2n]$ to the entire array based on the initial array. Here $\%$ denotes the modulo operation. For the first answer, $pre=0$.

Output $M$ lines. The $i$-th line is the beauty of the array after adding $x_i$ to the entire array based on the initial array.

The four added numbers are $-7$, $-4$, $-2$, and $1$. Constraints: $1 \le N,M \le 200000$. $|a_i| \le 200000$. $0 \le x_i \le 800000$. Translated by ChatGPT 5