官方题解只能做到 $O(n^3)$？玩的太差了。这道题可以做到 $O(n^2\log n)$ 时间、$O(n^2)$ 空间，不需要枚举高度，也不必停留在逐点插值的 $O(n^3)$ 做法。关键是：只计算递归实际需要的区间，每个区间只使用自己的高度断点，并用一次卷积完成多项式采样值的批量外推。

从机器人移动到区间计数

题目中，P 型机器人向左可以经过与起点等高的柱子，Q 型机器人向右却只能经过严格更矮的柱子。这个不对称非常重要。

对高度序列建立大根笛卡尔树，规定高度相同时，位置更靠右的柱子优先成为根。也就是按照二元组 $(h_i,i)$ 比较大小。

在这棵树中，结点 $s$ 的左子树，恰好对应向左连续满足 $h_j\le h_s$ 的柱子；右子树，恰好对应向右连续满足 $h_j< h_s$ 的柱子。因此，两种机器人的移动步数分别等于结点 $s$ 的左右子树大小。

于是，原题要求等价于：

笛卡尔树的每个结点，其左右子树的结点数之差都不超过 $2$。

考虑一个子树对应的区间 $I=[l,r]$，长度为 $m$。若选择位置 $k$ 为根，则左右子树大小分别是 $k-l$ 和 $r-k$，所以根必须属于 $K_I={k\in[l,r]:|2k-l-r|\le2}$。这个集合最多只有三个位置。

固定根的高度为 $x$ 后，左边所有高度必须不超过 $x$，右边所有高度必须严格小于 $x$。令 $F_{l,r}(x)$ 表示区间 $[l,r]$ 内满足要求、且所有高度都不超过 $x$ 的方案数，规定空区间的函数恒为 $1$。按照最右侧最大值所在的位置分类，可以得到唯一且不重不漏的转移：

$$ F_{l,r}(x)-F_{l,r}(x-1) = \sum_{\substack{k\in K_I\\A_k\le x\le B_k}} F_{l,k-1}(x)\,F_{k+1,r}(x-1). $$

这里左边使用 $x$、右边使用 $x-1$，正好实现“最大值最右侧的位置为根”的约定，不能将两边都写成相同的上界。

接下来从 $[1,n]$ 开始记忆化递归，只访问上述候选根产生的左右区间。需要解决的就剩下：如何高效表示和计算这些关于高度的函数。

分段多项式与批量外推

对于长度为 $m$ 的区间 $I$，只收集其中各个位置的 $A_i$ 和 $B_i+1$，排序去重，得到至多 $2m$ 个断点。

考虑相邻断点形成的高度块 $[c,d)$。当根高度 $x$ 遍历 $c,c+1,\ldots,d-1$ 时，每个位置是否允许取这个高度都保持不变。我们将 $F_I(x)$ 在整数点 $x=c-1,c,\ldots,d-1$ 上的值，用一个次数不超过 $m$ 的多项式表示。

注意，这个多项式的有效范围包含左端点 $c-1$。这样，转移里的 $F_L(x)$ 和 $F_R(x-1)$ 都能使用对应块上的同一份多项式表示，不需要因为出现 $x-1$，就不断给断点增加偏移量。

这个次数上界可以归纳证明。假设左右区间已经表示完毕，在当前块上分别选择其对应的多项式 $P_L$ 和 $P_R$。记允许作为根的位置集合为 $K_I(c)={k\in K_I:A_k\le c\le B_k}$，则差分右侧对应多项式 $G(x)=\sum_{k\in K_I(c)}P_{l,k-1}(x)P_{k+1,r}(x-1)$。

每一项的次数不超过 $(k-l)+(r-k)=m-1$，所以 $G$ 的次数不超过 $m-1$。对它做一次离散求和，就得到次数不超过 $m$ 的多项式；再加上一个常数，即可满足当前块左端点的边界值。

因此，每个区间只有 $O(m)$ 个多项式片段，每段次数至多 $m$，总表示规模为 $O(m^2)$。接下来要把每段的计算压到 $O(m\log m)$，而不是 $O(m^2)$。

所有片段都使用相同的绝对采样坐标 $0,1,2,\ldots$，不以各自的块左端点作为采样原点。

假设已经能直接取得子区间当前片段在 $0,1,\ldots,m$ 上的采样值。那么，每个 $G(t)$ 都只需要计算至多三个乘积，因而 $G(1),\ldots,G(m)$ 总共可以在线性时间内得到。

令 $Q(0)=0$，依次计算 $Q(t)=Q(t-1)+G(t)$，其中 $1\le t\le m$。这 $m+1$ 个值确定了一个次数不超过 $m$ 的多项式 $Q$，而且它确实满足 $Q(x)-Q(x-1)=G(x)$：等式两边的次数都不超过 $m-1$，并且在 $1,\ldots,m$ 这 $m$ 个点上相等。

设处理前面的高度块后，已经知道边界值 $\alpha=F_I(c-1)$。那么当前块的答案多项式就是 $P_I(x)=Q(x)+\alpha-Q(c-1)$，下一块需要的边界值则为 $P_I(d-1)$。

这里对 $Q(c-1)$ 和 $P_I(d-1)$ 的单点求值，都可以利用连续点拉格朗日插值，在 $O(m)$ 时间内完成。预处理阶乘、逆阶乘，再使用前缀积和后缀积即可，不需要逐个求逆，更不需要枚举两个端点之间的高度。

至此，在子区间采样值充足的前提下，构造当前片段只需要 $O(m)$ 时间。

有一个实现细节必须明确：存储的是当前片段对应的多项式在采样点上的值，不是原计数函数在这些采样点上的真实值。 例如，当前高度块可能位于 $10^8$ 附近，但仍然保存它的多项式在 $0,1,\ldots$ 上的代入值。即使块的长度小于多项式次数，也必须按同一份片段多项式外推，不能跑到其他高度块去查询真实计数值。

现在解决“子区间采样值是否足够”的问题。

一个长度为 $m$ 的区间，其片段多项式只需要 $m+1$ 个采样值就能确定，但它的父区间可能需要更多。设父区间长度为 $M$，另一个子区间长度为 $s$，由平衡条件可知 $s\le m+2$，所以 $M=m+s+1\le2m+3$。

因此，对每个长度为 $m$ 的区间，只要把每段多项式的采样值扩展到 $0,1,\ldots,\min(n,2m+3)$，就足以供它的所有可能父区间使用。空区间恒为 $1$，直接特殊处理。

扩展到的采样点数仍然是 $O(m)$，剩下的问题是如何批量计算，而不是对每个新点分别做一次线性插值。

设一个次数不超过 $m$ 的多项式 $P$ 已知采样值 $y_i=P(i)$，其中 $0\le i\le m$。定义 $a_i=(-1)^{m-i}y_i/(i!(m-i)!)$。对于任意新的整数采样点 $t>m$，拉格朗日插值可以写成：

$$ P(t) = \frac{t!}{(t-m-1)!} \sum_{i=0}^{m}\frac{a_i}{t-i}. $$

定义 $b_0=0$，$b_j=j^{-1}$，其中 $j\ge1$。上式中的求和恰好就是卷积 $a*b$ 的第 $t$ 项。

于是，做一次长度为 $O(m)$ 的卷积，再给每个结果乘上相应的阶乘因子，就能同时得到所有需要的新采样值，时间复杂度为 $O(m\log m)$。

这就是相对于逐点插值的实质性优化：逐点计算 $O(m)$ 个新值需要 $O(m^2)$，而批量外推只需要一次卷积。

综合起来，一个长度为 $m$ 的区间有 $O(m)$ 个片段。每段中，构造差分采样、做前缀和、计算两端的边界值都只需 $O(m)$，批量外推需要 $O(m\log m)$，所以整个区间的时间为 $O(m^2\log(m+1))$，空间为 $O(m^2)$。

为什么总复杂度是近二次

不能直接说“区间长度每次减半，所以总复杂度就是根区间的复杂度”。每个区间有至多三个候选根，最多会产生六个子区间；不同分支间还会共享状态。必须分析记忆化之后所有不同区间的总代价。

需要证明的核心结论是：所有实际访问的不同区间，其长度平方之和为 $O(n^2)$。

为了证明它，将位置区间改写成半开形式，初始区间为 $[0,n)$。一个合法根与区间中点的距离是常数，因此，实际产生的左右子区间，与理想的二等分结果相比，新边界只会多出常数大小的偏移。

固定一条长度为 $d$ 的“向左或向右”选择序列。如果每次都理想二等分，它对应一个确定的二进制划分区间；实际递归中，不论中间如何选择合法根，该区间的左右端点与理想位置的偏差都只有 $O(d)$。

这是因为每次新边界的误差，都是两个旧边界误差的平均值再加上一个常数；未改变的边界则保留原来的误差。因此每深入一层，最大端点误差只增加常数。

对于同一条左右选择序列，两个整数端点各有 $O(d+1)$ 种可能，故最多对应 $O((d+1)^2)$ 个不同区间。长度为 $d$ 的左右选择序列共有 $2^d$ 条，所以深度 $d$ 上至多出现 $O(2^d(d+1)^2)$ 个不同区间。

另一方面，子区间长度满足 $m'\le(m+1)/2$，因此非空递归只有 $O(\log n)$ 层，深度 $d$ 上的区间长度为 $O(n/2^d)$。由此得到：

$$ \sum_{\text{访问的不同区间 }I}|I|^2 \le O\!\left( \sum_{d\ge0}2^d(d+1)^2\left(\frac{n}{2^d}\right)^2 \right) = O\!\left(n^2\sum_{d\ge0}\frac{(d+1)^2}{2^d}\right) = O(n^2). $$

最后一个级数收敛。同一区间即使能在不同深度出现，上面的统计也只是将它重复计入上界；实际实现通过记忆化只计算一次。

因此，总时间为 $O(\sum_I |I|^2\log(|I|+1))=O(n^2\log n)$，总空间为 $O(\sum_I|I|^2)=O(n^2)$。收集并排序各区间断点、定位子区间对应的多项式片段，也都包含在这一时间上界中。

这里有两个实现条件不能省略。首先，每个区间只使用自身位置产生的断点，不能统一扩成全局的所有高度块之后，仍然沿用每个区间只有 $O(m)$ 段的分析。其次，必须记忆化区间状态，而不是把不同根选择产生的递归分支全部独立展开。

模数也需要正确处理。题目要求对 $10^9+7$ 取模，因此卷积应使用任意模数卷积，不能直接把答案模数换成常见的 NTT 模数。 下面的实现使用三个 NTT 模数进行卷积，再通过 CRT 还原到目标模数；小规模外推使用固定阈值的朴素计算来减小常数，不改变渐近复杂度。

最终算法达到的是 $\widetilde O(n^2)$ 的可实现上界。