#PU1522. USACO 2025 US Open Contest, Gold — Problem 2. Election Queries
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 () cows numbered from to . 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 will vote for cow (). To determine the two head cows, FJ will hold his election in the following process: Choose an arbitrary subset of his cows that contains at least one cow but not all cows. FJ is able to choose cow as the first head cow if its votes appear most frequently among all votes cast by cows in . FJ is able to choose cow as the second head cow if its votes appear most frequently among votes cast by cows not in . For a fixed subset , FJ denotes the diversity between his head cows as . As FJ does not like having leaders with similar numbers, he wants to choose such that the diversity is maximized. Note that if FJ is not able to choose two distinct head cows, then the diversity is . However, some cows keep changing their minds, and FJ may have to rerun the election many times! Therefore, he asks you () 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 and . The following line contains . The following lines contain two integers and , representing the update ().
输出格式
(见题面原文)
数据范围
Inputs 3-4: Inputs 5-7: 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