延迟决策技巧

一个经典的贡献就是 mex，按什么顺序决策都有可能出现先 $1$ 后 $0$ 导致 mex 直接变到 $2$。但是 mex 随着出现的数的集合扩大，显然是单调不降的。而且若决策一个数 $<\text{mex}$ 是不会影响 mex 的。

例一：P7213

先考虑按什么顺序。显然要么按值域来看，要么按顺序来看。但是如果按值域来看需要同时处理两个位置，所以我们考虑按顺序。那是从前往后还是从后往前呢？注意前面的数是否会减少，要依赖后面的数，所以我们应该从后往前、这样记录的信息就可以判定当前数要怎么减少。

然后来考察性质。首先如果后面出现了一个数 $x$，那么前面的数不可能等于 $x$。进一步观察，我们发现操作其实可以不看作是每一轮都对整体操作，而是转为：从后往前扫，只要当前的数后面出现过就 $-1$，直到变成 $0$ 或者后面没有。扫完了就得到最终的结果。

所以一个数 $x$ 要变成 $0$，等价于后面 $1\sim x$ 都出现了。那么我们可以大致得出一个数如果填 $x$ 就有两种可能：

那么难点就在于我们怎么判断 $1\sim x$ 里有没有漏的。如果具体决策每个数等于几，那就难以避免状态每个数是否出现。但是此时发现有一个单调性：如果已经连续出现了 $1\sim x$，那么未来连续出现的上限只会比 $x$ 大。所以决策一个数为 $\le x$ 不会改变这个连续高度，而决策 $>x$ 有可能改变。

把当前后缀里的数分为两个部分：$1\sim h$、$\ge h+2$ 的数。考虑在 DP 过程中记录连续出现的高度，决策下一个数是 $\le h$ 还是 $\ge h+2$，前者立刻算贡献，后者待定。当 $h$ 发生变化时，决策待定的元素里有哪些要被确定。

设 $dp(i,h)$ 表示 $i\sim n$ 的高度决策好了，最大连续出现高度为 $1\sim h$ 的方案数。

此时我们应该要预见到（或者在下面推的时候碰到）：一种高度只有两个名额，当剩下两个名额或者一个名额，可以做 $1$ 的贡献；如果不剩下名额，就做 $0$ 的贡献。而从两个名额变成一个名额、和从一个名额变成没有名额，这两种变化是本质不同的！所以难道我们要额外记录有多少个高度是两个名额的吗？

这样做复杂度肯定爆炸了。考虑上面遇到的问题，我们可以认为相等的两个数也是有区分的，最终给答案除以 $2^n$。这样有两个名额的贡献系数就是 $2$，从而转为有多少个名额可选，贡献系数就是多少。

然后考虑转移到 $i-1$。设 $i\sim n$ 里有 $p_i$ 个要变成 $0$，$q_i=n-i+1-p_i$ 个要留下。

转移即可，复杂度 $O(n^3)$。不要忘记最终除以 $2^n$。

在本题中，单调的标准即 "连续出现高度 $h$"。如果决策 $\le h$，不会改变 $h$；而决策 $\ge h+2$ 可能在后面改变 $h$，也可能不会影响。于是待定后者的决策即可。

例二：P14364

把计数排列看作天和人的匹配。按值域考虑每个人和哪个匹配。大致为 $dp(i,j)$ 表示 $c\le i$ 的人里有 $j$ 个面试失败的方案数。

然后就发现当决策一个人面试失败的时候并不只涉及 $c$ 比它小的人，因为可以让一个 $c$ 大的人遇到 $0$，所以还要额外记录后面有多少个人面试失败了。

为了避免记录每个人的状态，我们要考虑这个单调的标准，从而把同属于 "确定" 或 "待定" 的人能同类看待。

把 $(i,c_{p_i})$ 在坐标系上画成柱状图，画一条左下到右上的折线表示每一天的失败人数变化。这样就容易看出因为折线是单调向上的，所以在某次折线达到 $x$ 的高度后，之后耐心值 $\le x$ 的人都不可能被录取，而 $>x$ 的人只要放在 $1$ 的位置就一定会被录取。这就是单调的标准。

所以考虑把人分作耐心值 $\le x,>x$ 考虑。因为 $x$ 是单调上升的，所以过程中会有一些 $>x$ 的人进入 $\le x$，但是 $\le x$ 的永远会 $\le x$。所以 "$\le x$ 的人" 是确定的部分，"$>x$ 的人" 是不确定的部分。考虑设 $dp(i,j,k)$ 表示决策前 $i$ 天的安排、有 $j$ 个人失败、有 $k$ 个位置的人耐心值 $>j$（等待后面决策），在 $dp$ 里只决策前 $i$ 天耐心值 $\le j$ 的方案数。

使用刷表法转移。考虑第 $i+1$ 天的人是要失败还是要通过。记 $cnt_i$ 表示耐心值为 $i$ 的人数，$sc$ 为 $cnt$ 的前缀和。

虽然看起来要枚举 $w$ 是 $O(n^4)$ 的，但因为总人数 $O(n)$，所以 $w$ 一共只能枚举 $n$ 次。故总复杂度是 $O(n^3)$ 的。

例三：CF1608F

考虑转换计数对象，令 $s_i$ 为 $a$ 的前缀 $\text{mex}$ 数组，对 $s$ 计数再考察一个 $s$ 可以对应多少个 $a$。

对于 $s$，显然应该有 $s_i\le i$ 和 $s_i\le s_{i+1}$ 和 $s_i\in [b_i-k,b_i+k]$。

考虑固定 $s$ 后 $a$ 有多少种选取方案。手玩一下，首先能发现一个简单的性质：$s_i\neq s_{i+1}$ 时，$a_{i+1}=s_i$。于是这启示我们把 $s$ 分成若干个相等段来考虑。

于是设划分的结果是 $[l_1=1,r_1],[l_2=r_1+1,r_2],\dots,[l_k,r_k=n]$。每段内的 $s$ 都相等。那么有：

感受一下，以上的条件已经充分了。所以开始 DP：因为有 $\text{mex}$ 运算，所以采用延迟决策、记录待定位置数的方法，$f(i,j,k)$ 表示前 $i$ 个位置，$s_i=b_i+j$，有 $k$ 个位置上的 $a$ 是没确定的（$>s_i$ 的个数），方案数。

考虑转移。枚举下一位 $s_{i+1}=b_{i+1}+p$（$p\in [-k,k]$）：

就算假设那个系数可以 $O(1)$ 求，状态是 $O(n^2k)$ 的，枚举 $s_{i+1}$ 是 $O(k)$ 的，若 $s_i<s_{i+1}$ 还要枚举放多少个下来还是 $O(k)$ 的。复杂度是 $O(n^2k^3)$ 起步，肯定过不了，必须优化。

接下来是一个很有道理但是很巧妙的想法：$\text{mex}$ 只关心每种数是否出现过，那如果我们待定的方式是有 $k$ 种数是 $>s_i$ 的，就非常方便了。所以我们改设 $f(i,j,k)$ 表示前 $i$ 个 $s_i=j$ 有 $k$ 种数待定。

那么 $s_i=s_{i+1}$ 时，$a_{i+1}$ 可以选择新开一种或者选择等于旧的一种。而 $s_i<s_{i+1}$ 时只需要从 $k$ 种里选 $s_{i+1}-s_i-1$ 种就行了！

所以更改了一下定义，轻松就做到了 $O(n^2k^2)$。但是这个复杂度还是过不了。继续优化。写出转移式子：

现在来优化。前两条不用优化，看看第三条是什么东西，发现枚举 $j'$ 完全不如直接枚举 $b_{i+1}+j'-(b_i+j)-1$。重写一下就是 $f(i,j,k)$ 会转移到 $f(i+1,j+c,k-c)$ 这条斜线上。用个前缀和优化即可。

upd：有一个聪明的方法可以不用前缀和优化。我们不用 "一次性" 决定好 $\text{mex}$ 要增长到哪里。可以认为 $\text{mex}$ 有两种增长方式：在 $a_i$ 放一个 $\text{mex}$，或者在目前待定里取一种放 $\text{mex}$。所以可以写成 $f(i,j,k)\leftarrow f(i-1,j-1,k)+f(i,j-1,k+1)\times (k+1)$。

例四：图灵杯第七届高级组T1 棋无常树

令 $mxb_i$ 为 $i$ 子树内 $b_i$ 的最大值，则赋值后 $i$ 子树内 $0\sim mxb_i-1$ 都应该出现过。同时 $i$ 子树内 $a\neq -1$ 的数也确定出现过。定义 $vis_{i,j}=0/1$ 表示 $i$ 子树内数 $j$ 是否出现过。

定义 $f_{i,j,k=0/1}$ 表示在 $i$ 子树内填 $a$，使得 "$\neq mxb_i$ 且不确定是否出现过的数里" 有 $j$ 种不同的数，且 $mxb_i$ 没有出现/出现了 的方案数。所以这个状态实际上把数分成了三类：确定的数、不确定的数、$mxb_x$，在转移时就要让这三类数指代的对象统一了才能转移。

考虑合并 $x$ 和其子树 $i$，为了方便起见，不妨 $mxb_x\ge mxb_i$。记 $sz_u$ 为当前 $u$ 子树内有多少个 $a=-1$ 的，也就是 $f$ 数组的第二维在有意义的前提下最高取到多少。

因为 $f$ 的定义是基于 $vis$ 的，第一个任务是合并 $f_x,f_i$ 的 $vis$。

当我们发现 $vis_{x,p}=1,vis_{i,p}=0$ 时，我们要把 $vis_{i,p}$ 改成 $1$，那这会对 $f_i$ 有什么影响？$p$ 本来在 $i$ 的视角下属于 "不确定是否出现过的数"，现在变成确定出现的了。所以：

也就是从 $j+1$ 个不确定的里面选一个 $p$ 出来变成确定的，这样更新一次是 $O(sz_i)$ 的。$vis_{x,p}=0,vis_{i,p}=1$ 的同理对 $f_x$ 更新，一次 $O(sz_x)$。

这个操作会经常出现，我们称它为 trans。可以发现，当有一个新的确定数出现，为了确保不确定数和确定数之间没有重复，就需要做一次 trans。

然后 $vis_x,vis_i$ 相等了，开始合并 $f_x,f_i$。为了方便，搞一个 $g_{j,0/1}$ 作为临时数组，$f_x*f_i$ 先放到 $g$ 里面，转移完了再从 $g$ 复制回 $f_x$。

我们终于合并了所有子树，太好了！但是现在还需要把 $x$ 的影响加入 $f_x$ 内。这又要根据 $a_x,b_x$ 分类讨论。令 $s$ 表示 $x$ 子树内有多少种确定的数会出现（$s=\sum_i vis_{x,i}$）。

于是 DP 的部分结束了，怎么计算答案？

令 $s=n+1-\sum_i vis_{1,i}-(mxb_1\neq -1)$，那么 $s$ 就是不确定数的选择范围。

然后是复杂度分析。

因此总复杂度 $O(n^2)$。