使用字符串哈希判断相等。用线段树维护操作。
因为数对 $P$ 取模，且每次只加一，因此取模的次数不超过 $n\cdot (1+q/P)$。题目中 $P=65536$，因此暴力取模就可以通过。
另一个方法是注意到两个数列相等等价于第一个数相等且差分数列相等。用树状数组维护差分数列及哈希即可。
时间复杂度 $O(n+q\log n)$。
QOJ.ac
QOJ
Discussion #227 for Problem #9302. Caesar Cipher
Type: Editorial
Status: Open
Posted by: jiangly
Posted at:
Last updated:
题解
Comments
No comments yet.