官方题解只能做到 $O(N^2)$？玩的太差了。题目统计的是不同的最终序列而非不同的操作顺序,两问分别求零位置 $b_i$ 之和的最大值,以及零位置 $c_i$ 之积对所有最终序列的求和。记 $B_{\mathrm{all}}=\sum_{i=1}^n b_i$、$C_{\mathrm{all}}=\prod_{i=1}^n c_i\bmod P$,则对最终序列 $D$ 有 $f(D)=B_{\mathrm{all}}+\sum_{d_i>0}(-b_i)$、$g(D)=C_{\mathrm{all}}\prod_{d_i>0}c_i^{-1}\bmod P$,于是可以改为只给非零位置赋权 $W_i=(-b_i,c_i^{-1})$,零位置不产生权值。为了把两问一起描述,定义 $(m_1,z_1)\oplus(m_2,z_2)=(\max(m_1,m_2),\,z_1+z_2)$ 与 $(m_1,z_1)\otimes(m_2,z_2)=(m_1+m_2,\,z_1z_2)$(第二分量均在模 $P$ 意义下),零元与幺元分别为 $\mathbf0=(-\infty,0)$、$\mathbf1=(0,1)$;$\oplus$ 表示合并两类不同的方案,$\otimes$ 表示拼接权值。注意第二分量是所有方案的权值和,不是达到第一分量最大值的方案数:即使两个方案的第一分量不同,第二分量也照常相加。下文所有 DP 都使用这套运算,最终若得到 $V_n=(M,Z)$,答案即为 $B_{\mathrm{all}}+M$ 与 $C_{\mathrm{all}}Z\bmod P$。

设 $V_i$ 为原序列前 $i$ 项的答案,$V_0=\mathbf1$;设 $F_i(x)$ 为序列 $[a_1,\ldots,a_{i-1},x]$ 的答案,其中末位的权值仍取 $W_i$,于是 $V_i=F_i(a_i)$、$F_i(0)=V_{i-1}$;再设 $H_i(y)$($y>0$)表示前 $i$ 项中所有满足 $d_i=y$ 的最终序列的权值汇总,但暂不计入位置 $i$ 自己的权值 $W_i$——引入 $H$ 正是因为位置 $i$ 日后若被消成零,它本就不该产生 $W_i$。

先看 $F_i(x)$ 中最终 $d_i>0$ 的情况,按是否对最后一条边做过有效操作分为两类。没有操作时 $d_i=x$,前 $i-1$ 项可为任意可达状态,贡献 $W_i\otimes V_{i-1}$;有操作时,设操作前位置 $i-1$ 的值为 $z$,由末项非零知 $0< z< x$,操作后最后两项变为 $(0,x-z)$,而这次操作总可以放到所有其他操作之后:它把位置 $i-1$ 变成零,此后任何涉及 $i-1$ 的操作都不再有效,其他位置的操作则可以提前,故贡献 $W_i\otimes\bigoplus_{0< z< x}H_{i-1}(z)$。这里没有重计,因为由最终的 $d_i$ 可唯一恢复 $z=x-d_i$,进而唯一恢复操作前的前缀最终状态。顺带得到 $H$ 的转移:

• $H_i(y)=V_{i-1}$ 当 $y=a_i$,$H_i(y)=H_{i-1}(a_i-y)$ 当 $0< y< a_i$,其余为 $\mathbf0$ (1);

也就是说 $H$ 的维护只有三件事——保留旧函数中 $0< y< a_i$ 的部分、做一次反射 $y\mapsto a_i-y$、再在 $a_i$ 处加入权值为 $V_{i-1}$ 的点。

另一个关键性质是:当初始末项为 $x>0$ 而最终末项为零时,最后一条边上的有效操作可以放到最开始。这次操作必须减去 $x$,故先要 $x\le a_{i-1}$;先做它,序列变为 $[a_1,\ldots,a_{i-2},a_{i-1}-x,0]$,之后只需处理前 $i-1$ 项。提前它不会破坏可达性:位置 $i-1$ 除最后一条边外只能与位置 $i-2$ 发生一次有效操作,若它原本在最后一条边之前且从位置 $i-1$ 减去 $u$,由之后仍须减去 $x$ 知 $a_{i-1}-u\ge x$,即 $a_{i-1}-x\ge u$,所以先减 $x$ 再执行原操作仍然合法,其他操作不受影响。因此“末项最终为零”的最终序列与修改后前缀的最终序列一一对应,贡献为 $F_{i-1}(a_{i-1}-x)$。定义 $K_i(t)=F_i(a_i-t)$($0\le t\le a_i$),$K_i(t)=\mathbf0$($t>a_i$),这一类贡献恰为 $K_{i-1}(x)$。合并得:

• 对 $x>0$,$F_i(x)=W_i\otimes\bigl(V_{i-1}\oplus\bigoplus_{0< z< x}H_{i-1}(z)\bigr)\oplus K_{i-1}(x)$ (2)。

两大类按最终末项是否为零划分,互不相交,每类内部又是一一对应,因此统计的确实是最终序列而不是操作历史。

把 (2) 中的 $x$ 换成 $a_i-t$,并由 (1) 知当 $0\le t< a_i$ 时 $\bigoplus_{y>t}H_i(y)=V_{i-1}\oplus\bigoplus_{0< z< a_i-t}H_{i-1}(z)$,即得

$$K_i(t)=K_{i-1}(a_i-t)\oplus W_i\otimes\bigoplus_{y>t}H_i(y)$,$0\le t\le a_i \; (3)$$

该式在 $t=a_i$ 时也成立:此时后缀为空,而 $K_{i-1}(0)=V_{i-1}=F_i(0)$。取初始状态 $H_0=\varnothing$、$K_0(0)=\mathbf1$、$K_0(t)=\mathbf0$($t>0$),每轮末尾读 $V_i=K_i(0)$。于是每加入一个位置只需:取 $v=K(0)$;把旧 $K$ 限制到 $[0,a_i]$、旧 $H$ 限制到 $(0,a_i)$,并统一反射 $t\mapsto a_i-t$;在新 $H$ 的 $a_i$ 处加入权值 $v$;对每个 $t\in[0,a_i]$ 令 $K(t)\leftarrow K(t)\oplus W_i\otimes\bigoplus_{y>t}H(y)$;最后 $V_i=K(0)$。

断点只有线性多个:由 (1),$H_i$ 每轮只保留一部分旧点再新增一个点;由 (3),$K_i$ 是分段常值函数,且断点包含于 $\{0\}\cup\operatorname{supp}(H_i)$。更具体地,把 $0$ 也当作一个权值为 $\mathbf0$ 的特殊点维护,则每轮旧的 $0$ 经反射变成新的 $a_i$,只需把它的 $H$ 权值改为 $V_{i-1}$;裁剪边界 $a_i$ 经反射变成新的 $0$,仅当该边界原本不存在时才新建一个点。所以每轮至多新建一个断点,整个算法只创建 $O(n)$ 个断点,被裁掉的断点也只会被删除一次。

等号必须单独处理:$H$ 保留的是 $0< y< a_i$,而 $K$ 保留的是 $0\le t\le a_i$,也就是旧 $H(a_i)$ 要删除,旧 $K(a_i)$ 必须保留——前者不能作为“末项仍非零”的转移,后者恰好处理两个数同时变成零的情形。因此每个断点必须分别保存该点处的 $E_j=K(\text{断点})$ 与相邻断点之间开区间上的函数值,不能只存一份阶梯函数值。例如 $A=[a,a]$ 时应得 $V_2=(W_1\otimes W_2)\oplus\mathbf1$,分别对应“不操作”和“两数同时归零”,而全零状态只能计一次。

反射的开销可以先去掉:不真正修改断点坐标,而是维护 $t=\varepsilon z+\delta$($\varepsilon\in\{1,-1\}$),其中 $z$ 是断点在数据结构中按升序排列的固定坐标,$t$ 是当前实际坐标,则反射 $t\mapsto a_i-t$ 只需令 $\varepsilon\leftarrow-\varepsilon$、$\delta\leftarrow a_i-\delta$,函数值仍挂在原节点上无需移动。这时裁掉实际坐标大于 $a_i$ 的点只会从物理顺序的一端连续删除,新裁剪边界也只插入同一端;实际坐标上的后缀在 $\varepsilon=1$ 时对应物理后缀,在 $\varepsilon=-1$ 时对应物理前缀。至此已经没有任意位置的插入、删除、查询,只剩下双端队列两端的操作与整队列的前缀/后缀贡献更新——用平衡树维护即得 $O(n\log n)$,但这个 $\log n$ 还能去掉。

按物理坐标从小到大编号,设节点 $j$ 保存该断点的 $H$ 权值 $h_j$、该断点上的 $K$ 值 $E_j$,以及该断点右侧到下一个断点之间的 $K$ 值 $R_j$;允许对一整段节点打三个标记 $(p,s,c)$,含义是

$$E_j\leftarrow E_j\oplus p\otimes\bigoplus_{k< j}h_k\oplus s\otimes\bigoplus_{k>j}h_k\oplus c \; (4)$$

与

$$R_j\leftarrow R_j\oplus p\otimes\bigoplus_{k\le j}h_k\oplus s\otimes\bigoplus_{k>j}h_k\oplus c \; (5)$$

开区间右侧的前缀包含当前点,故 (5) 用 $k\le j$,断点自身用严格前缀 $k< j$。我们需要的整段更新就是 $(p,s,c)=(\mathbf0,W_i,\mathbf0)$ 或 $(W_i,\mathbf0,\mathbf0)$。在 $h_j$ 不变时,两次更新只需把三个标记分别 $\oplus$ 起来即可合并,这只用到 $\otimes$ 对 $\oplus$ 的分配律,而最大值与加法、求和与乘法都满足它。下传时,设一段分为左右两部分 $X,Y$,记 $H_X=\bigoplus_{j\in X}h_j$、$H_Y=\bigoplus_{j\in Y}h_j$,则 $Y$ 的权值全属于 $X$ 中节点的后缀、$X$ 的权值全属于 $Y$ 中节点的前缀,于是父标记 $(p,s,c)$ 传为

$$X:(p,s,\,c\oplus s\otimes H_Y) \; (6) $$

与

$$Y:(p,s,\,c\oplus p\otimes H_X) \; (7)$$

这就是整个数据结构的核心。改变某个 $h_j$ 之前要先下传相关旧标记,保证历史更新仍用历史权值,而不会被新的 $h_j$ 重新解释。

用两个栈表示双端队列,左栈栈顶为队首、右栈栈顶为队尾;每个栈节点除自己的 $h,E,R$ 外还保存它及其下方所有节点的 $H$ 汇总与三个懒标记。把一个栈看成“栈顶节点”与“剩余栈”两部分即可直接套用 (6)、(7),于是对一个栈而言:整栈打标记只需更新栈顶函数值并累积标记,$O(1)$;弹出或修改栈顶只需向剩余栈下传一次标记,$O(1)$;压入新节点只需算一次新的汇总值,$O(1)$。整条双端队列是“左栈 + 右栈”,故对整队列打前缀或后缀贡献标记也只需对两个栈顶各处理一次,同样 $O(1)$。当需要访问队首而左栈为空(或访问队尾而右栈为空)时,把现有节点的懒标记依次下传、取出所有节点、按物理顺序分成大致相等的两半重建两个栈,有 $m$ 个节点时花费 $O(m)$,但这是摊还常数的:取势能 $\Phi=C\bigl||L|-|R|\bigr|$($C$ 为足够大的常数),普通双端插入删除只让势能改变 $O(1)$,而重建前一边为空、势能为 $Cm$,重建后降到 $O(1)$,足以支付重建费用,只有一个节点的情形本来就是常数开销。因此双端访问、插入、删除、修改都是摊还 $O(1)$,整队列更新是 $O(1)$;这里不需要排序,也不需要二分寻找裁剪位置,直接从对应一端不断弹出实际坐标大于 $a_i$ 的节点即可,而由于总共只创建 $O(n)$ 个断点,所有这类弹出累计也只有 $O(n)$ 次。

整体流程为:初始化一个实际坐标为 $0$、$H$ 权值为 $\mathbf0$ 的节点,$K(0)=\mathbf1$,$V_0=\mathbf1$;对 $i=1..n$,先从实际坐标较大的一端删除所有坐标 $>a_i$ 的节点,保留或补出坐标 $a_i$ 处的节点(保留其 $K$ 值、把其 $H$ 权值清零),把旧坐标 $0$ 处的 $H$ 权值改成 $V_{i-1}$,做一次懒反射 $t\mapsto a_i-t$(新定义域之外的区间值按 $\mathbf0$ 处理),再整队列执行 $K(t)\leftarrow K(t)\oplus W_i\otimes\bigoplus_{y>t}H(y)$,并读出 $V_i=K(0)$;最后由 $V_n$ 还原题目要求的两个答案。每轮只有常数次双端操作与一次整队列更新,额外删除的节点总数为 $O(n)$,故函数 DP 的维护时间为 $O(n)$、空间为 $O(n)$;所有 $c_i^{-1}$ 可用前缀积配合一次快速幂批量求出,耗时 $O(n+\log P)$。因此总复杂度为时间 $O(n+\log P)$、空间 $O(n)$,固定模数下即两问同时线性时间。

提交记录：https://qoj.ac/submission/2932920 。NOI 题就是简单。