[USACO19JAN] Train Tracking 2 P

同一个位置上的数看似可能被多个 $c$ 所限制，但实际上真正限制它的只有所有涉及到它的 $c$ 中最大的。

那么我们转而考察某个极长的 $c_i$ 相等的区间 $[i,j]$ 会对哪个区间做出什么样的限制。

如果该区间的 $c$ 大于其左侧区间，那么它所限制的区间的左端点为 $i$；否则它所限制区间的左端点为 $i+K-1$，并且该区间一定以 $c$ 开头。特别地，第一个区间的开头为起始位置。

如果该区间的 $c$ 大于其右侧区间，那么它所限制的区间的右端点为 $j+K-1$；否则它所限制区间的右端点为 $j$，并且该区间一定以 $c$ 结尾。特别地，最后一个区间的结尾为终止位置。

---

接下来需要解决这样的问题：求长度为 $n$，任意长为 $k$ 的区间最小值都为 $c$ 的序列的数量。

不难发现这样的要求等价于，每个值不小于 $c$，并且任意长为 $k$ 的区间中均包含至少一个 $c$。

于是 DP，用前 $n-1$ 个数合法，最后一个数任意填的方案数，减去前 $n-1$ 个数合法，长为 $k$ 的后缀中不出现 $c$ 的方案数即可。