Election Queries
다이아몬드 V의견: 0
*Note: The time limit for this problem is 3s, 1.5x the default.*
Farmer John has \(N\) (\(2 \leq N \leq 2 \cdot 10^5\)) cows numbered from \(1\) to
\(N\). 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 \(i\) will vote for cow \(a_i\)
(\(1 \leq a_i \leq N\)).
To determine the two head cows, FJ will hold his election in the following
process:
- Choose an arbitrary subset \(S\) of his cows that contains at least one cow but not all cows. FJ is able to choose cow \(x\) as the first head cow if its votes appear most frequently among all votes cast by cows in \(S\).
- FJ is able to choose cow \(y\) as the second head cow if its votes appear most frequently among votes cast by cows not in \(S\).
- For a fixed subset \(S\), FJ denotes the ** diversity ** between his head cows as \(|x - y|\). As FJ does not like having leaders with similar numbers, he wants to choose \(S\) such that the ** diversity ** is maximized. Note that if FJ is not able to choose two distinct head cows, then the diversity is \(0\).
However, some cows keep changing their minds, and FJ may have to rerun the
election many times! Therefore, he asks you \(Q\) (\(1 \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.
Problem credits: Chongtian Ma and Haokai Ma
SCORING
- Inputs 3-4: \(N, Q \leq 100\)
- Inputs 5-7: \(N, Q \leq 3000\)
- Inputs 8-15: No additional constraints.
Problem credits: Chongtian Ma and Haokai Ma
The first line contains \(N\) and \(Q\).
The following line contains \(a_1, a_2, \ldots, a_N\).
The following \(Q\) lines contain two integers \(i\) and \(x\), representing the
update \(a_i = x\) (\(1 \leq i, x \leq N\)).
Output \(Q\) lines, the \(i\)'th of which is the maximum possible ** diversity **
after the first \(i\) queries.
5 3
1 2 3 4 5
3 4
1 2
5 24
3
2After 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\).
8 5
8 1 4 2 5 4 2 3
7 4
8 4
4 1
5 8
8 44
4
4
7
7평가 및 의견
Election Queries
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Election Queries