Election Queries

题目描述

注意：本题时间限制为 3s，为默认的 1.5 倍。 农夫约翰有 $N$（$2 \leq N \leq 2 \cdot 10^5$）头奶牛，编号从 $1$ 到 $N$。农场将举行一次选举来选出两头新的首领奶牛。最初已知奶牛 $i$ 会投票给奶牛 $a_i$（$1 \leq a_i \leq N$）。 为了决定这两头首领奶牛，FJ 将按如下流程进行选举： 选择一个任意的奶牛子集 $S$，要求 $S$ 至少包含一头奶牛，但不能包含所有奶牛。如果奶牛 $x$ 在 $S$ 中所有奶牛投出的票里出现次数最多，那么 FJ 可以选择奶牛 $x$ 作为第一头首领奶牛。 如果奶牛 $y$ 在不属于 $S$ 的奶牛所投出的票里出现次数最多，那么 FJ 可以选择奶牛 $y$ 作为第二头首领奶牛。 对于固定的子集 $S$，FJ 定义两头首领奶牛之间的多样性（diversity）为 $|x - y|$。由于 FJ 不喜欢编号相近的领袖，他希望选择 $S$ 使得多样性最大。注意，如果 FJ 无法选出两头不同的首领奶牛，则多样性为 $0$。 然而，有些奶牛会不断改变主意，FJ 可能需要多次重新进行选举！因此，他会向你提出 $Q$（$1 \leq Q \leq 10^5$）个询问。每个询问中，有一头奶牛会改变自己的投票。在每次询问之后，他会问你在新的首领奶牛中，可能得到的最大多样性是多少。

输入格式

第一行包含 $N$ 和 $Q$。 第二行包含 $a_1, a_2, \ldots, a_N$。 接下来的 $Q$ 行每行包含两个整数 $i$ 和 $x$，表示更新 $a_i = x$（$1 \leq i, x \leq N$）。

输出格式

输出 $Q$ 行，其中第 $i$ 行为进行前 $i$ 次询问后可能得到的最大多样性。

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

4
3
2

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

4
4
4
7
7

提示

第一次询问后，$a = [1, 2, 4, 4, 5]$。在选举的第一步，FJ 可以令 $S = \{1, 3\}$。此时，奶牛 $1$ 得到一票，奶牛 $4$ 得到一票。因此，FJ 可以选择奶牛 $1$ 或奶牛 $4$ 作为第一头首领奶牛。 对于不在选举中的奶牛，奶牛 $2$ 得到一票，奶牛 $4$ 得到一票，奶牛 $5$ 也得到一票。因此，FJ 可以从奶牛 $2$、$4$ 或 $5$ 中任意选择一头作为第二头首领奶牛。 为了获得最大的多样性，FJ 可以选择奶牛 $1$ 作为第一头首领奶牛，奶牛 $5$ 作为第二头首领奶牛。因此，多样性为 $|1-5| = 4$。 第二次询问后，$a=[2,2,4,4,5]$，FJ 可以令 $S = \{4, 5\}$。那么，他可以选择 $5$ 作为第一头首领奶牛，选择奶牛 $2$ 作为第二头首领奶牛。最大可能的多样性为 $|5 - 2| = 3$。 SCORING: 输入 3-4：$N, Q \leq 100$ 输入 5-7：$N, Q \leq 3000$ 输入 8-15：无额外限制。 题目致谢：Chongtian Ma 和 Haokai Ma

标签: USACO|2025|Gold

来源

USACO|2025|Gold