这周 VP 了两场 Div.2。均获得较高名次，可能之后需要 VP ARC 这种有点强度的比赛更好一点。
联考：
20240909
T1 又是数学。
T2 唐氏了。注意到有结论，一个合法路径必定可以调整到经过一个在时间上正好能走的边。然后就简单了。正着反着 dij，然后 \(O(m)\) 合并。
T3 更为唐氏，场上好像只差一步转化，可能弯路绕多了导致的。首先把两边都有出口的 bot 提出来，然后两两限制当且仅当 \(l_i\leq l_j,r_i\leq r_j\)，其中 \(l_i\) 为负，代表向左走的最近的出口，\(r_i\) 同理。
把这个限制转化到二维平面上的一个前缀，对于点 \((\infty+l_i,r_i)\)，这个就相当于如果这个点选 L，那么前缀随意选，否则前缀都只能选 R。记录 \(f_i\) 为每个时刻，对于横坐标大于等于 \(i\) 的点计数的方案数。我们按 \(l\) 绝对值从小到大加入点。
每次加入，相当于在区间 \([0,\infty-r_i]\) 上进行修改，我们会惊喜的发现，我们相当于加入了这个新点填 R 的情况的贡献。而在这个区间中，它是一个定值！即为 \(f_{\infty-r_i+1}\)。离散化后树状数组维护即可，最后答案即为 \(f_1\)。
考虑初始值，不难发现原来 \(f\) 全是 \(1\)。真的很巧妙的一个观察啊！
20240910
大部分人的评价是：不如出卡精度 GEO。
T1 shabi，之前正好 vp 过一个 CF1656F 强于此题。
T2 纯唐。不过又积累了一个新的 DP 转移的一种方式。
考虑设 \(f_{i,j}\) 为第 \(i\) 个位置开始消除，直到只剩下 \(j\) 元素的最小右端点。考虑因为 \(f_{i,s_i}\) 最小且固定，且空集由 \(26\) 转移过来，所以其实空集的转移对象只有 \([1,s_i-1]\)，因为其余的转移是不优的。很厉害啊！所以我们可以设定一个转移顺序：\(s_i\to \text{z},\varnothing,\text{a}\to s_i-1\)。然后转移有两个 \((j-1)+(j-1)\) 和 \((\varnothing)+(j)\)。
最后用 空集处的 DP 值 倍增就能判断是否合法。
T3 奇艺搞笑的马良题。就是缩成 babababa 类似的字符串，每次交换每段与前缀合并，一个字符串为空就把另外一个字符串的一半拉过来。
T4 niubi。容易想到回滚莫队。但是我们有性质：这个题如果能支持删除那么可以双指针。推一推就可以发现我们可以把决策单调性分治的过程回滚化了。时间复杂度 2log。
20240912
T2 拍出来有问题，然后给我放过了/qd/qd/qd/qd
T1 shabi/qd。
T2 大概是先枚举回文中心，然后这个东西满足贪心，一个正反 KMP 和 Manacher 就 OK 了。然后我场上是枚举的回文中心是一个串的回文串，然后就不知道怎么做了/qd，然后我钦定回文串只有最大的才有贡献。场上其实是证出来了回文中心满足贪心，但是根本没有往这个枚举想。
T3 课件原/qd/qd/qd/qd/qd/qd，CF1149D。
T4 P8394/qd。场上一直不知道 \(G=1\) 怎么做，然后最后才胡出来，然后就会 60 了。但是怎么可能写完。我场上没考虑预处理，但是二分是显然的/qd/qd/qd/qd/qd/qd/qd。大概就是二分一个前缀长度，这个前缀都从前面出来，这个后缀都从后面出来，然后要保证这两部分贡献尽量相等；即如果前面小于后面，那就向后面走，否则想前面走。预处理一个字符集对于一个点前面和后面的贡献，然后就完了。
20240913
T1 /qd。
T2 哈希。场上胡的是多重集哈希，时间复杂度 \(O(n|\Sigma|\log n)\)，还带巨大常数，但是单模的正确性足够高，直接过了。但是实际上可以设 \(i-pre_i\) 为权值，然后 \(O(n|\Sigma|)\) 对于每个后缀找到哪些本该为 \(0\) 的位置填了 \(1\)。然后二分的时候，可以比较 \(O(|\Sigma|)\) 段哈希值，如果有不同再二分。然后如果 \(0\) 的位置不一样可以直接判断。这样能做到 \(O(n|\Sigma|+n\log n)\)。
T3 出题人有点私募了。考虑设 A 为 \(1\)，B 为 \(2\)，在模 \(3\) 意义下，和为 \(1\) 的非交替串剩 A，和为 \(2\) 的非交替串剩 B，剩下的是空集。可以通过这个加法证明最后那个为 \(0\)。然后出题人就知道这个充要条件就开始发电了。用一个矩阵维护和，然后用一个矩阵维护交替串数量。然后因为是区间子区间问题，我们对于每个区间还要维护其答案，维护其前缀积的和和后缀积的和。然后你还要反转，所以标记还要两倍。
注意前后缀积的和在未激活状态下是全 \(0\)，区间的积是单位矩阵。我觉得一个正常的出题人都最多出到子区间，激活这个太无脑了。
T4 在 dfn 序上 DP。计算减去的代价的最大值。把 LCA 这个条件搞成在目前祖先的子树最大 DP 值更新，然后这里有支配性，即其其他子树的决策或者其之前没有更新的时候的决策劣于现在的决策。搞出来是一个斜率优化的形式。因为询问的 \(x\) 没有单调性，就只能直接上李超树了。时间复杂度 \(O(n\log V)\)。
下周继续整二项式反演。
赛后排行榜真的很困难，而且下周和下下周连续 ARC 和 AGC。没法开发。/ng
标签：总结,前缀,一个,T2,然后,20240915,qd,回文 From： https://www.cnblogs.com/xingyuxuan/p/18415739