P6780 [Ynoi2009] pmrllcsrms

You are given an integer sequence $a$ of length $n$, and a constant $c$. There are $m$ operations: `1 x y`: Modify the value at position $x$ to $y$. `2 l r`: Query $\max\left(\max_{l \leq l' \leq r' \leq r\atop r'-l'+1\leq c} ~~ \left(\sum_{i=l'} ^{r'} a_i\right), 0\right)$ within the interval $[l,r]$.

The first line contains three positive integers $n, m, c$, representing the length of the sequence, the number of operations, and the given constant. The next line contains $n$ integers $a_1,\dots,a_n$, representing the sequence $a$. Then follow $m$ lines, each containing three numbers describing one operation, with the meaning as stated above.

For each query, output one line with one number representing the answer.

Idea: chenkuowen&nzhtl1477, Solution: ccz181078, Code: ccz181078, Data: ccz181078. For $100\%$ of the testdata, $1 \le n\le 10^6$, $1\le m\le 2\times10^6$, $1\le x,c\le n$, $1\le l\le r\le n$, $-10^9 \le a_i,y \le 10^9$. Translated by ChatGPT 5