![[Record] 杂题选做](http://pic.xiahunao.cn/yaotu/[Record] 杂题选做)
感觉很多题过了就跑很不够……不能再颓了！
P13866 [SWERC 2020] Daisy's Mazes
很有趣的一道题。
比较傻地对栈序列 dp，显然状态数量是 NP 的。考虑如何减少状态。
假设一种简单情形，也即在出发点和结束点栈都为空，可以看作走了一条合法括号路径，那么可以根据实现的精细程度有各种各样的多项式复杂度算法判断是否存在这样一条路径。具体而言将转移分为括号序列拼接（传递闭包）和在括号序列外层增加一层括号两种，记忆化搜索即可。
这启发我们可以通过添加虚点将初始栈序列和结束栈序列不为空时的栈序列状态转换为虚点之间的路径（换而言之，将状态转换到自动机上），使问题归为前面简单的判定问题。
具体地，对于起始状态，增加 \(n\sim 2n-1\) 号节点，对于 \(n<i\leq 2n-1\)，向 \(i-1\) 号节点连所有 \(k\) 中颜色的边，\(n\) 号节点向 \(0\) 号节点连所有 \(k\) 中颜色的边。对于终止状态，\(n-1\) 号节点向自己连所有 \(k\) 种颜色的边。
P8868 [NOIP2022] 比赛
洛谷的题解写的推式子的方式看起来很学不会，固定自己的套路，历史版本和使用线性函数形式进行推导。
- 诚然可以列出 \(5\times 5\) 的矩阵，接下来要么神通广大地卡常，要么精力旺盛地拆分 \(125\) 个转移手算去掉无效转移合并相同转移。
- 诚然也可以直接写分块，免去线段树下传标记讨论的麻烦，接下来充分发扬 \(\text{Ynoi}\) 的精神。
先注意一个问题，虽然有最值修改一句值域连续段转覆盖为加法的套路，但查询的东西是历史版本和，没有必要将区间覆盖标记转化为加标记，这样会更麻烦。
设出答案：
\[S_l=\sum_{r'=l}^{r}(\max_{i=l}^{r'}a_i)(\max_{i=l}^{r'}b_i)
\]
将 \(\max a\) 和 \(\max b\) 分别记作 \(X_l\) 和 \(Y_l\)，答案可以表示为一个函数的形式，也即：
\[S_l'=S_l+k_{xy}X_lY_l+k_{x}X_l+k_{y}Y_l+C
\]
懒标记也便顺势维护 \(k_{x,y},k_{x},k_{y},C\) 几个系数项，其合并也即计算复合函数。