Homework Help

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

요약

임의 부분 배열의 역순 쌍 개수를 알려주는 질의만으로 숨겨진 순열의 최장 증가 부분 수열 길이를 구한다.

난이도: 어려움10점 중 8점
유형: 이분 탐색, 분할 정복, 구간, 정렬
정답자: 아직 제출이 없습니다

문제

Alice was recently given a homework assignment to write a program that would output the number of inversions in any subarray of a given permutation. She happily turned it in and got full marks on her assignment. The next week, their homework assignment was to find the length of the longest increasing subsequences in the same array. Unfortunately, Alice had already thrown away the paper that contained the permutation she needed.

Luckily, this permutation was stored in the program she wrote. Unfortunately, she is now only able to query for the number of inversions in the subarrays of the permutation. As class is close to starting, she asks you for help to solve this problem in a timely manner.

A sequence $a$ is a subsequence of an array $b$ if it is possible to delete some (possibly zero) elements from $b$ to get $a$ . A sequence is increasing if every element is strictly greater than all preceding ones, and the LLIS of an array is the length of the longest increasing subsequence.

예제1

예제 1
입력
```
3

1

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

? 1 2

! 2
```