事实上也可以这样：记录 $pre_c$ 表示 $c$ 最后一次出现的位置。扫描线，扫到询问 $(l, r, c)$ 的时候只需判断是否有 $pre_c\ge l$ 即可。
这样的复杂度仍然是 $\mathcal O(m\log n)$。

回头看一下，这道题其实是一个相当经典的倍增 + 二分的模型，在 CTT2019 D1T2 也有考。不过再看到这个模型完全反应不过来。。

换了一个实现得更漂亮的 std，被卡常了的话可以参考一下。

回复 @┭┮﹏┭┮ : vector 的存储是很慢的，考虑 $\pi(n)\approx n/\ln(n)$，存素数的数组可以开到 1e7 左右，不会 MLE

bitset 这么牛。

由乃救爷爷。

https://www.bilibili.com/video/BV1QM411A73c/

玩原神玩的。

其实这个题暴力hash做法复杂度就是线性的，常数吊打manacher。

如果做 DP 的话，似乎存在凸性，可以使用 wqs 二分优化？！

DP 套 DP，惊为天人！
修复了一下 MathJax 。

数据有点水阿，后缀数组+启发式合并没有判断后缀 1 是否在集合中就过了。
当时写 KMP 有点不懂，学习了 Fail 树后大概理解了，KMP 做法的本质其实是 Fail 树上修改一条链的值。

duliu。

对这种结论题不太敏感阿。很厉害的题目。

你说的对，但是《NOIP2022》是由 CCF 自主研发的一款全新开放世界冒险游戏。游戏发生在一个被称作「吉吉朋鸟」的幻想世界，在这里，被评测机选中的人将被授予「省一」，导引常数之力。你将扮演一位名为「考生」的神秘角色，在考试中邂逅性格各异、能力独特的 OIer 们，和他们一起击败强敌，找回失散的分数——同时，逐步发掘「暴力 AC」的真相。