문제
Farmer John의 농장에는 1번부터 N번까지 번호가 매겨진 소들이 있으며, N는 2 이상 200,000 이하입니다. 선거를 통해 농장의 두 명의 새로운 우두머리 소를 결정하려고 합니다. 처음에, 소 i는 소 a_i에게 투표할 예정입니다 (1 ≤ a_i ≤ N).
두 명의 우두머리 소를 결정하는 절차는 다음과 같습니다.
농부 John은 소들 중 일부(전체가 아니며, 적어도 한 마리는 포함되는)를 임의로 선택하여 집합 S를 만듭니다.
집합 S에 속한 소들이 던진 표를 보고, 가장 많이 나온 표를 받은 소를 첫 번째 우두머리 소로 선택할 수 있습니다.
전체 소 중 S에 속하지 않은 소들의 표를 보고, 가장 많이 나온 표를 받은 소를 두 번째 우두머리 소로 선택할 수 있습니다.
단, 두 번 선택된 우두머리 소가 서로 다른 소여야 합니다. (만약 두 우두머리 소가 같다면, 다양도는 0으로 간주합니다.) 두 우두머리 소 x와 y의 다양도는 |x - y|로 정의됩니다. Farmer John은 리더들의 숫자가 너무 비슷하면 마음에 들지 않으므로, 다양도가 최대가 되도록 집합 S를 선택하려 합니다.
이때, 주어진 투표 정보를 바탕으로 다양한 집합 S 중에서 만들어질 수 있는 최대 다양도를 구하는 문제입니다.
입력
첫 번째 줄에 소의 수 N와 정수 Q가 주어집니다.
다음 줄에는 N개의 정수 a_1, a_2, …, a_N가 공백으로 구분되어 주어지며, 이는 소 i가 투표할 대상의 번호를 의미합니다.
이후 Q개의 줄 각각에는 두 정수 i와 x가 주어지며, 이는 소 i가 투표할 대상을 x로 바꾼다는 의미의 업데이트 (a_i = x)를 나타냅니다.
출력
Q개의 줄을 출력합니다. i번째 줄에는 첫 i개의 업데이트 후의 투표 정보를 바탕으로, 위 절차를 통해 선택 가능한 두 우두머리 소의 최대 다양도 (즉, 최대 |x - y|, 단 두 우두머리 소는 서로 달라야 함)를 출력합니다. 만약 두 우두머리 소를 서로 다르게 선택하는 것이 불가능하면 0을 출력합니다.
예제 #1
5 3
1 2 3 4 5
3 4
1 2
5 2
4
3
2
첫 번째 업데이트 후, 투표 정보는 [1, 2, 4, 4, 5]가 됩니다.
예를 들어, S = {1, 3}으로 선택하면,S 안에서는 소 1의 투표 (1)와 소 3의 투표 (4)가 각각 1회씩 등장하므로, 첫 우두머리는 1이나 4 중 선택 가능하다.
S 밖 (즉, {2, 4, 5})에서는 소 2, 4, 5가 각각 투표를 던지며 (2, 4, 5 각각 1회씩) 최대 빈도인 후보는 2, 4, 5 중 임의 선택 가능하다.
최대 다양도를 얻으려면 첫 번째 우두머리로 1, 두 번째 우두머리로 5를 선택하여 |1 - 5| = 4가 됩니다.
두 번째 업데이트 후, 투표 정보는 [2, 2, 4, 4, 5]가 됩니다.
예를 들어, S = {4, 5}로 선택하면,S 안에서는 투표가 4와 5로 나타나므로 첫 번째 우두머리 후보는 4 또는 5가 될 수 있고,
S 밖 (즉, {1, 2, 3})에서는 투표가 [2, 2, 4]로, 다수표는 2가 됩니다.
최대 다양도는 |5 - 2| = 3.
세 번째 업데이트 후, 투표 정보는 [2, 2, 4, 4, 2]가 됩니다.
이제 가능한 투표 값은 2와 4뿐이므로 최대 다양도는 |2 - 4| = 2.
따라서 출력은 차례대로 4, 3, 2가 됩니다.
예제 #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
로그인해야 코드를 작성할 수 있어요.