Greedy Subsequences
Contest: Educational Codeforces Round 61 (Rated for Div. 2)
Difficulty rating: 2400
Tags: data structures, dp, trees

For some array $$$c$$$, let's denote a greedy subsequence as a sequence of indices $$$p_1$$$, $$$p_2$$$, ..., $$$p_l$$$ such that $$$1 \le p_1 < p_2 < \dots < p_l \le |c|$$$, and for each $$$i \in [1, l - 1]$$$, $$$p_{i + 1}$$$ is the minimum number such that $$$p_{i + 1} > p_i$$$ and $$$c[p_{i + 1}] > c[p_i]$$$.

You are given an array $$$a_1, a_2, \dots, a_n$$$. For each its subsegment of length $$$k$$$, calculate the length of its longest greedy subsequence.

Input format:
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 10^6$$$) — the length of array $$$a$$$ and the length of subsegments.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — array $$$a$$$.

Output format:
Print $$$n - k + 1$$$ integers — the maximum lengths of greedy subsequences of each subsegment having length $$$k$$$. The first number should correspond to subsegment $$$a[1..k]$$$, the second — to subsegment $$$a[2..k + 1]$$$, and so on.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example:

- $$$[1, 5, 2, 5]$$$ — the longest greedy subsequences are $$$1, 2$$$ ($$$[c_1, c_2] = [1, 5]$$$) or $$$3, 4$$$ ($$$[c_3, c_4] = [2, 5]$$$).
- $$$[5, 2, 5, 3]$$$ — the sequence is $$$2, 3$$$ ($$$[c_2, c_3] = [2, 5]$$$).
- $$$[2, 5, 3, 6]$$$ — the sequence is $$$1, 2, 4$$$ ($$$[c_1, c_2, c_4] = [2, 5, 6]$$$).

In the second example:

- $$$[4, 5, 2, 5, 3, 6]$$$ — the longest greedy subsequences are $$$1, 2, 6$$$ ($$$[c_1, c_2, c_6] = [4, 5, 6]$$$) or $$$3, 4, 6$$$ ($$$[c_3, c_4, c_6] = [2, 5, 6]$$$).
- $$$[5, 2, 5, 3, 6, 6]$$$ — the subsequence is $$$2, 3, 5$$$ ($$$[c_2, c_3, c_5] = [2, 5, 6]$$$).

Example input:
6 4
1 5 2 5 3 6

Example output:
2 2 3

Example input:
7 6
4 5 2 5 3 6 6

Example output:
3 3

Editorial:
Let's calculate for each position $$$i$$$ position $$$nxt_i$$$ — "the closest greater from the right" element to $$$i$$$ and add directed edge from $$$i$$$ to $$$nxt_i$$$. Then we will get oriented forest (or tree if we'd add fictive vertex) where all edges are directed to some root.
So, we can look at current subsegment we need to calculate the answer for as at a number of marked vertices in the tree. Then, the answer itself is a longest path up to the tree consisting only from marked vertices. Key observation is next: if $$$u$$$ and $$$v$$$ are marked and $$$u$$$ is an ancestor of $$$v$$$ then any vertex $$$y$$$ on path from $$$v$$$ to $$$u$$$ is also marked.
So, "the longest path up to the tree consisting only from marked vertices" has length equal to a number of marked vertices on path to the root. And we have three types of queries: mark a vertex, unmark a vertex and calculate maximum number of marked vertices among all paths to the root.
It can be done with Segment Tree on Euler Tour of the tree: if we calculate $$$T_{in}$$$ and $$$T_{out}$$$ for each vertex in dfs order, then marking/unmarking is just adding $$$\pm 1$$$ to a segment $$$[T_{in}, T_{out})$$$, and maximum among all paths is a maximum on the whole tree.
Result time complexity is $$$O(n \log{n})$$$ and space complexity is $$$O(n)$$$.