P12029 [USACO25OPEN] Election Queries G

**注意：本题时间限制为 3 秒，是默认时间的 1.5 倍。** 农夫约翰有 $N$ 头（$2 \leq N \leq 2 \cdot 10^5$）编号从 $1$ 到 $N$ 的奶牛。农场正在举行选举，将选出两头新的领头牛。初始时，已知第 $i$ 头奶牛会投票给第 $a_i$ 头奶牛（$1 \leq a_i \leq N$）。 选举过程如下： 1. 农夫约翰任意选择一个非空真子集 $S$（即至少包含一头牛但不包含所有牛）。 2. 让集合 $S$ 中的奶牛进行投票，将得票数最多的奶牛选为第一头领头牛 $x$（如果出现平票，可以在得票最多的奶牛中任意选择一个）。 3. 让其余奶牛进行投票，用同样的方式选出第二头领头牛 $y$。 4. 定义两头领头牛的差异度为 $|x - y|$。若无法选出两头不同的领头牛，则差异度为 $0$。 由于奶牛们经常改变主意，农夫约翰需要进行 $Q$ 次（$1 \leq Q \leq 10^5$）查询。每次查询会修改一头奶牛的投票对象，你需要回答当前状态下可能获得的最大差异度。

第一行包含 $N$ 和 $Q$。 第二行包含初始投票数组 $a_1, a_2, \ldots, a_N$。 接下来 $Q$ 行，每行两个整数 $i$ 和 $x$，表示将 $a_i$ 修改为 $x$。（$1 \le i, x \le N$）

输出 $Q$ 行，第 $i$ 行表示前 $i$ 次查询后的最大可能差异度。

#### 样例一解释： 第一次查询后，$a = [1,2,4,4,5]$。选择 $S = \{1,3\}$ 时： - $S$ 中：牛 $1$ 得 $1$ 票，牛 $4$ 得 $1$ 票 $\to$ 可选择牛 $1$ 或牛 $4$ 作为第一头领头牛。 - 剩余牛中：牛 $2,4,5$ 各得 $1$ 票 $\to$ 可选择牛 $2,4,5$ 作为第二头领头牛。 最大差异度为 $|1-5| = 4$。 第二次查询后，$a = [2,2,4,4,5]$。选择 $S = \{4,5\}$ 时： - $S$ 中：牛 $4$ 得 $1$ 票，牛 $5$ 得 $1$ 票。 - 剩余牛中：牛 $2$ 得 $2$ 票。 最大差异度为 $|5-2| = 3$。 #### 测试点性质： - 测试点 $3\sim4$：$N,Q \leq 100$。 - 测试点 $5\sim7$：$N,Q \leq 3000$。 - 测试点 $8\sim15$：无额外限制。