显然可以容斥，也就是选一个数字的序列，要求它们都是连续 $k$ 步取出的，合法的条件是它们在 $[l,r]$ 的每个栈中的出现位置都是单调递增的。这个容斥可以用 DP 实现，系数可以在区间扩展的时候 $O(1)$ 更新，总复杂度为 $O(n^2k^2)$。注意到每次 DP 的复杂度其实是 $O(n+m)$，其中 $m$ 是 $(u,v)$ 的对数，满足 $u$ 在 $[l,r]$ 的每个栈中都在 $v$ 之前。因为排列是随机的，这样的总对数期望只有 $$ \sum_{l=2}^k(k-l+1)\sum_{(u,v)}2^{-l}=O(n^2k) $$ 故总复杂度为 $O(n^2k+nk^2)$。