T429617 「SFOI Round 1」Home II

你可以点击[这里](/problem/T427018)查看本题弱化版。 **本题题面仅供娱乐，请尊重任何一种宗教信仰**。 虔诚的「根式 n 教」信徒小 X 居住在一条无限延伸的一维数轴上，他想要一个家。

在这条数轴上共建有 $n$ 个「原」，即「根式 n 教」的信徒们进行宗教活动「启动」的场所，其坐标分别用 $a_i$ 表示。 每天清晨，小 X 需要从他的家出发，依次前往每一个「原」进行活动。由于每次「启动」需要携带相应的「元素」，而小 X 只能同时携带 $1$ 种「元素」，因此在每次「启动」结束后，他要先从该「原」返回家，找到相应的「元素」，然后才能继续前往下一个「原」进行「启动」。特别的，在最后一次「启动」结束后，小 X 也需要回家。 同时，这条数轴上的任意一个整点处都有一块「神」的宝地，可以用于建造房屋。而每块宝地的售价不同，具体地，坐标为 $l$ 的宝地售价为 $p\times l$，其中 $p$ 为常数。注意，在某些情况下，售价可能为负。 小 X 想要从「神」这里买下一块宝地用来建造他的家。由于他没有很多钱，并且不想走路，他希望每天清晨进行所有「启动」的路程与该宝地的售价之和最小。 特别的，如果有多块符合要求的宝地，小 X 希望他的家的坐标尽可能小。 请告诉小 X 他应当买下的宝地的坐标。 由于「原」的坐标可能会不断更改，因此小 X 会给你 $q$ 次询问。具体的，每次询问他会给定 $2$ 个参数 $x$ 和 $y$，表示将第 $x$ 个「原」的坐标变为 $y$，即 $a_x\leftarrow y$，请你帮助小 X 计算修改后的答案。请注意，每次修改后的 $a_x$ 将会保留，并影响下一次的询问。 --- **【形式化题意】** 给定序列 $\{a_n\}$ 和常数 $p$，试求当 $\displaystyle\sum_{i=1}^n2|x-a_i|+p\times x$ 尽可能小时整数 $x$ 可取的最小值。 另外给出 $q$ 次询问，每次求出修改后的答案，保留修改。

输入共 $q+2$ 行。 第 $1$ 行 $3$ 个整数，分别表示「原」的数量 $n$ 、宝地的售价参数 $p$ 以及询问的次数 $q$。 第 $2$ 行 $n$ 个整数，分别表示「原」的坐标 $a_i$。 接下来，对于每次询问，输入共 $1$ 行 $2$ 个整数，分别表示该次询问的参数 $x$ 和 $y$。

输出共 $q+1$ 行。 第 $1$ 行 $1$ 个整数，表示未修改时的答案。 接下来，对于每次询问，输出共 $1$ 行 $1$ 个整数，表示该次询问的答案。请注意，每次修改后的结果将会保留，并影响下一次的询问。 特别的，若答案的绝对值大于 $10^9$，则输出 $\texttt{No}$。

**【数据范围】** **本题开启捆绑测试**。 对于 $100\%$ 的数据，$1\le n\le2\times10^5$，$0\le |p|,|a_i|\le10^9$，$0\le q\le2\times10^5$，且保证在每次询问时 $a_i$ 均两两不同。 | $\text{Subtask}$ | $n\le$ | $q\le$ | $\text{Note}$ | $\text{Score}$| | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $2$ | $10^3$ | $\text{No}$ | $5$ | | $2$ | $100$ | $10^3$ | $\text{Yes}$ | $5$ | | $3$ | $100$ | $10^3$ | $\text{No}$ | $10$ | | $4$ | $10^3$ | $10^3$ | $\text{Yes}$ | $5$ | | $5$ | $10^3$ | $10^3$ | $\text{No}$ | $10$ | | $6$ | $5\times10^4$ | $10^3$ | $\text{Yes}$ | $5$ | | $7$ | $5\times10^4$ | $10^3$ | $\text{No}$ | $15$ | | $8$ | $2\times10^5$ | $0$ | $\text{No}$ | $10$ | | $9$ | $2\times10^5$ | $2\times10^5$ | $\text{No}$ | $35$ | - $\text{Note}$：保证 $p=0$。