草莓蛋糕

拆开 \(\max\) ：对于商店 \(A\) 设 \(ha_i=c_i-y_i\)，对于商店 \(B\) 设 \(hb_i=y_i-c_i\) ，那么可以通过 \(ha,hb\) 的大小关系来判定是使用 \(ya+yb\) 还是 \(ca+cb\) 贡献

将 \(h\) 离散化后使用线段树来求答案，每个叶子维护两个商店的 \(c,y\) 最小值，可以使用 multiset，再合并左右子区间根据实际含义维护即可，这里实际含义即左边每个叶子的 \(h\) 都小于右侧的

矩阵补全

将 \(f\) 视作集合幂级数，对于 \(b=0\) 的元素不做 FWT，否则让做啥运算就做啥运算的 FWT

求出来点值快速幂，然后做一遍逆变换

上一道使用这个形式计算的题是 THUPC2019 找树，今天没读明白题。

万灵药

题 目 说 啥 你 干 啥

题目中提到先求 LCS 再求 LCP 就建两个 SAM 实现。将 \(\rm S_{[x-|LCS|+1,x]}\) 放到反串 SAM 上定位，对答案的改变量就是找到所有已经挂到树上的点和它的 \(\rm LCA\) 的最大长度

吗？

这在该点和 LCA 存在父子关系时需要特殊处理，挂到相同节点就是两个元素长度取 \(\min\) ，其中之一是另外一个的严格祖先就是长度较小者的长度。

为了简单处理，可以将长度平摊到根链上的每个点，每个点维护它的不包括自己的子树中的节点数量并乘 \(\rm len[x]-len[fa_x]\) 即可

挂到一个点的部分需要每个点开一个线段树，剩下的都用树剖维护即可，时间复杂度 \(\Theta(n\log^2n)\) ，只写了动态开点就跑了 1.8s 那么这不是一个好的做法

标算将求 LCP 的过程挪到了 Trie 树上来避免多个子串共点的情况，考察求两个前缀 LCS 的过程可以发现不是 SAM节点最长长度对应的串不会在 LCS 中出现，那么问题被简单化至可以解决