Seven Nevers
시간 제한2초메모리 제한512 MB
순열에서 연속한 k개 원소를 지웠을 때 남은 수열의 최장 증가 부분 수열 길이를 모든 시작 위치마다 구한다.
문제
최장 증가 부분 수열 문제는 주어진 수열의 부분 수열 중에서 원소가 오름차순으로 정렬되어 있으면서 길이가 최대인 것을 찾는 문제이다. 이 부분 수열은 연속하지 않아도 된다.
첫 n개의 양의 정수의 순열 a1, a2, . . . , an과 정수 k가 주어진다. 각 i = 1, 2, . . . , n − k + 1에 대해, 수열 a1, a2, . . . , ai−1, ai+k, ai+k+1, . . . , an의 최장 증가 부분 수열의 길이를 구하라. 다시 말해, a에서 ai, ai+1, . . . , ai+k−1을 지운 수열의 최장 증가 부분 수열의 길이를 구하라.
입력
첫째 줄에 두 정수 n과 k가 주어진다 (1 ≤ k < n ≤ 3 · 105). n은 주어진 순열의 길이이고, k는 지울 연속한 원소의 개수이다.
둘째 줄에 n개의 정수 a1, a2, . . . , an이 주어진다 (1 ≤ ai ≤ n; i ≠ j이면 ai ≠ aj). 이는 순열의 원소이다.
출력
n−k+1개의 정수를 한 줄에 하나씩 출력한다. i번째 정수는 i = 1, 2, . . . , n − k + 1에 대한 수열 a1, a2, . . . , ai−1, ai+k, ai+k+1, . . . , an의 최장 증가 부분 수열의 길이이다.