传送门 这个题我一眼秒，然后发现好像是查询好像变成了 O(log2n) O(log^2n) 然后发现数据范围说查询操作不超过10000次，然后就觉得应该是正解了。。 然后调试了超级久。。。 再然后就WA了3个点。。 最后发现我调试的时候为了方便，质数只取到了1000，然后取到1e9+7，就过了。。 我们来说正解吧。 emmmm，一句话题解吧。 Splay+Hash+二分 好像

火星人prefix 题目背景： bzoj1014 分析：我有一句XXX不知道当不当讲，但是真的太恶心了！！！ 这道题本来的做法是对于每一个节点，维护以它为根的子树的字符串的hash值就可以了，我是用无旋treap来实现的，然后每一次合并和分割的时候，就可以直接update像上维护即可，但是当时开始的时候我的代码不断地T飞，然后我尝试优化了很多波的常数，最后发现并没有什么卵用，然后