[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$。

输出格式

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

输入输出样例 #1

输入 #1

5 3
1 2 3 4 5
3 4
1 2
5 2

输出 #1

4
3
2

输入输出样例 #2

输入 #2

8 5
8 1 4 2 5 4 2 3
7 4
8 4
4 1
5 8
8 4

输出 #2

4
4
4
7
7

说明/提示

样例一解释：

第一次查询后，$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$：无额外限制。