레이팅 미적용*참고: 이 문제의 시간 제한은 3초로, 기본값의 1.5배이다.*
농부 존은 \(1\)부터 \(N\)까지 번호가 붙은 \(N\) (\(2 \leq N \leq 2 \cdot 10^5\))마리의 소를 기르고 있다. 농장의 새 대표 소 두 마리를 뽑기 위한 선거가 열린다. 처음에 소 \(i\)는 소 \(a_i\) (\(1 \leq a_i \leq N\))에게 투표할 것으로 알려져 있다.
두 대표 소를 정하기 위해, 농부 존은 다음 과정으로 선거를 진행한다.
- 소들 중 적어도 한 마리를 포함하되 전체는 아닌 임의의 부분집합 \(S\)를 선택한다. \(S\)에 속한 소들이 던진 표 가운데 소 \(x\)에 대한 표가 가장 많이 나타나면, 농부 존은 소 \(x\)를 첫 번째 대표 소로 선택할 수 있다.
- \(S\)에 속하지 않은 소들이 던진 표 가운데 소 \(y\)에 대한 표가 가장 많이 나타나면, 농부 존은 소 \(y\)를 두 번째 대표 소로 선택할 수 있다.
- 고정된 부분집합 \(S\)에 대해, 농부 존은 두 대표 소 사이의 다양성을 \(|x - y|\)로 정의한다. 농부 존은 번호가 비슷한 지도자들을 좋아하지 않으므로, 다양성이 최대가 되도록 \(S\)를 선택하고 싶어 한다. 서로 다른 두 대표 소를 선택할 수 없다면 다양성은 \(0\)이다.
그런데 일부 소들이 계속 마음을 바꾸기 때문에, 농부 존은 선거를 여러 번 다시 치러야 할 수도 있다! 따라서 그는 \(Q\) (\(1 \leq Q \leq 10^5\))개의 쿼리를 묻는다. 각 쿼리에서 한 소가 자신의 표를 바꾼다. 각 쿼리 후, 새로운 대표 소들에 대해 가능한 최대 다양성을 구해야 한다.
Problem credits: Chongtian Ma and Haokai Ma
SCORING
- 입력 3-4: \(N, Q \leq 100\)
- 입력 5-7: \(N, Q \leq 3000\)
- 입력 8-15: 추가 제약 없음.
Problem credits: Chongtian Ma and Haokai Ma
첫째 줄에 \(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 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