[R82F] 擂台

数据规模：$1 \le n \le 500$，$1 \le a_i \le 10^9$，所有 $a_i$ 两两不同。

思路

把比赛过程看成合并树。 每次「从当前队伍里选相邻两人比赛」，等价于把两个相邻连续段合并成一个连续段，胜者是两段的最大值（最大值不会被打败）。于是整场比赛对应一棵二叉树：叶子是 $n$ 名选手，按初始编号从左到右排列，每个内部结点合并两个相邻的连续段，其胜者就是该段的最大值。反过来，任意一棵这样的二叉树都可以自底向上依次执行合并，因此「比赛过程」与「区间上的二叉树」一一对应。

记录只由树决定。 在一个合并结点处，两侧胜者中实力较弱的那位此时被淘汰，于是它的 $b$ 值等于另一位的编号；其余选手的 $b$ 值早已确定。所以记录与合并的先后次序无关，只由树的形状决定。

围绕最大值拆分。 设区间 $S=[l,r]$ 的最大值在位置 $p$（它必然是整个区间的胜者）。在 $S$ 对应的树中，从根出发一直走「包含 $p$ 的那个子结点」，得到一条通向叶子的链。链上每次向下，都等于把与当前区间相邻的一段连续块吸收进来：$p$ 左侧的选手被切成若干连续块，从右往左依次吸收；右侧同理，从左往右依次吸收。两侧块的吸收顺序可以任意交错，但交错不影响记录内容。每一块的胜者（即该块的最大值）都是在被吸收的那一刻被 $p$ 淘汰的，所以这些位置的 $b$ 值都等于 $p$。

因此，若把区间胜者的 $b$ 值看成一个外部占位符，整个区间的记录就由「左部怎么分块 + 右部怎么分块 + 每个块内部的记录」唯一决定。

不重不漏。 固定区间与固定一侧（左部或右部），两种不同的分块一定给出不同的记录。取两者最左的分歧点 $x$：两种分块都在 $x$ 处开始新块，一块是 $[x,y]$，另一块是 $[x,y']$，不妨 $y'<y$。在后一种分块里，从 $y'+1$ 开始还有一块，设其胜者为 $r$，则 $r\in[y'+1,y]$ 且 $b_r=p$。若在前一种分块里 $r$ 不是 $[x,y]$ 的最大值，则那里的 $b_r\ne p$，两者已不同；若 $r$ 正是 $[x,y]$ 的最大值，则取后一种分块中 $[x,y']$ 的胜者 $q$，它满足 $q<r$，于是前一种分块里 $b_q\ne p$，也一样能区分。而分块固定时，各块的下标集合互不相交，块内记录不同必然导致整体记录不同。所以选择可以相乘、按分块求和。

状态与转移。 区间统一取左闭右开 $[l,r)$：

• $g(l,r)$：区间 $[l,r)$ 上能产生的不同记录数，其中该区间胜者的 $b$ 值是固定的占位符；
• $f(l,r)$：把 $[l,r)$ 切成若干连续块，并给每块选一份记录（每块胜者的 $b$ 值都是同一个外部下标）的方案数，即对所有分块求 $\prod g(\text{块})$ 之和。

设 $p$ 为 $[l,r)$ 中最大值的位置，则左右两侧各自独立分块：

$g(l,r)=f(l,p)\cdot f(p+1,r).$

$f$ 按「最后一块」枚举切点：

$f(l,r)=\sum_{k=l}^{r-1} f(l,k)\cdot g(k,r),\qquad f(l,l)=1.$

答案是 $g(1,n)$：全区间胜者是全局最大值，它的 $b$ 值必须为 $0$，正对应占位符。

计算顺序。 按区间长度从小到大递推。$g(l,r)$ 只用到两个更短的 $f$；$f(l,r)$ 用到 $f(l,k)$（更短）与 $g(k,r)$，其中 $k=l$ 的那一项就是刚算出的 $g(l,r)$，所以对每个状态先算 $g$ 再算 $f$ 即可。

检验。 当 $a$ 单调时，分块只能逐块收缩，答案恰为卡特兰数 $C_{n-1}$（$n=3$ 时为 $2$，而样例 2 的序列 $\{1,3,2\}$ 只有 $1$ 种记录）。可以把这一点当作实现的对照检查。

复杂度

共有 $O(n^2)$ 个状态，每个 $f$ 状态枚举 $O(n)$ 个切点，时间 $O(n^3)$；存储 $f,g$ 以及区间最大值位置表，空间 $O(n^2)$。

仓颉实现

二维表按一维数组存储，下标为 $l\cdot(n+1)+r$。区间取左闭右开后，空区间的 $f$ 值自然为 $1$，不需要额外判空。

import std.env.*
import std.convert.*

main() {
    let n = Int64.parse(getStdIn().readln().getOrThrow())
    let a = getStdIn().readln().getOrThrow().split(" ", removeEmpty: true).map({ p: String => Int64.parse(p) })
    let MOD: Int64 = 998244353
    let w = n + 1
    let sz = w * w
    let mx = Array<Int64>(sz, { _ => 0 })
    for (l in 0..n) {
        var best = l
        for (r in (l + 1)..=n) {
            if (a[r - 1] > a[best]) {
                best = r - 1
            }
            mx[l * w + r] = best
        }
    }
    let f = Array<Int64>(sz, { _ => 0 })
    let g = Array<Int64>(sz, { _ => 0 })
    for (l in 0..=n) {
        f[l * w + l] = 1
    }
    for (len in 1..=n) {
        for (l in 0..=(n - len)) {
            let r = l + len
            let p = mx[l * w + r]
            g[l * w + r] = f[l * w + p] * f[(p + 1) * w + r] % MOD
            var s: Int64 = 0
            for (k in l..r) {
                s = (s + f[l * w + k] * g[k * w + r]) % MOD
            }
            f[l * w + r] = s
        }
    }
    println(g[n])
}