Seven Nevers
Time limit2sMemory limit512 MB
For every window of k consecutive elements in a permutation, compute the LIS length after deleting that window.
- Level
Hard9 of 10
- Topics
- Dynamic programming, Segment tree, Divide and conquer, Greedy
- Solved
- No attempts yet
Problem
The longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence's elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence does not have to be contiguous.
You are given a permutation of the first n positive integers a1, a2, . . . , an and an integer k. For each i from 1 to n − k + 1, find the length of the longest increasing subsequence of the sequence a1, a2, . . . , ai−1, ai+k, ai+k+1, . . . , an. In other words, find the length of the longest increasing subsequence of the sequence obtained by erasing ai, ai+1, . . . , ai+k−1 from a.
Input
The first line contains two integers n and k (1 ≤ k < n ≤ 3 · 105), the length of the given permutation and the number of consecutive elements to be removed.
The second line contains n integers a1, a2, . . . , an (1 ≤ ai ≤ n; ai ≠ aj for i ≠ j), the elements of the permutation.
Output
Output n−k+1 integers, one per line, where the i-th integer is the length of the longest increasing subsequence of the sequence a1, a2, . . . , ai−1, ai+k, ai+k+1, . . . , an for i = 1, 2, . . . , n − k + 1.