P14378 【MX-S9-T1】「LAOI-16」签到

> 有个地方真实存在，有着复眼能看到的色彩。 > > 在人们无数次沉没里，怎么还有条船不远万里。

给定一个长度为 $n$ 的非负整数序列 $A_1, \ldots, A_n$ 以及两个长度为 $k$ 的正整数序列 $B_1, \ldots, B_k$ 和非负整数序列 $C_1, \ldots, C_k$。 你使用的 sʍopuᴉʍ 系统的画图软件有 $k$ 种颜色 $1\sim k$。你需要为 $n$ 个元素都涂上一种颜色，使得颜色 $i$ 的出现次数恰好为 $B_i$。 对于涂上了第 $i$ 种颜色的元素，值同时加上 $C_i$。 经过上述操作后会得到新的序列 $A'$，你想知道序列 $A'$ 可能的最小极差是多少（极差的定义为整个序列的最大值减去最小值的值）。 这实在太困难了，所以你的 sʍopuᴉʍ 系统共 $Q$ 次发生 UB 错误，把你的序列 $A$ 改掉了！第 $i$ 次会把 $A_{x_i}$ 改为 $v_i$。在你解决完问题后你会发现序列被修改了，所以你按下了 Ctrl+Z 撤销这次修改。 但是这很有趣！你需要把每次修改后的答案输出。

第一行，三个正整数 $n,k,q$，含义见题目描述。 第二行，$n$ 个非负整数 $A_1, \ldots, A_n$。 第三行，$k$ 个正整数 $B_1, \ldots, B_k$。 第四行，$k$ 个非负整数 $C_1, \ldots, C_k$。 接下来 $q$ 行，每行两个整数 $x_i, v_i$，表示将 $A_{x_i}$ 改为 $v_i$。修改之间独立。

共 $q$ 行，每行一个非负整数，表示修改后可能的最小极差。

**【样例解释 #1】** - 第一次修改后序列为：$\langle 8,4,4,8,5\rangle$，可行的操作是 $\langle 8{\color{red}{{}+4}},4{\color{red}{{}+6}},4{\color{red}{{}+6}},8{\color{red}{{}+4}},5{\color{red}{{}+5}}\rangle$，最小极差为 $8{\color{red}{{}+4}}-(5{\color{red}{{}+5}})=2$。 - 第二次修改后序列为：$\langle 8,4,4,3,5\rangle$，可行的操作是 $\langle 8{\color{red}{{}+4}},4{\color{red}{{}+6}},4{\color{red}{{}+5}},3{\color{red}{{}+6}},5{\color{red}{{}+4}}\rangle$，最小极差为 $8{\color{red}{{}+4}}-(3{\color{red}{{}+6}})=3$。 - 第三次修改后序列为：$\langle 8,4,4,5,5\rangle$，可行的操作是 $\langle 8{\color{red}{{}+4}},4{\color{red}{{}+6}},4{\color{red}{{}+5}},5{\color{red}{{}+4}},5{\color{red}{{}+6}}\rangle$，最小极差为 $8{\color{red}{{}+4}}-(4{\color{red}{{}+5}})=3$。 - 第四次修改后序列为：$\langle 8,4,4,4,8\rangle$，可行的操作是 $\langle 8{\color{red}{{}+4}},4{\color{red}{{}+6}},4{\color{red}{{}+6}},4{\color{red}{{}+5}},8{\color{red}{{}+4}}\rangle$，最小极差为 $8{\color{red}{{}+4}}-(4{\color{red}{{}+5}})=3$。 - 第五次修改后序列为：$\langle 2,4,4,4,5\rangle$，可行的操作是 $\langle 2{\color{red}{{}+6}},4{\color{red}{{}+6}},4{\color{red}{{}+5}},4{\color{red}{{}+4}},5{\color{red}{{}+4}}\rangle$，最小极差为 $4{\color{red}{{}+6}}-(2{\color{red}{{}+6}})=2$。 **【样例 #2】** 见选手目录下的 $\textbf{\textit{register/register2.in}}$ 与 $\textbf{\textit{register/register2.ans}}$。 该样例满足测试点 $1$ 的约束条件。 **【样例 #3】** 见选手目录下的 $\textbf{\textit{register/register3.in}}$ 与 $\textbf{\textit{register/register3.ans}}$。 该样例满足测试点 $2\sim 5$ 的约束条件。 **【样例 #4】** 见选手目录下的 $\textbf{\textit{register/register4.in}}$ 与 $\textbf{\textit{register/register4.ans}}$。 该样例满足测试点 $6\sim 8$ 的约束条件。 **【样例 #5】** 见选手目录下的 $\textbf{\textit{register/register5.in}}$ 与 $\textbf{\textit{register/register5.ans}}$。 该样例满足测试点 $9\sim 11$ 的约束条件。 **【样例 #6】** 见选手目录下的 $\textbf{\textit{register/register6.in}}$ 与 $\textbf{\textit{register/register6.ans}}$。 该样例满足测试点 $12\sim 20$ 的约束条件。 **【数据范围】** 本题共 $20$ 个测试点，每个 $5$ 分。 对于所有测试数据，保证： - $1\le k\le n\le 5\times 10^5$，$1\le q\le 5\times 10^5$； - $1\le x_i\le n$； - $0\le A_i,C_i,v_i \le 5\times 10^5$； - $1\le B_i\le 5\times 10^5$； - $\sum B_i=n$。 ::cute-table{tuack} |测试点编号|$n,k,q \le$|特殊性质| |:--:|:--:|:--:| |$1$|$8$|A| |$2\sim 5$|$2\times 10^3$|无| |$6\sim 8$|$5\times 10^5$|B| |$9\sim 11$|^|C| |$12\sim 20$|^|无| 特殊性质 A：$A_i,C_i,v_i\le 8$。 特殊性质 B：$k=2$。 特殊性质 C：$C_i\le 1$。