CSP-S 游寄

初赛

唉唉，又错了这个 t1。

最终 95。

复赛

Day 0

打了几个板子。

Day 1

t1，shaber 题，5min 过了。

t2，binary search，被我猜中题了！！然后就是【模板】区间选点，，

抄错速度公式了，白调 15min，大概 15:20 左右过的（？

t3，哦哦，\mathcal{O}(n^2) 非常简单啊！

然后呢？转移值本质不同的只有 a_j=a_i 和 a_j\ne a_i 啊！然后呢？是不是对于前者我一定会选离 i 最近的那个 a_j=a_i 啊。

欸，画一下，猜对了！

后面那个转移呢？我打个 tag 从前往后推过去对不对啊？

答案问 \max，不合法的转移必然不优，这不就 \mathcal{O}(n) 了，做完了！！、

可能不到 15min 就把 t3 过了，

现在不过才 60min，t4 拿什么秒我！！！！

t4，一股 maze 的味道/se/se/se

看看单组询问咋做。先来拆个贡献，变成看看每个 i 能不能成为 winner。我们发现每个 i 在每一层是小儿子还是大儿子已经确定了，也就是每次是比较 i 还是比较 i 的对手就确定了！那么我们对于两者分别讨论就好了！

如果比较 i，那么我直接判就完了；具体的，如果 i 是知道信息的，那我看看是不是 <k，小于就 game over 了；如果 i 不知道信息，那可以直接 skip，因为我让 a_i\gets \infty 肯定是不劣的！

如果是比较对手，撕，有点难处理啊。想想看。一个 Key Observation 是，空节点是可以随机应变的！因为如果空节点可以成为他的对手，那么仅仅只需要空节点的值 \ge k-1（当然肯定需要空节点一路干上了的过程中没有人拦他的路，，），因为在前 k-1 层的比较中我让空节点值 >k-1 是没有任何用的！

那么当进行第 k 轮比较时，我让空节点值取到 k-1 给 i 让路就行了！

好的，我们获得了一个大体思路：不妨设 f_i,g_i 分别为在 不考虑空节点时在 i 节点的 winner（我们认为空节点是 \infty，可以自己感受一下为啥这样没问题）和 让一个空节点成为 winner 的 c 最大是多少（这个显然是有单调性的）。

转移有些细节，

好的，然后咋做呢？？

继续回到最开始的拆贡献，我考虑从 i 对应的叶子节点一直往上爬，爬到一个前缀节点（其到根链上一直作为左儿子），我就可以让他对一个区间的 c_i 产生贡献！！具体的区间范围根据上面的讨论然后再摸一下就出来了！

我们差分一下，就对完了！！！

获得了 \mathcal{O}(T(n\log{n}+m)) 的做法！！！

开写！！

好的写完了，光荣过不了样例。开调。

debug 的过程有些惊险啊，不过还是最后 20min 乱改了一些东西过了所有大样例。

再小卡一下常。

貌似本地 T=64 要跑 1s 出头啊，T=128 要 3s 啊，不过这个机子看起来，很慢啊，那我是不是有 [84,92] 分了？？？

反复检查了几遍文件夹一类的东西，也是结束了。

可能也许大概是 100+100+100+[84,92]=[384,392]？？

出场看见了 dspt 和 Madoka。

Madoka 貌似有一点小爆啊，写了半场的 t4 然后假了，似乎获得了 100+100+100+0 的分数？

dspt 和我一样啊，不过他的 t4 跑得比我慢一些？

在机房群里乱问了一下。

京✌也是和我差不多一个分啊。

xhgua 似乎是被 t3 创飞了？？（顶针王不应该一眼秒了这个题吗？），写了个线段树优化 dp 来着，t4 就好像拼了个位数暴力，似乎 t3 可能还爆了（？（upd：100 -> 20）

lycc 貌似是 100+100+100+?，不是很懂。

luanyi 是不是也差不多 300+ 来着。

szh 反正是没有任何意外的 ak 了/bx/bx/bx（upd：貌似出现了 1<<-1 的问题，不知道会不会似啊）（upd：没似）。

很多人 t4 写了假做法 or 冲了一半没敢继续写了，感觉我这个最后 20min 调出来也有点惊险啊。

你说得对，但是我被 xy 抓取当黑奴去造心有对 t2 数据了/ll/ll/ll

upd：最终 100+100+100+76，再也不信 ccf 机子了/ll/ll/ll