NOIP2025模拟赛4总结

套了好几层操作，先摸拟下样例再说。

感觉只需要求出$min$和$max$就可以求出答案。

打个暴力验证下结论，应该是对的。

好像可以用回滚莫队，但是这是$T1$。

听说有人很快过了，应该不会太难。

原来$|b_i| \le 10$，那肯定要用桶。

好像直接贪心就好，过大样例了。

结论挺好证的，只需要让负数区间不断移动，就可以保证$min$和$max$中的每一个值都能取到。

赛后发现回滚莫队好像假了，需要带个$log$。

字符串？有些像$AC$自动机。

不太对，需要不断更新$fail$树，直接退化成$O(n^2)$，只有$20$分。

听说有人用$SAM$，还有人在$fail$树上套数据结构。

用哈希可以暴力$20$分。

好像可以根号分治。

大样例还挺快，空间好像也不高。

赛后发现只有$20$分，其他点T或M了。

$60$分正解和我想的一样，只能是我实现的太差了。

$100$分是考虑到字符串最多有140多种长度，然后将该长度的所有子串的哈希值存下，二分下就好。

感觉是倍增，但好像很奇怪，为什么会移动啊！

这怎么倍增啊？

打个暴力先跳了吧，估计有$20$分吧。

赛后发现$30$分，挺好的。

正解就是神奇倍增，加个偏移量，然后再二分一下。

倍增还能这么玩啊！

转换下题意，好像不难，上个线段树好像就没了。

先打个暴力吧。

暴力怎么$WA$了。

算了，放弃了。

赛后发现题意转换错了。

正解是平衡树，用时一天，学了$FHQ-Treap$的基础内容。