← 返回题目列表

AtCoder · past21_n

N. 最大子数组和

中文机器翻译题面 查看原题

问题陈述

给你一个整数序列 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