F - Up-Down Queries Editorial /

Time Limit: 5 sec / Memory Limit: 1024 MB

配点 : 1100 点

問題文

各要素が 0 以上 M 以下で長さが N の整数列 x=(x_1,x_2,\cdots,x_N) に対し，f(x) を次のように定義します．

  • 長さ M の整数列 y=(y_1,y_2,\cdots,y_M) を用意する． 最初，y の要素はすべて 0 にする． その後，各 i=1,2,\cdots,N に対しこの順に以下の操作を行う．
    • 各整数 j (1 \leq j \leq x_i) に対し，y_j の値を \max(y_j-1,0) で置き換える．
    • 各整数 j (x_i < j \leq M) に対し，y_j の値を y_j+1 で置き換える．
  • すべての操作が終わった時点での y の要素の総和を f(x) の値とする．

各要素が 0 以上 M 以下で長さが N の整数列 A=(A_1,A_2,\cdots,A_N) が与えられます． Q 個のクエリを処理してください．

  • i 番目のクエリ: 整数 X_i,Y_i が与えられるので，A_{X_i} の値を Y_i で置き換える． その後，f(A) の値を出力する．

制約

  • 1 \leq N,M,Q \leq 250000
  • 0 \leq A_i \leq M
  • 1 \leq X_i \leq N
  • 0 \leq Y_i \leq M
  • 入力される値はすべて整数．

入力

入力は以下の形式で標準入力から与えられる．

N M Q
A_1 A_2 \cdots A_N
X_1 Y_1
X_2 Y_2
\vdots
X_Q Y_Q

出力

答えを出力せよ．

入力例 1

3 4 2
1 2 3
1 4
3 0

出力例 1

2
6

まず 1 番目のクエリを考えます． A_1 の値を 4 で置き換え，A=(4,2,3) になります． そして，f(A) の値は次のように求まります．

  • y=(0,0,0,0) を用意する．
  • A_1=4 について操作を行い，y=(0,0,0,0) になる．
  • A_2=2 について操作を行い，y=(0,0,1,1) になる．
  • A_3=3 について操作を行い，y=(0,0,0,2) になる．
  • y の要素の総和 =2 が f(A) の値となる．

次に 2 番目のクエリを考えます． A_3 の値を 0 で置き換え，A=(4,2,0) になります． そして，f(A) の値は次のように求まります．

  • y=(0,0,0,0) を用意する．
  • A_1=4 について操作を行い，y=(0,0,0,0) になる．
  • A_2=2 について操作を行い，y=(0,0,1,1) になる．
  • A_3=0 について操作を行い，y=(1,1,2,2) になる．
  • y の要素の総和 =6 が f(A) の値となる．

入力例 2

7 2 9
2 0 2 2 0 1 0
1 1
3 0
4 0
4 1
6 1
3 2
2 0
3 2
2 0

出力例 2

4
7
11
9
9
6
6
6
6

入力例 3

20 200000 10
39664 143179 193565 153887 16141 91985 51452 155409 116777 190060 87620 64458 106481 51272 9108 100995 139248 18243 181424 6182
4 196305
13 59753
8 96194
6 57037
19 125781
16 142779
15 13967
10 17772
16 84763
12 17283

出力例 3

1145670
1234421
1352851
1352851
1464137
1380569
1380569
1608611
1724643
1736769

Score : 1100 points

Problem Statement

For an integer sequence x=(x_1,x_2,\cdots,x_N) of length N with each element being between 0 and M, inclusive, we define f(x) as follows:

  • Prepare an integer sequence y=(y_1,y_2,\cdots,y_M) of length M. Initially, set all elements of y to 0. Then, for each i=1,2,\cdots,N, in order, perform the following operations:
    • For each integer j (1 \leq j \leq x_i), replace the value of y_j with \max(y_j-1,0).
    • For each integer j (x_i < j \leq M), replace the value of y_j with y_j+1.
  • The sum of the elements of y after all operations is the value of f(x).

You are given an integer sequence A=(A_1,A_2,\cdots,A_N) of length N with each element being between 0 and M, inclusive. Process Q queries:

  • The i-th query: Given integers X_i and Y_i, replace the value of A_{X_i} with Y_i. Then, print the value of f(A).

Constraints

  • 1 \leq N,M,Q \leq 250000
  • 0 \leq A_i \leq M
  • 1 \leq X_i \leq N
  • 0 \leq Y_i \leq M
  • All input values are integers.

Input

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

N M Q
A_1 A_2 \cdots A_N
X_1 Y_1
X_2 Y_2
\vdots
X_Q Y_Q

Output

Print the answer.

Sample Input 1

3 4 2
1 2 3
1 4
3 0

Sample Output 1

2
6

Consider the first query. We replace the value of A_1 with 4, making A=(4,2,3). Then, the value of f(A) is calculated as follows:

  • Prepare y=(0,0,0,0).
  • Perform the operation for A_1=4, resulting in y=(0,0,0,0).
  • Perform the operation for A_2=2, resulting in y=(0,0,1,1).
  • Perform the operation for A_3=3, resulting in y=(0,0,0,2).
  • The sum of the elements of y, which equals 2, is the value of f(A).

Next, consider the second query. We replace the value of A_3 with 0, making A=(4,2,0). Then, the value of f(A) is calculated as follows:

  • Prepare y=(0,0,0,0).
  • Perform the operation for A_1=4, resulting in y=(0,0,0,0).
  • Perform the operation for A_2=2, resulting in y=(0,0,1,1).
  • Perform the operation for A_3=0, resulting in y=(1,1,2,2).
  • The sum of the elements of y, which equals 6, is the value of f(A).

Sample Input 2

7 2 9
2 0 2 2 0 1 0
1 1
3 0
4 0
4 1
6 1
3 2
2 0
3 2
2 0

Sample Output 2

4
7
11
9
9
6
6
6
6

Sample Input 3

20 200000 10
39664 143179 193565 153887 16141 91985 51452 155409 116777 190060 87620 64458 106481 51272 9108 100995 139248 18243 181424 6182
4 196305
13 59753
8 96194
6 57037
19 125781
16 142779
15 13967
10 17772
16 84763
12 17283

Sample Output 3

1145670
1234421
1352851
1352851
1464137
1380569
1380569
1608611
1724643
1736769