• 周二. 7 月 16th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

CF666E

admin

11 月 28, 2021

同学们都用 (SAM) 过了,那我发一个 (SA) 的题解

考虑使用 (SA) 的流氓做法,把所有串拼在一起

容易发现符合条件的子串满足 (lcp(x,pl)geq (r-l+1)) ,即 (rk) 上连续的一段

二分找出每个询问的左边界和右边界,问题就转化为了一个区间众数问题

可以使用经典的 (O(n sqrt n )- O(sqrt n)) 区间众数求法

我这里偷懒,写了个莫队+线段树的 (O(q sqrt n log m)) 做法。这样写容易被卡常,可以调一下莫队的参数(但是跑得还挺快的?)

代码

发表回复