#P6717. [CCO2018] Boring Lectures

[CCO2018] Boring Lectures

题目描述

有一个长为 NN 的数列,第 ii 个数为 aia_i

QQ 次修改,第 jj 次会将第 iji_j 个数改成 xjx_j

您需要求出在最初和每次修改之后连续的的 KK 个元素中,最大值与次大值的和最大是多少。

输入格式

第一行三个整数 N,K,QN,K,Q 见题目描述。
第二行 NN 个整数 aia_i 为这个序列。
接下来 QQ 行每行两个整数 ij,xji_j,x_j 代表一次更改。

输出格式

Q+1Q+1 行第 jj 行代表第 j1j-1 次修改后得到的答案,第一行就代表未修改前得到的答案。

4 3 1
6 1 2 4
1 3
8
6

提示

样例说明

对于样例 11

  • 还未修改时,我们选定 [1,3][1,3],得到的和为 6+2=86+2=8
  • 进行第一次修改时,我们选定 [2,4][2,4],得到的和为 2+4=62+4=6

数据规模与约定

对于 100%100\% 的数据,2N1062 \le N \le 10^62KN2 \le K \le N0Q1050 \le Q \le 10^50ai1090 \le a_i \le 10^91ijN1 \le i_j \le N0xj1090 \le x_j \le 10^9
对于 20%20\% 的数据,Q=0Q=0
对于另外 40%40\% 的数据,N104N \le 10^4

说明

翻译自 Canadian Computing Olympiad 2018 Day 2 B Boring Lectures