Informatica Online Judge

  Pick me KOI [1931 / 078B]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 3   Total Tried : 5


The Champion of this Problem (C++) : gs16051 - 38ms / 1495byte
My Best Submission (C++) : N/A

[koistudy.net (34th 송현진)]
Writer ID : [gs16051]

Background

KOI국은 admin에 의해 세워진 이후 발전을 거듭하였다.
시간이 흘러, 초대 대통령인 admin의 임기가 몇 달 남지 않았다. KOI국에서는 새 대통령을 뽑는 선거를 진행할 예정이다.
이번 대통령 선거에는 $n$명의 후보자가 출마하였다. 그러나 몇몇 후보자는 다른 후보와 단일화를 하여 불출마를 선언하였다.
각 후보자 별 지지자는 $a_i$명이다(물론 자기 자신도 포함한다). 만약 i번 후보자가 j번 후보자와 단일화하여 사퇴하면 i번 후보의 지지자들은 j번 후보를 지지한다.
한 후보는 여러 번 단일화를 할 수 있다. 그러나 세 명 이상이 한 번에 단일화를 하는 일은 없다.
사람들은 단일화 상황에 따라 지지 후보를 여러 번 바꿀 수 있다.

당신은 여론조사 기관의 대표이다. KOI국은 매우 거대하므로 데이터 분석을 위한 프로그램을 작성해야 한다.
후보 별 지지자 추이를 조사하여 승자를 예측하는 것이 당신의 임무이다

Input

첫 줄에는 후보자의 수 $n$이 주어진다(단, $1\leq n\leq200000$).
두 번째 줄에는 후보자 별 지지자 수 $a_i$가 공백으로 구분되어 주어진다($1\leq i\leq n$, $1\leq a_i\leq10^9$, $v_i$는 자연수).
세 번째 줄에는 사건의 수 $k$가 주어진다(단, $1\leq q\leq200000$).
이후 q번째 줄에는 각 사건을 설명하는 데이터가 입력된다. 데이터의 의미는 다음과 같다:
1 i : i번째 후보(사퇴하였다면 해당 후보가 지지하는 후보)의 지지자 수를 조사하여 출력한다.
2 i $a_i$ : i번째 후보의 지지자가 $a_i$명으로 변화하였음을 반영한다. 해당 사건이 일어날 때 i번 후보는 사퇴하지 않은 상태이다.
3 i j : i번째 후보가 j번째 후보와 단일화를 선언하고 사퇴하였음을 반영한다. i번 후보와 j번 후보 모두 이 사건 전에는 사퇴하지 않았다. 아무것도 출력하지 않는다.
4 : 가장 지지자 수가 많은 후보와 그 지지자 수를 출력한다. 만약 지지자 수가 동일하다면 번호가 가장 작은 후보가 우선이다.
5 i j : i번째 후보(또는 그 후보의 지지자)와 j번째 후보(또는 그 후보의 지지자) 중 지지자가 많은 후보와 지지자 수 차이를 출력한다. 만약 두 후보의 지지자 수가 동일하다면 "EVEN"(큰따옴표 제외)을 출력한다.
(단, $1\leq i,j\leq n$, $i\neq j$)

테스트 케이스
#1(25%): $1\leq n\leq1000$, $1\leq q\leq1000$
#2(25%): 1, 4번에서 사퇴한 후보자의 번호는 입력되지 않는다.
#3(50%): 추가 조건 없음

Output

입력되는 각각의 조건에 따라 적절한 내용을 출력한다.

IO Example

Example Input 1
5
1 2 3 4 5
4
3 2 1
5 4 2
3 2 4
4

Example Output 1
4 1
4 7

<설명>
첫 번째 사건에서는 2번 후보가 사퇴하고 1번 후보의 지지자는 3명이 된다.
두 번째 사건에서는 4번 후보의 지지자가 4명이고 2번 후보가 지지하는 1번 후보는 지지자가 3명이므로 "4 1"을 출력한다.
세 번째 사건에서는 2번 후보가 지지하던 1번 후보가 사퇴하고 4번 후보의 지지자는 7명이 된다.
네 번째 사건에서는 3번 후보의 지지자가 3명, 4번 후보는 7명, 5번 후보는 5명이므로 "4 7"을 출력한다.

Example Input 2
2
2 2
2
4
5 1 2

Example Output 2
1 2
EVEN

<설명>
첫 번째 사건에서는 1번 후보의 지지자가 2명, 2번 후보의 지지자가 2명이므로 번호가 작은 1번 후보가 우선이다. "1 2"를 출력한다.
두 번째 사건에서는 1번 후보와 2번 후보의 지지자 수가 같으므로 "EVEN"을 출력한다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]