P6717 [CCO 2018] Boring Lectures

There is a sequence of length $N$, where the $i$-th number is $a_i$. There are $Q$ modifications. In the $j$-th modification, the number at position $i_j$ is changed to $x_j$. You need to find, for the initial sequence and after each modification, the maximum possible value of the sum of the largest and second largest elements among all consecutive subarrays of length $K$.

The first line contains three integers $N, K, Q$, as described above. The second line contains $N$ integers $a_i$, the sequence. The next $Q$ lines each contain two integers $i_j, x_j$, representing one modification.

Output $Q+1$ lines. The $j$-th line represents the answer after the $(j-1)$-th modification. The first line represents the answer before any modifications.

#### Sample Explanation For Sample $1$. - Before any modification, we choose $[1,3]$, and the sum is $6+2=8$. - After the first modification, we choose $[2,4]$, and the sum is $2+4=6$. #### Constraints For $100\%$ of the testdata, $2 \le N \le 10^6$, $2 \le K \le N$, $0 \le Q \le 10^5$, $0 \le a_i \le 10^9$, $1 \le i_j \le N$, $0 \le x_j \le 10^9$. For $20\%$ of the testdata, $Q=0$. For another $40\%$ of the testdata, $N \le 10^4$. #### Notes Translated from [Canadian Computing Olympiad 2018](https://cemc.math.uwaterloo.ca/contests/computing/2018/) Day 2 [B Boring Lectures](https://cemc.math.uwaterloo.ca/contests/computing/2018/stage%202/day2.pdf)。 Translated by ChatGPT 5