숙제 도움

시간 제한1초메모리 제한2048 MB

요약

숨겨진 순열의 임의 부분 배열에 대해 역전 개수를 질의할 수 있을 때, 그 순열의 최장 증가 부분 수열 길이를 구합니다.

난이도: 보통10점 중 7점
유형: 이분 탐색, 분할 정복, 배열
정답자: 아직 제출이 없습니다

문제

Alice는 최근 주어진 순열의 임의의 부분 배열에서 역전(inversion)의 개수를 출력하는 프로그램을 작성하는 숙제를 받았다. 그녀는 이 숙제를 기쁘게 제출했고 만점을 받았다. 다음 주 숙제는 같은 배열에서 가장 긴 증가하는 부분 수열의 길이를 구하는 것이었다. 안타깝게도 Alice는 필요한 순열이 적힌 종이를 이미 버린 뒤였다. 다행히 이 순열은 그녀가 작성한 프로그램에 저장되어 있다. 하지만 지금 그녀는 순열의 부분 배열에 있는 역전 개수를 질의하는 것만 할 수 있다. 수업이 곧 시작되므로, 그녀는 이 문제를 제때 풀 수 있도록 도와 달라고 부탁한다. 수열 $a$ 가 배열 $b$ 의 부분 수열이라는 것은 $b$ 에서 일부 원소(0개일 수도 있다)를 삭제하여 $a$ 를 얻을 수 있다는 뜻이다. 수열이 증가한다는 것은 모든 원소가 그보다 앞의 모든 원소보다 엄격하게 크다는 뜻이다. 배열의 LLIS는 가장 긴 증가하는 부분 수열의 길이이다.

예제1

예제 1
입력
```
3

1

1
```
예상 출력
```
? 1 3

? 1 2

! 2
```