#PU1522. USACO 2025 US Open Contest, Gold — Problem 2. Election Queries

    ID: 1676 传统题 3000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:open25来源:usaco.orgscoring:equal_test_cases线段树平衡树枚举

USACO 2025 US Open Contest, Gold — Problem 2. Election Queries

USACO 2025 US Open Contest, Gold — Problem 2. Election Queries

题目描述

Note: The time limit for this problem is 3s, 1.5x the default. Farmer John has NN (2≤N≤2⋅1052 \leq N \leq 2 \cdot 10^5) cows numbered from 11 to NN. An election is being held in FJ's farm to determine the two new head cows in his farm. Initially, it is known that cow ii will vote for cow aia_i (1≤ai≤N1 \leq a_i \leq N). To determine the two head cows, FJ will hold his election in the following process: Choose an arbitrary subset SS of his cows that contains at least one cow but not all cows. FJ is able to choose cow xx as the first head cow if its votes appear most frequently among all votes cast by cows in SS. FJ is able to choose cow yy as the second head cow if its votes appear most frequently among votes cast by cows not in SS. For a fixed subset SS, FJ denotes the diversity between his head cows as ∣x−y∣|x - y|. As FJ does not like having leaders with similar numbers, he wants to choose SS such that the diversity is maximized. Note that if FJ is not able to choose two distinct head cows, then the diversity is 00. However, some cows keep changing their minds, and FJ may have to rerun the election many times! Therefore, he asks you QQ (1≤Q≤1051 \leq Q \leq 10^5) queries. In each query, a cow changes their vote. After each query, he asks you for the maximum possible diversity among his new head cows.

输入格式

The first line contains NN and QQ. The following line contains a1,a2,…,aNa_1, a_2, \ldots, a_N. The following QQ lines contain two integers ii and xx, representing the update ai=xa_i = x (1≤i,x≤N1 \leq i, x \leq N).

输出格式

(见题面原文)

数据范围

Inputs 3-4: N,Q≤100N, Q \leq 100 Inputs 5-7: N,Q≤3000N, Q \leq 3000 Inputs 8-15: No additional constraints. Problem credits: Chongtian Ma and Haokai Ma

样例

样例 1

5 3
1 2 3 4 5
3 4
1 2
5 2
4
3
2
After the first query, $a = [1, 2, 4, 4, 5]$. At the first step of the election,
FJ can make $S = \{1, 3\}$. Here, cow $1$ receives one vote and cow $4$ receives
one vote.  Therefore, FJ can choose either cow $1$ or cow $4$ as its first head
cow.
For all cows not in the election, cow $2$ receives one vote, cow $4$ receives
one vote, and cow $5$ also receives one vote. Therefore, FJ can choose any one
of cows $2$, $4$, or $5$ to be its second head cow.
To obtain the maximum diversity, FJ can choose cow $1$ as the first head cow and
cow $5$ as the second head cow. Therefore, the diversity is $|1-5| = 4$.
After the second query, $a=[2,2,4,4,5]$ and FJ can make $S = \{4, 5\}$. Then, he
can choose $5$ as the first head cow and cow $2$ as the second head cow. The
maximum possible diversity is
$|5 - 2| = 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