尝试学了一下D题的第二个通过代码，感觉比题解简单很多。如果用$\, f_n(i) \,$表示所有长度为$\, n \,$，最后一个数字为$\, i \,$，且后面再加上$\, i + 1, i + 2, \cdots, m \,$后是一个合法串的方案数。那么转移矩阵$\, f_{n+1} = A f_n \,$满足$\, A_{ij} = [i = 1] \mid [j = 1] \mid [i = j + 1] \,$。如果暴力维护$\, f_n \to f_{n+1} \,$的过程，复杂度是$\, O(m) \,$每次。但是注意到$\, f_{n+1}(m) - f_n(m - 1) = \cdots = f_{n+1}(2) - f_n(1) = f_n(m) \,$，所以只需要用滑窗单独维护$\, f_{n+1}(1) \,$，剩余部分shift一下，再维护一下差值就行。
2021.1 月赛题解
Once edited 3 年，3 月前
本次 EOJ 月赛由华东师范大学 ACM 团队与华东师大二附中信息学竞赛组联合举办。首先，感谢以下同学为本次月赛命题做出的贡献：
命题人：blunt_axe
验题团队：zbww、ssshwy、RainAir、Kilo_5723、Xiejiadong、jhdonghj112、xryjr233、Once、bingoier
感谢华东师范大学肖春芸老师、华东师范大学第二附属中学金靖老师周密的组织策划，使得 EOJ 月赛能够圆满完成。此外，感谢 EOJ 运维团队为月赛提供了重要的技术支持。
最后，祝各位 ACMer 和 OIer 们元旦快乐，学业有成。
扫描二维码关注我们的微信公众号，获得更多信息。本次月赛的获奖名单和后续竞赛通知将通过公众号发布。
预计难度顺序：A < E < C < B < D < F。
A 逆十字
发现每个 “逆十字” 唯一对应一个只有五个格子的小十字，所以只要数出小十字的个数即可。
B 洪水
考虑终点 $(c, d)$ 未被淹没的最晚时刻 $T$。我们可以证明，以 $(a, b)$ 为起点的最晚出发时刻是 $T - |a - c| - |b - d|$。换句话说， Cuber 出现后可以沿着最短路径不停地走，并且到达终点后的下一时刻终点被淹没。
为什么一定可行呢？考虑 $t$ 时刻 Cuber 站在 $(x, y)$ 的情况。因为此时 $(x, y)$ 未被淹没，所以在 $t - 1$ 时刻 $(x, y)$ 的相邻格子也未被淹没（如果某相邻格子在 $t - 1$ 时刻被淹没，那么 $(x, y)$ 必会在 $t$ 时刻被淹没，故矛盾）。所以，如果 “时光倒流”，Cuber 就能自由移动，我们就能轻易推得上述结论了。
时间复杂度 $O(nq)$，可优化到 $O((n + q) \log n)$。
C 魔树
发现一个 D 操作恰好抵消前面的一个 A 操作。维护一个 “操作栈”，碰到操作后：
- 如果是
A操作，那么向栈中加入这个操作； - 如果是
D操作且栈非空，弹出栈顶； - 如果是
D操作且栈为空，不对栈操作并把原树的所有叶子删除。
在（删去几层叶子后的）原树基础上，再依次执行栈中的 A 操作，就能得到最终的树。因为转化后只有 A 操作，所以结点数比较好算。
有个问题就是如何删除叶子。可以选择从下到上、类似拓扑排序的方法。也可以对于每个点算出：它到子树中最远叶子的距离。这个值加上 $1$ 直接代表了它属于第几层叶子，所以删叶子时不用真的删，记录一下总共删叶子的层数即可。
D 区间替换
记 $\texttt{F}$ 为 $[1, 2, \cdots, m]$，$\texttt{P}$ 为 $\texttt{F}$ 的一个真前缀，$\texttt{S}$ 为 $\texttt{F}$ 的一个真后缀，$\texttt{R}$ 为 $[2, 3, \cdots, m - 1]$ 的一个子段。
发现：合法的数组一定能由这四个基本的东西拼成，例如：
$$
\mathtt{PP\cdots P \ F \ SS\cdots S \ R \ PP\cdots P \ F \ SS\cdots S}
$$
进一步地，有如下规律：
- 开头必须是 $\texttt{F}, \texttt{P}$；
- 结尾必须是 $\texttt{F}, \texttt{S}$；
- $\texttt{F}, \texttt{S}$ 后面能接 $\texttt{F}, \texttt{P}, \texttt{S}, \texttt{R}$；
- $\texttt{P}, \texttt{R}$ 后面只能接 $\texttt{F}, \texttt{P}$。
所以，记 $f(n, c \in \lbrace \texttt{F}, \texttt{P}, \texttt{S}, \texttt{R}\rbrace )$ 表示以 $c$ 结尾的、长度为 $n$ 的数组个数。前缀和优化就能做到 $O(n)$。
E 菜品制作
在 $k = 1$ 时答案为 $\sum_{i = 1}^{n} a_i$。之后 $k$ 每增加 $1$，答案都会增加 $\max_{i = 1}^{n} a_i$。所以答案为 $\sum_{i = 1}^{n} a_i + (k - 1) \max_{i = 1}^{n} a_i$。
F 动态规划
对于序列 $[l_1, r_1], [l_2, r_2], \cdots, [l_k, r_k]$，考虑使用调整法得到答案。
考虑两个相邻的区间 $[a, b], [c, d]$：
- 如果它们有交，那么一定存在 $x_{[a, b]} = x_{[c, d]}$ 的最优方案。因此，可以把两个区间删掉，换成一个新区间 $[\max(a, c), \min(b, d)]$；
- 如果 $b < c$，那么一定存在 $x_{[a, b]} = b, x_{[c, d]} = c$ 的最优方案。因此，可以把两个区间分别换成 $[b, b], [c, c]$；
- 如果 $a > d$ 则和第二种情况对称，可以把两个区间分别换成 $[a, a], [d, d]$。
如果对序列不断做上述操作，答案不变，并且最终只会得到两种序列：
- 仅包含一个区间的序列；
- 每个区间仅包含一个整点的序列。
只要用这个算法套上线段树就可以直接解决问题。线段树的结点存储对应序列调整后的序列，如果是第一种就存一个区间，如果是第二种就只存 $x_1, x_k$ 以及中间的答案。合并两个结点时，先把两个序列拼起来，然后在中间进行调整即可。
时间复杂度 $O((n + m) \log n)$。
Comments
写错了，$ A_{ij} \,$应该是$\, [i = 1] \mid [j = m] \mid [i = j + 1] \,$。
妙啊
这个做法非常简洁，我出题时也没想到。感谢您的分享以及这份代码的提交者！