N - Maximum Subarray Sum Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

問題文

長さ N の整数列 A = (A_1, A_2, \ldots, A_N) および整数 K が与えられます。

以下の形式のクエリが Q 個与えられるので、順に処理してください。

  • 整数 i, x が与えられる。A_i の値を x に変更する。その後、A の長さ K の連続部分列の値の和の最大値を求める。

制約

  • 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 番目のクエリでは、まず A_6 の値を 2 に変更するため、A = (2, 3, 1, 1, 7, 2) となります。A の長さ 4 の連続部分列の値の和の最大値は 3 + 1 + 1 + 7 = 12 です。

  • 2 番目のクエリでは、まず A_5 の値を 2 に変更するため、A = (2, 3, 1, 1, 2, 2) となります。A の長さ 4 の連続部分列の値の和の最大値は 2 + 3 + 1 + 1 = 7 です。

  • 3 番目のクエリでは、まず A_4 の値を 5 に変更するため、A = (2, 3, 1, 5, 2, 2) となります。A の長さ 4 の連続部分列の値の和の最大値は 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

Problem Statement

You are given an integer sequence A = (A_1, A_2, \ldots, A_N) of length N, and an integer K.

Process the given Q queries in the following format in order.

  • Given integers i and x, set A_i to x, and find the maximum sum of the values in a length-K (contiguous) subarray of A.

Constraints

  • 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
  • For each query, 1 \leq i \leq N
  • For each query, 1 \leq x \leq 10^9
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N K
A_1 A_2 \ldots A_N
Q
\text{query}_{1}
\vdots
\text{query}_{Q}

Here, \text{query}_{i} denotes the i-th query, given in the following format:

i x

Output

Print Q lines. The i-th line should contain the answer to the i-th query.

Sample Input 1

6 4
2 3 1 1 7 4
3
6 2
5 2
4 5

Sample Output 1

12
7
11

Initially, A = (2, 3, 1, 1, 7, 4).

  • For the 1-st query, first set A_6 to 2, making A = (2, 3, 1, 1, 7, 2). Then, the maximum sum of the elements in a length-4 subarray of A is 3 + 1 + 1 + 7 = 12.
  • For the 2-st query, first set A_5 to 2, making A = (2, 3, 1, 1, 2, 2). Then, the maximum sum of the elements in a length-4 subarray of A is 2 + 3 + 1 + 1 = 7.
  • For the 3-st query, first set A_4 to 5, making A = (2, 3, 1, 5, 2, 2). Then, the maximum sum of the elements in a length-4 subarray of A is 3 + 1 + 5 + 2 = 11.

Sample Input 2

7 2
1 7 2 6 3 5 4
5
7 7
1 100
3 1000
5 10000
2 100000

Sample Output 2

12
107
1007
10006
101000