回复 @AeeE5x :
cnt 数组并不需要 long long，里面存的数是 $\mathcal O(n)$ 级别的。

喜报: unr d1t3 出现这个模型，被取之。回旋镖哦哦哦哦

事实上也可以这样：记录 $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 树上修改一条链的值。