If \(K=0\)

If \(K=0\), the problem can be solved with the following method.

Manage a lazy segment tree, the \(L\)-th element of which contains \((\mathrm{max}(P_L,\ldots,P_R) - \mathrm{min}(P_L,\ldots,P_R)) - (R -L )\).

Actually, the management can be achieved only with segment addition, so the problem can be solved with a lazy segment tree that supports segment additions and segment minimum-value searching and sliding \(R\) from \(1\) to \(N\).

How to update the lazy segment tree?

The \(-(R-L)\) part is easy, so we explain here how to manage \(\mathrm{max}(P_L,\ldots,P_R)\) part with segment additions.

Here, we consider utilizing the technique of managing maximum value with a stack.

The technique of finding maximum value with a stack

For a fixed \(R\), \(\mathrm{max}(A_i, A_{i+1},\ldots,A_R)\) is monotonically increasing with respect to \(i\).

When \(R\) increases as \(1,2,\ldots,N\) in this order, the indices \(i\) such that \(\mathrm{max}(A_i, A_{i+1},\ldots,A_R) \neq \mathrm{max}(A_{i+1}, A_{i+2},\ldots,A_R)\) can be managed with a stack as follows.

• Prepare an empty stack.
• Every time \(R\) is incremented, do the following.
  • While stack is non-empty and the first value is less than \(A_R\), pop the first element of the stack.
  • Push \(A_R\) to the stack.

Since \(A_1,A_2,\ldots,A_N\) is pushed at most once each, this algorithm works in a total of \(\mathrm{Ο}(N)\) time.

With the method above, we can obtain the maximum value \(X\) for the current segment, so we can manage the maximum value with segment addition. (When an element is popped, we can cancel them out by doing negative addition.)

\(\mathrm{min}\) can be processed in the same way.

The time complexity is \(\mathrm{O}(N\log N)\).

For general cases

We can handle the general cases with a little modification on the lazy segment tree. Instead of managing the minimum value and the number of them, we can manage \(K+1\) small values and their numbers.

The time complexity is \(\mathrm{O}(NK\log N)\) or \(\mathrm{O}(NK^2\log N)\).