BOJ 25351 - 중간 구간 게임

문제 링크 : https://www.acmicpc.net/problem/25351

문제 풀이

part 1

이후로 f(p)는 구간 p에 대한 중간 원소 인덱스 합을 의미한다. 또한 (a,b) 는 닫힌 구간 [a,b] 를 의미한다. 

선공과 후공이 고를 수 에 대해서 생각해보자. T번째 판은 [a,b] 에서 진행된다.
두 개의 구간 p와 q에 대해서 p가 q에 속한다면 f(p)<=f(q)이다. - lemma 1
lemma 1에 의해서 후공은 a 혹은 b를 선택하게 된다. 

 이때 선공이 수 x를 선택한다면 후공이 a 또는 b를 선택하여 게임의 점수는 max(f(a,x), f(x,b)) 가 된다. 그렇다면 선공은 x를 어떻게 게임의 점수인 식이 최소가 되도록 하는 x를 고를 것이다. 이때 lemma 1에 의해서 x값이 커질수록 f(a,x)의 값은 단조증가 할 것이며, f(x,b)의 값은 단조감소 할 것이다. 
 선공이 고를 최소가 되는 x는 f(a,x)의 값과 f(x,b)의 값이 역전되는 지점일 것이다. 이 지점은 이분탐색으로 찾을 수 있다. f(a,x)와 f(x,b) 값을 비교하면서 큰 쪽으로 x를 이동시키면 된다. 따라서 f(a,x) 와 f(x,b) 값을 잘 계산하면 x를 찾아 이 문제를 해결할 수 있다. 

part 2.1

 일단은 먼저 시간초과가 날 수 있는 $O(Nlog^2N)$ 풀이부터 살펴보자. 다양한 접근 방식이 있지만, 내가 생각한 방식은 중간 원소 인덱스 합이 라는 값을 다른 식으로 표현하는 것이다. 

 구간 내에서 중간 원소 인덱스 합 = (구간 내 모든 원소 인덱스 합) - (구간 내에서 같은 값의 원소 중 가장 왼쪽에 있는 원소들의 인덱스 합) - (구간 내에서 같은 값의 원소 중 가장 오른쪽에 있는 원소들의 인덱스 합) + (구간 내에서 유일하게 존재하는 원소들의 인덱스 합)

 구간 내 모든 원소 인덱스 합은 가우스 합을 이용하면 $O(1)$에 간단하게 구할 수 있다.

Part 2.2

가장 오른쪽에 있는 원소들의 인덱스 합은 PST를 이용하여 구할 수 있다.
1. 모든 원소 $A_i$ 들에 대하여 값이 같으며 바로 왼쪽에 있는 원소의 인덱스 $p$를 구해놓는다. 
2. pst의 오른쪽 끝을 1부터 n까지 바꿔가면서 진행한다. 즉 i번째 pst는 (1~i)의 값을 들고 있다.
3. pst 한번의 업데이트는 인덱스 i에 +i, 인덱스 p에 -p 를 업데이트 하면 된다. 

 가장 왼쪽에 있는 원소들의 인덱스 합도 비슷하게 구할 수 있다. 다만 구간 내에서 유일하게 존재하는 원소들의 인덱스 합을 구하기 위해서는 조금 다른 방식을 사용해야 한다. 

Part 2.3

 구간 내에서 유일하게 존재하는 원소들의 인덱스 합을 구하기 - 서로 다른 수와 쿼리 2 의 풀이 기반. 

 똑같이 i번째 pst는 1~i 에 대한 정보를 담고 있을 것이며 구간의 오른쪽 끝이 i인 정보에 대해서 탐색할 때 사용한다. 
따라서 i번째 pst에 대해서 날리는 쿼리는 (x,i) 구간 또는 (x,n) 구간이다. 
$A_i=k$, 값이 k인 i 직전의 인덱스는 p, 값이 k인 p 직전의 인덱스는 q라고 가정하자.

 i 업데이트 이전의 pst. 즉 i-1 번째 pst에서 값 k는 구간 내 유일 원소 인덱스 합에 q이하의 x에 대해서는 0, p초과의 x에 대해서도 0, q초과 p이하의 x에 대해서만 값 p를 관여 했을 것이다. 이 말이 잘 이해가 안 되었을 수도 있으니 아래 그림을 참조하면 좋을 것이다.

 따라서 반열린 구간 (q,p] 에 값 p가 더해져 있어야 하며, i가 들어오는 순간 (q,p] 구간에 -p를 더하고 반열린 구간 (p,i]에 값 i를 더해야 한다. 하지만 pst 에서는 구간 업데이트를 할 수 없기 때문에 range update point query 라는 것을 이용하여 prefix를 이용한 point update range query 로 바꿔주면 된다. (혹은 이렇게 한번에 생각했을 수도 있다.)

 결론적으로 업데이트는 인덱스 i에 +i . 인덱스 p에 -i . 인덱스 p에 -p . 인덱스 q에 +p 로 업데이트가 될 것이다. 

Part 2.4

 가장 왼쪽에 있는 원소들의 인덱스 합은 i~n을 관리하는 pst 에 2.2를 대칭적으로 해서 구할 수 있다. 하지만 추후 작업을 위해서는 1~i를 관리하는 pst에 모두 담아야 한다. 
 이는 위와 똑같이 생각을 해보면 인덱스 i에 +i, 인덱스 p에 -i 라는 것을 어렵지 않게 생각해 낼 수 있다. 

Part 2.5

 위의 내용을 다 합쳐보자. part2.2 + part 2.4 - part 2.3 을 한번에 저장한 후에 전체 구간 인덱스 합에서 빼면 된다. 이때 3개에 대한 처리를 합쳐서 계산해보자. 

	i	p	q
part 2.2	+i	-p
- part 2.3	-i	+i +p	-p
part 2.4	+i	-i
총합	+i		-p

와! 다 합쳤더니 8번의 업데이트를 단 2번의 업데이트만 하여 다음 pst를 만들면 된다는 사실을 알아냈다. 

이대로 pst를 구현하고 part 1으로 이분탐색을 실시하여 문제를 해결하면 $O(Nlog^2N)$ 이고 문제를 해결할 수 없다. 적어도 나는 7초가 나왔다. 하지만 $O(Nlog^2N)$ 으로 이 문제를 해결한 사람도 있으니, 최적화에 자신이 있다면 이러한 방법도 시도할 수는 있다. 

Part 3 - Going to $O(NlogN)$

part 3.1

 최종 목표는 세그먼트 트리에서 내려가면서 이분탐색을 하는 것이다. 트리에서 두 자식을 보면서 어느쪽으로 내려갈지를 계속 확인하고, 최종적으로 내려간 위치의 인덱스가 구하고자 하는 x가 되도록 하고 싶다. 
 또한 2.4에서 한쪽 방향 pst에 모두 몰아 넣은 것은 이를 위한 초석이기도 하다. 

 part 2에서 한 모든 내용을 대칭 시켜서 i~n을 관리하는 pst 도 하나 만들자. (part 2에서 만든 pst는 pst1, 방금 뒤집어서 만든 pst는 pst2라고 한다.) 즉, qry(x,y) 를 구할 때 pst1의 1~y를 담당하는 pst에서 (x,y) or (x,n)으로 구하는 값과 pst2의 x~n을 담당하는 pst에서 (1,y) or (x,y)으로 구하는 값은 일치한다는 소리이다. 

part 3.2

 이제 part 1에서 설정했던 t번째 game [a,b] 에 대한 선공의 최적의 x를 $O(NlogN)$ 에 구해보도록 하자. 
f(a,x) 는 pst 2의 a~n pst. f(x,b) 는 pst1의 1~b pst에서 구하면서 진행한다.  하나의 고정된 pst에서 내려가면서 진행해야 하기 때문에 pst2를 새로 만든 것이다. (앞으로 a~n pst, 1~b pst 라는 말을 떼고 혼용해서 사용하려고 한다.)

현재 노드가 구간 [s,e]를 담당하고 있고 m=(s+e)/2 라면 pst2의 왼쪽 자식은 [s,m] 의 값을 담고 있고, pst1의 오른쪽 자식은 [m+1,e]의 값을 담고 있다. 내려오면서 계속 값을 더해주면서 저장하면서 내려왔다면 pst2의 [1,m] 값, pst1의 [m+1,n] 값을 알 수 있으며, 선택한 pst에 의해서 pst2의 [1,m] 값 = pst2의 [a,m] 값이며 pst1의 [m+1,n] 값 = pst1의 [m+1,b] 값이기 때문에 트리에서 내려가면서 m에 대해서 f(a,m), f(m+1,b)를 O(1) 만에 구할 수 있으며, 이 값을 비교하여 다음 m을 정해서 내려가는 것이 가능하다. 

여기서 의문이 들 수 있다. f(a,m), f(m,b)를 가지고 비교해야하는 데 우리가 아는 값은 f(a,m), f(m+1,b) 이다. 따라서 이를 보정해 주어야 한다. 전체 칸을 n+1 칸으로 늘린다. 그 후, pst2는 상관이 없지만, pst1 에는 인덱스 1의 값을 0으로 고정하고, i+1 의 위치에 i의 값을 담는다. 즉, 한 칸 씩 시프트해서 값을 저장하고 있는 것이다. 이러면 pst1에서 [m+1,e] 를 담당하는 구간은 사실 [m,e-1] 의 값을 저장하고 있고, 이것이 모여 [m+1,n+1] 구간이 되면 이는 [m,n] = [m,b] 의 값을 알 수 있는 것이다. 따라서 이 문제를 해결할 수 있다. 

Part 4 정리

1. 선공이 a 또는 b를 고른다는 사실을 확인한다.
2. 후공이 f(a,x), f(x,b) 의 대소관계가 뒤집어지는 지점의 x를 고른다는 점을 확인한다.
3. f(a,x)를 구하기 위해서 중간 원소 인덱스 합을 구하는 방식을 식으로 풀어서 쪼갠후에 각각에 대해서 pst에 업데이트 한다.
3-1. pst를 만드는 과정에서 하나는 1만큼 shift하기, 하나는 뒤집을 pst로 만들기를 한다.
4. 쿼리 a,b 에 대해서 각각 끝점에 해당하는 pst를 선택한다. 
5. 두개의 pst에서 동시에 같은 방향의 자식노드로 내려가면서 합을 누적하고, 이를 이용하여 f(a,m),f(m,b) 를 계속 비교하면서 내려간다,
6. 최종적으로 바닥에 도달했을 때의 담당하는 구간을 통해서 x의 값을 구해낼 수 있다.
7. 구한 x의 값을 이용하여 max( f(a,x), f(x,b) ) 의 값을 구해 출력한다.