BOJ 17665 Triple Jump

JOI Open Contest 2019 #1 三段跳び(Triple Jump)

 

 

문제 설명

 

직선 위에 $N$개의 구역이 있으며, i번 구역의 점수는 $A[i]$이다.

‘3단 점프’란, 다음의 조건을 만족하는 세 개의 구역 $(a, b, c)$의 순서쌍이다.

• $a < b < c$
• $b - a < c - b$

3단 점프의 점수는 $A[a]+A[b]+A[c]$, 즉 3단 점프에 속하는 세 구역의 점수의 합이다.

$Q$개의 쿼리 $(l, r)$이 주어진다. 각 쿼리에서는, $l ≤ a < b < c ≤ r$을 만족하는 3단 점프 $(a, b, c)$들의 점수의 최댓값을 구하여야 한다.

 

 

필요한 관찰

 

다음과 같은 3단 점프 $(a, b, c)$는 의미가 없다는 것을 알 수 있다.

• $a < d < b$이며, $A[a] ≤ A[d]$인 $d$가 존재한다.

 

이 경우, $(a, b, c)$보다 $(d, b, c)$가 항상 이득이므로 $(a, b, c)$는 고려할 필요가 없다.

 

다음과 같은 3단 점프 $(a, b, c)$ 또한 의미가 없다.

• $a < d < b$이며, $A[b] ≤ A[d]$인 $d$가 존재한다.

이 경우, $(a, b, c)$보다 $(a, d, c)$가 항상 이득이므로 $(a, b, c)$는 고려할 필요가 없다.

$b$를 고정하여 생각해보면, 위의 조건을 만족하는 $(a, b)$쌍은 최대 $2N$개이다.

 

 

Full Solution

 

이와 같이 유효한 $(a, b)$ 순서쌍들의 개수를 $O(N)$개로 줄이는데 성공하였다면, 세그먼트 트리를 이용하여 각 쿼리를 해결할 수 있다.

• 유효한 $(a, b)$ 순서쌍들을 전부 구하여, 각각을 구역 $a$에 저장한다.
• 쿼리 $(l, r)$들을 구역 $r$에 저장한다.
• 구역을 $1$부터 $N$까지 차례로 확인한다.
• $i$번째 구역을 볼 때 세그먼트 트리의 노드 $i$에 $A[i]$를 저장한다.
• 저장된 $(a, b)$에 대하여, 세그먼트 트리의 노드 $(2b - a - 1)$에 $A[a]+A[b]$를 저장한다.
• 세그먼트 트리의 적절한 구간 연산을 통하여, 각 쿼리의 답을 $O(logN)$에 구할 수 있다.

 

라고 장황하게 설명했지만, 간단히 요약하자면 스위핑을 하면서 오프라인 쿼리를 수행하면 된다.

 

총 시간복잡도는 $O((N+Q)logN)$이다.