Maybe a classic solution to this kind of problems in China?

We use divide and conquer to solve this problem. We define Solve(l, r) to calculate the good pairs \((L,R)\) satisfying \(l\le L\le R\le r\), \(\textit{mid}=(l+r)/2\). Then we first call Solve(l, mid), Solve(mid + 1, r) and only need to calculate situations of \(L\le\textit{mid}<R\).

Calculate the suffix max/min from \(\textit{mid}\) in the left part and the prefix max/min from \(\textit{mid}+1\) in the right part. Then we enumerate minimum and maximum in which part. As the cases are symmetric, here I only show two cases.

• When minimum and maximum are both in the left part

Enumerate \(k\in[0,K]\), then it becomes \(R=\textit{max}-\textit{min}+L-k\). So \(\forall L\in[l,\textit{mid}]\), calculate \(R\) and check whether minimum and maximum are both in the left part.

• When minimum is in the left part and maximum in the right part

Enumerate \(k\in[0,K]\), then it becomes \(\textit{max}+L-k=\textit{min}+R\). Note that prefix/suffix maximum is non-decreasing and prefix/suffix minimum is non-increasing, this can be solved by two pointers.
Let \(c_x\) be the number of legal right part such that \(\textit{min}+R=x\). Just enumerate \(L\) from \(\textit{mid}\) downto \(l\), add legal parts (\(\textit{max}_R<\textit{max}_L\)) to \(c\) and delete illegal ones (\(\textit{min}_R>\textit{min}_L\)) from \(c\). As prefix minimum is non-increasing, right parts will be deleted from left to right, which can also be processed by two pointers.

Total time complexity: \(T(n)=2T(n/2)+O(nk)=O(nk\log n)\).

Sample Code(C++) (only 61 ms)

When \(K\) is large, just change the bucket \(c\) to a Fenwick tree and it is solved in \(O(n\log^2n)\).