题解

思路

把 $x$ 平移为 $0$ 不会改变递增子序列。沿着折线行走时，记当前位置为 $s$，此前到达过的最小位置为 $m$。从一次出现 $m$ 的位置开始，之后依次选择 $m,m+1,\ldots,s$，一定能得到长度 $s-m+1$ 的递增子序列；反过来，任何严格递增子序列的末项与首项之差至少为长度减一。因此最长长度为

这里的 $D$ 可在扫描 $d$ 的前缀和时求出。

接着考虑计数。每当路径降到新的全局最小值，就开始一个新的“纪元”。在一个纪元内，以当前最小值为高度 $0$，所有高度都非负。令 $f_k$ 表示已经扫描的前缀中，恰好依次选出高度 $0,1,\ldots,k$ 的方法数。

新访问高度 $k>0$ 时，可以把这次访问接在任意一种选出 $0,1,\ldots,k-1$ 的方案后，所以执行

再次访问高度 $0$ 时，它本身构成一种新的起点，所以执行 $f_0\leftarrow f_0+1$。每个纪元结束时把 $f_D$ 加入答案。若 $D=0$，每个元素自身都是最长子序列，答案直接为序列 $p$ 的长度。

不能逐个展开最多 $5\times 10^{10}$ 次移动。观察一次向上长段会在一段连续下标上依次做前缀和；一次向下长段则会在一段连续下标上同时做 $f_k\leftarrow f_k+f_{k-1}$。初始数组在区间上是常数多项式，而前缀和使次数至多增加一，同步相邻求和不增加次数。总共只有 $n$ 个长段，因此所有 $f_k$ 可以维护成若干段低次多项式。

做法

用若干互不相交的闭区间覆盖 $[0,D]$。每个区间保存其多项式在连续 $n+3$ 个整数点上的值；用拉格朗日插值可以在 $O(n)$ 时间求该多项式在任意整数点的值。

处理一个长段前，先在操作区间的左右端点切开已有分段。

• 向上经过高度区间 $[l,r]$ 时，从左到右处理每个分段。对该段保存值做前缀和，并把左侧的累计值作为常数加入；段末值成为下一段的累计值。
• 向下经过高度区间 $[l,r]$ 时，先保留旧分段快照。每段左端单独切成一个点，其新值由旧左端值和旧的前一高度值相加；剩余部分对应多项式 $P(t+1)+P(t)$。高度 $0$ 的额外来源按加一处理。
• 若下降越过当前纪元的高度 $0$，先把当前 $f_D$ 加入答案，再以新的全局最小值重新建立初始状态。

分段端点只会来自输入的前缀位置，每次操作产生的分段数是多项式级别；多项式次数不超过 $n$。所有运算都对 $998244353$ 取模。长度 $D+1$ 用 64 位整数保存。

正确性来自三个不变量：$D+1$ 等于最长长度；$f_k$ 始终精确统计当前纪元内选出连续高度 $0$ 到 $k$ 的方案；分段多项式维护与逐点递推完全等价。各纪元互不重叠，累加所有纪元的 $f_D$ 恰好得到全部最长子序列个数。

复杂度

设 $n\le 50$。分段数量为 $O(n^2)$，一次插值求值为 $O(n)$，总时间复杂度为 $O(n^4)$，空间复杂度为 $O(n^3)$。