백준 5676번 음주 코딩

문제

오늘은 ACM-ICPC 대회 전 날이다. 상근이는 긴장을 풀기 위해서 팀원들과 근처 술집으로 갔다.

상근이와 친구들은 다음 날 있을 대회를 연습하기 위해서 작은 게임을 하기로 했다.

먼저, 선영이는 상근이에게 총 N개의 정수로 이루어진 수열 X1, X2, ... XN을 적어준다. 게임은 총 K번 라운드로 이루어져있고, 매 라운드마다 선영이는 상근이에게 명령을 하나씩 내린다. 명령은 아래와 같이 두 가지가 있다.

• 변경: 이 명령은 친구가 수열의 한 값을 바꾸고 싶을 때 사용한다.
• 곱셈: 선영이는 상근이에게 i와 j를 말한다. 상근이는 Xi × Xi+1 × ... × Xj-1 × Xj 의 값이 양수인지, 음수인지, 0인지를 대답한다.

곱셈 명령에서 상근이가 대답을 잘못했을 때의 벌칙은 소주 한 잔이다. 상근이는 갑자기 대회가 걱정되기 시작했다. 또, 상근이는 발머의 피크 이론을 증명하고 싶지 않다.

다행히 선영이는 상근이에게 노트북 사용을 허락했다. 상근이는 자신의 수학 실력보다 코딩 실력을 더 믿는다.

상근이를 돕는 프로그램을 작성하시오.

문제풀이

사용한 알고리즘: Fenwick Tree

(1) 생각

 구하고자 하는 건 구간 i~j 곱이  양수인지 음수인지 0 인지 입니다.
 따라서, Fenwick tree 를 이용하여 각 구간의 음수개수와 양수 개수를 기억해 줍니다.

(2) 코드 6~11

 'state[x] : x 가 무슨 수인지'
 'Minus[x] : x 가 음수 이면 1 아니면 0'
 'Zero[x] : x 가 0 이면 1 아니면 0'
 으로 설정해 주었습니다.

(3) 코드 13~69

 Fenwicktree 가 각각 Minus, zero 로 2개 있다고 생각하고 구현하였습니다.

(4) 코드 87~94

 0을 업데이트 해야하는 경우는
    1. 변경해야 하는 수가 0 이고, 해당 값이 원래는 0이 아니었던 경우
    2. 해당 값이 0이고, 변경해야 하는 수가 0이 아닌경우
 음수를 업데이트 해야하는 경우는
    1. 변경해야 하는 수가 음수이고, 해당 값이 원래는 음수가 아닌 경우
    2. 해당 값이 음수이고, 변경해야 하는 수가 음수가 아닌 경우
 입니다.

(5) 코드 95~104

 우리가 알아야 하는 것은 i~j 구간에
    1. 0이 있는지 여부 ( 있으면 0 출력 )
    2. 음수 개수가 짝수 개인지 ( 짝수이면 + 출력 )
    3. 음수 개수가 홀수 개인지 ( 홀수이면 - 출력 )
 입니다.