https://www.acmicpc.net/problem/18838
문제요약
- LIS 중에서 사전순으로 K 번째를 찾기
- 서로 다른 숫자(다행히)
- N : 10^5
접근법
- https://www.acmicpc.net/problem/17411 문제를 응용할 수 있음
- 큰 흐름
- 각 숫자로 시작하는 LIS의 길이, 경우의 수를 계산
- 주어진 수열의 LIS의 길이가 X라고 할때
- X의 길이를 갖는 가장 작은 숫자부터 경우의 수를 비교
- 경우의 수 > K : 해당 숫자로 시작하는 LIS는 K번째에 들어오지 않음
- 경우의 수 < K : 해당 숫자로 시작하는 LIS는 K번째에 들어옴
- X-1, X-2, ... 에 대해 반복으로 수행하고, K도 업데이트 시켜줌
- 각 숫자로 시작하는 LIS의 길이 찾기
- lower_bound나 segment tree로 해결 가능
- 경우의 수 계산
- 구하고자 하는 곳의 LIS의 길이가 X일때, 구해야하는 것은 길이 : X-1, 위치 : 오른쪽, 숫자 : 커야함
- 길이가 X-1인 것들의 (숫자, 위치)를 모아서 정렬시켜놓음
- 길이가 X인 것들의 (숫자, 위치)를 모아서 정렬시켜놓음
- 길이가 X인 것들을 큰 것부터 살펴보는데, X-1에서는 이보다 큰 것들을 segment tree에 업데이트함. 이후 오른쪽 것들의 합을 구함(LIS를 구간트리로 구하는 아이디어)
- 작업이 끝나고 난 후 X-1에 사용한 것들을 대상으로만 "0"으로 segment tree에서 업데이트 => segment tree 전체를 클리어하면 시간복잡도에서 걸림
- K 번째 찾기
- 길이[] 배열에 시작하는 숫자를 담고 정렬
- 이후 K 번째 수 찾기 기법 사용
newbieski