MOCK quasi-PTS 20230102 日志

又来了，要不然差临门一脚要不然是编译器出锅悬置指针导致了看似非常不合理的 undefined behavior。这已经不是简单的 frustration 了，要是考场上遇到这种根本没办法查出来的语言相关问题，不就三年 OI 一场空了么？

不过，正是因为考试前从没“用过”悬置指针，才会诱发这样的问题。这再次提醒我们，考场上千万不要使用不熟悉的语法糖，使用平时经大量验证的写法，纵使排版稍欠美观、或代码量增长少许，也是稳定而完备的。

不得不说，这几场“主题模拟赛”的题面中，唯这一场是最上心的。既将足球相关术语用平易近人的方式融合进题面里，又不使其过分冗长而消磨选手耐心。

简略题解

A – 胖虎

本题所求的即最长的 $l$，满足两个整数序列 $a,b$ 中分别存在一个长为 $l$ 的子段，这两个子段对应的位置的数字和构成的长为 $l$ 的新序列是一个回文串。

我们立刻想到二分答案——（将奇、偶回文串分开考虑时）“是否存在长度为 $l$ 的合法解”关于 $l$ 具有单调性。于是转化为判定性问题：对于一固定 $l$，是否存在 $i,j$，满足 $a_i+b_j=a_{i+l-1}+b_{j+l-1},a_{i+1}+b_{j+1}=a_{i+l-2}+b_{j+l-2},\cdots$。将式子稍稍变形可得 $$a_{i+k}-a_{i+l-k-1}=b_{j+l-k-1}-b_{j+k}$$ 于是条件只与 $a,b$ 中的一个相关。考虑 $c_{l,i}=\langle a_i-a_{i+l-1},a_{i+1}-a_{i+l-2},\cdots\rangle$，$d_{l,j}=\langle b_{j+l-1}-b_{j},b_{j+l-2}-b_{j+1},\cdots\rangle$，只要存在 $c_{l,i}=d_{l,j}$，那么对于 $l$ 存在答案。

不难想到哈希判定。但问题在于，怎么快速计算所有位置 $i$ 的 $a_{l,i}$ 的哈希值？场上我被这个问题卡死，最后遗憾写 $\newcommand\bigO{\operatorname{O}}\bigO(n^3)$ 部分分跳题。经何钒佑点拨，解决方法其实异常简单：我们设计的哈希函数一般是将序列 $a$ 看作一多项式 $f(x)$ 的系数序列，对所有序列均代入一固定的 $x$ 求得其值（并在某个数域下表示）。既然如此，我们插入/删除系数序列首尾元素得到的新点值，均可以由简单的四则运算得到——删除对应“减去 $?\times x^{?}$”和”除以 $x$“，加入反之。所以可以 $\bigO(n)$ 计算整个序列对于固定 $l$ 的哈希值。

可以由生日悖论得到当域足够大时错误率可以接受。时间复杂度 $\bigO(n\log n)$，如果采用 std::unordered_set 等均摊 $\bigO(1)$ 的键值表的话。

B – 魔术师

题意即“选取长为 $n\quad(n\leq 10^5)$ 的序列 $a$ 的任一子段 $a_{l,\cdots,r}$，使得该子段元素和减去该子段最大的 $k$（$k$ 为常数，$\boldsymbol{k\leq 100}$）个元素的结果最大化”。

我还以为是什么流什么匹配，结果直接链表模拟就行了。

我们比较元素时以大小为一关键字，下标为二关键字，于是每个元素唯一而答案不受影响。而被减去的这 $k$ 个数有最小值 $x$。假设 $x$ 为定值。如果激活所有大于等于 $x$ 的元素，记已激活位置为 $p_1,\cdots,p_m$（为方便记 $p_0=0,p_{m+1}=n+1$），则考虑 $a_{p_i}\quad(0<i\leq m+1-k)$ 为某个可能的解 $[l,r]$ 中被减掉的第一个元素，于是有左端点 $l\in (p_{i-1},p_i]$，右端点为 $r\in[p_{i+k-1},p_{i+k})$。

若我们按 $x$ 递减的顺序依次激活这 $n$ 个元素，则每向上文的 $p$ 插入一个新的位置，新的合法解只可能由该位置以及前 $k$ 个已激活位置产生。于是我们考虑这不多于 $k+1$ 个已激活位置作为“被减去的首个元素”，查询符合要求的 $[l,r]$ 构成的最大子段和即可。这可以用前缀和转化为 RMQ 问题，ST 表预处理即可。

时间复杂度 $\bigO(nk+n\log n)$。

C – 屠夫

太可惜了，在实战中的首次成功应用却因为该死的指针爆零。

题意即维护数字序列，支持

• “将区间最大值减 $1$”连续执行 $k$ 次（$k\leq 10^{18}$，存在多个最大值时取下标最小的一个，最大值为 $0$ 时停止执行）；
• 单点修改；
• 查询区间和。

不难想到使用 Segment Tree Beats!。我们只需要对每个节点维护最大值、最大值计数、严格次大值、次大值计数、区间和以及取 $\min$ 延迟标记。考虑某个区间 $[l,r]$ 的最大值 $\newcommand\mx{\text{mx}}$ 有 $\newcommand\cnt{\operatorname{cnt}}\cnt_{\mx}$ 个，以及严格次大值 $\newcommand\smx{\text{smx}}\smx$；于是当 $k\geq (\mx-\smx)\cnt_{\mx}$ 时，所有最大值必然直接变成次大值，相当于区间取 $\min\{a_i,\smx\}$，同时令 $k\leftarrow k-(\mx-\smx)\cnt_{\mx}$；反之，令 $c=k\bmod{\cnt_{\mx}},d=\lfloor\frac{k}{\cnt_{\mx}}\rfloor$，则区间内前 $c$ 个为 $\mx$ 的元素 变为 $\mx-d$，后 $k-c$ 个最大值变为 $\mx-d+1$。

执行该过程时恰当维护区间和，后两种操作就是平凡的。应用势能分析可以得到 $\bigO(m\log^2 n)$ 的复杂度上限，已经相当优秀了。

哦，还有关于指向数组元素的指针的错误使用。一言以蔽之：源于长为 $n$ 的数组 a 的指针 pt，其必须满足 pt >= a && pt <= a + n，且当 pt != a + n 时可以解引用，否则是 UB。