[JOI Open Contest 2018] Xylophone

문제 : https://www.acmicpc.net/problem/16794

---

N개의 건반으로 이루어진 실로폰이 있다.

 

각 건반은 1부터 N 사이로 이루어진 서로 다른 음의 높이를 가지고 있는데, 이를 크기가 N인 배열 A로 나타낼 수 있다.

즉, A는 크기가 N인 순열로 볼 수 있다.

 

건반에서 가장 낮은 음높이의 건반은 가장 큰 음높이의 건반의 왼쪽에 있다.

\(A_i = 1, A_j = N\)일 때, \(i<j\)이다.

 

건반의 주인은 \(s\)번부터 \(t\)번까지의 건반을 한 번에 누를 수 있다.

 

건반의 주인은 절대음감이라서, \(s\)번째 건반부터 \(t\)번째 건반 중 가장 높은 음과 가장 낮은 음의 차이를 알 수 있다.

 

절대음감을 이용하여, 배열 A를 찾는 문제

 

---

구현해야 할 함수

void solve(int N)

인터렉션을 이용하여 배열 A를 찾아야 한다.

 

인터렉션

int query(int s,int t)

\(max(A[s,t])-min(A[s,t])\)를 반환한다.

최대 1만번 호출할 수 있다.

 

void answer(int i, int a)

A[i] = a 라고 기록한다.

 

---

제약

• N은 최대 5000

 

---

풀이

간단한 계산을 위해 A[1] = 1로 가정해보자

그리고 A[2] = A[1] + query(1,2) = \(x\)로 정의하자.

 

 

다음 A[3] = \(y\)의 경우는 아래 세 가지중 하나이다.

1. \(y\)가1과 \(x\)사이인 경우
2. \(y\)가 1보다 작은 경우
3. \(y\)가 \(x\)보다 큰 경우

---

 

1. \(y\)가 1과 \(x\) 사이인 경우

 

query(1,3)이 query(1,2)와 같은 경우이다.

A[3] = \(y\)는 1과 \(x\) 사이에 존재한다.

이는 \(y\)가 [1,3] 구간에서 최대값과 최소값에 영향을 주는 수가 아니기 떄문이다.

 

 

그러므로 A[3] = A[2] - query(2,3) 이다.

 

---

 

2. \(y\)가 1보다 작은 경우

query(1,3)과 query(1,2)는 같지 않다.

그러나 query(1,3)과 query(2,3)은 같은 경우이다.

 

 

그러므로 A[3] = A[2] - query(2,3)이다.

 

 

---

 

3. \(y\)가 \(x\)보다 큰 경우

위 쿼리 조건을 만족하지 않는 경우다.

A[3] = A[2] + query(2,3)이다.

 

 

 

---

A[3]의 가능한 세 가지 경우에 대해서, 새로 호출한 쿼리는 query(2,3)과 query(1,3) 두 종류이다.

 

이와 같은 방법으로 A[i]는 query(i-2,i)와 query(i-1,i)를 이용하여 구할 수 있다.

 

A[i-2]<A[i-1]인 경우, 위 상술한 방법으로 구할 수 있고,

A[i-2]>A[i-1]인 경우에는 query 앞에 부호만 바꾸어 주면 된다.

 

 

---

 

이러한 방법으로 구한 A는 0이하의 값이 나올 수 있다.

이 때 (A의 최소값+1)만큼 A에 더해줌으로써, 배열 A가 1~N사이의 값이 나오도록 조정해주면 된다.

 

 

---

이렇게 구한 배열 A를 검토해보면, \(A_i = 1, A_j = N\)일 때, \(i<j\)조건을 만족하지 않을 수도 있다.

이는 처음 A[2] = A[1] + query(1,2)로 가정한 부분이 A[2] = A[1] - query(1,2) 라서 생긴 문제다.

 

 

이는 배열 A의 위상을 바꾸어 주면 된다.

 

d[i] = A[i] - A[i-1]로 계산하고,

A[i] = A[i-1] - d[i]를 해주면 된다.

이 때, 배열 d를 먼저 전부 구한 후에, A를 다시 계산만 해주면 된다.

 

 

최종적으로 A[i] 계산하는데 사용한 query는 2개씩이 되고, 10000번의 query로 문제를 풀 수 있다.