p1117专题

P1117 [NOI2016]优秀的拆分 [Hash]

传送门 比较容易想到的是, l[i], r[i] 表示 i 的左右 有多少个 AA 串 那么答案就是  , 于是已经可以 n^2 过 95 了 我们考虑批量处理长度为 L 的AA串, 每隔 L 个位置打一个标记 然后对于两两标记之间前后求一个 LCP(Hash + 二分) 画个图, 就可以看出, 哪些区间是有贡献的, 差分一下就可以了 #include<bits/stdc++.h>#