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