问题陈述
给你一个整数序列 A = (A_1, A_2, \ldots, A_N) 长度 N,和一个整数 K.
处理给定的 Q 按以下格式按顺序查询。
- 给定整数 i 和 x,设置 A_i to x,并找到长度中值的最大总和K (连续)子数组 A.
约束
- 1 \leq K \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq Q \leq 2 \times 10^5
- 对于每个查询, 1 \leq i \leq N
- 对于每个查询, 1 \leq x \leq 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N K
A_1 A_2 \ldots A_N
Q
\text{query}_{1}
\vdots
\text{query}_{Q}
在这里, \text{query}_{i} 表示 i-第一个查询,按以下格式给出:
i x
输出
打印 Q 行。 的 i- 第行应包含以下问题的答案 i-第一个查询。
示例输入 1
6 4 2 3 1 1 7 4 3 6 2 5 2 4 5
示例输出 1
12 7 11
最初, A = (2, 3, 1, 1, 7, 4).
- 对于 1-st 查询,第一组 A_6 to 2, 制作 A = (2, 3, 1, 1, 7, 2)。然后,长度中元素的最大和4 的子数组 A is 3 + 1 + 1 + 7 = 12.
- 对于 2-st 查询,第一组 A_5 to 2, 制作 A = (2, 3, 1, 1, 2, 2)。然后,长度中元素的最大和4 的子数组 A is 2 + 3 + 1 + 1 = 7.
- 对于 3-st 查询,第一组 A_4 to 5, 制作 A = (2, 3, 1, 5, 2, 2)。然后,长度中元素的最大和4 的子数组 A is 3 + 1 + 5 + 2 = 11.
示例输入 2
7 2 1 7 2 6 3 5 4 5 7 7 1 100 3 1000 5 10000 2 100000
示例输出 2
12 107 1007 10006 101000