简单写一下游记。最后一次 CSP 了哈哈。

昨天天气阴森森的，进入考场很有趣的是我们跟着人走错楼了，走到了一个大阶梯教室。最后好歹是走到机房了。

首先每个题目都看了一遍，只有 T4 没啥思路。

T1

放在桶里面，从前往后扫一遍就行了。

T2

时限2s。就是算一下超速区间然后二分看一下有没有被抓到就行。然后按照右端点排序贪心就完了。听说很卡常？但是考场上我没注意到这点，大样例跑飞快。

T3

看到之后想了一个想法，就是相等的只会选择离他最近的那个相等的，否则会更优，看起来很正确。由于有两种颜色，有一种结尾一定是前一个。因此就很容易有暴力 $n^2$ 的做法了。然后就只需要开一个 $f_{i,0/1}$，$f_{i,0}$ 表示前 $i$ 个的答案，$f_{i,1}$ 表示 $i$ 不与 $i - 1$ 连接的答案。顺便记录一个 $pre$ 数组表示前一个出现的位置，直接转移再用前缀和处理区间就完了。然后写对拍，最后拍出了暴力的错误，后面直到考试结束都没错，应该没有什么问题。

T4

此世距离考试结束还有2个小时，大概就是建一个满二叉树吧，每次新增一个点往上更新。然后这里有每次 $\Theta(\log^2n)$ 的做法，就是每个节点记录一下可能传上来的值，大于 $K$ 的放到一堆，未确定点放到一堆，而且可以发现不确定点当擂主可以自由选择是否晋级。然后当时没写这种，想正解，得到错误结论就是确定点只可能有一个获胜，下来想发现假了，就是既可能确定点又可能不确定点当擂主 update 的时候就可能有两个确定点。这样只能过前两个样例，希望 CCF 给过几个点。发现这样应该可以过特殊性质 AB，那就得分40+吧。想了想，关键就是既可能确定点又可能不确定点当擂主时向上合并的问题。然后一个一个加的过程可以二进制拆分，形成若干个满二叉树，顶点都是确定值。然后就可以从当前最右边的点向祖先跳，然后这条链从上到下更新，就算从链上每个点要更新到当前的根（就是前缀那个最深的能包含这个前缀的点）所需要的最小值。这样每次和一个满二叉树合并的时候就看一下满不满足条件，满足的话就把确定点的贡献合并上去。合并的具体过程大概就是擂主如果是确定点，那么很好判，合并后要么是擂主，要么是另一个上来。如果是混合点，那么非擂主也可以合并上来。这样就可以做到单 $\log$。

后记

没啥可记。

友链 -> alloverzyt