[Ynoi2009] pmrllcsrms
题目描述
给你一个长度为 $n$ 的整数序列 $a$,和一个常数 $c$ 。
有 $m$ 次操作:
`1 x y`:将位置 $x$ 的值修改为 $y$。
`2 l r`:表示询问区间 $[l,r]$ 中 $\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)$。
输入输出格式
输入格式
第一行三个正整数 $n,m,c$ ,分别表示序列长度,操作次数,以及给定的常数。
之后一行 $n$ 个整数 $a_1,\dots,a_n$ 表示序列 $a$ 。
之后 $m$ 行,每行三个数表示一次操作,意义如上述。
输出格式
对每个询问,输出一行一个数表示答案。
输入输出样例
输入样例 #1
5 10 2
0 -5 -3 8 -3
1 5 -1
1 2 3
1 5 -6
1 2 9
2 5 5
2 3 3
1 1 -3
2 4 4
1 1 4
1 3 3
输出样例 #1
0
0
8
说明
Idea:chenkuowen&nzhtl1477,Solution:ccz181078,Code:ccz181078,Data:ccz181078
对于 $100\%$ 的数据,$1 \le n, m\le 10^6, 1\le x,c\le n, 1\le l\le r\le n, -10^9 \le a_i,y \le 10^9$ 。