摘要：
这个操作十分的复杂 但是可以拿平衡树维护 直接二分答案然后用$hash$值判断即可 复杂度$O(10000 * log^2 n + n \log n)$ 阅读全文
posted @ 2018-11-13 16:38
remoon
阅读(252)
评论(0)
推荐(0)
摘要：
$bzoj$跑的太慢了...... 我们考虑用线段树来解决这个问题 考虑扫描线 当扫到左端点$i$时，我们把线段$i$加入线段树 同时，对于每个左端点$i$，我们在线段树上二分出最远的$r$满足$r$被覆盖了$k$次以上 复杂度$O(n \log n)$ 然后$TLE$了，这一定不是我的锅... 阅读全文
posted @ 2018-11-13 15:28
remoon
阅读(176)
评论(0)
推荐(0)
摘要：
既然只有一位的不同，那么我们可以枚举这一位.... 我们只需要快速地计算去掉某一位的$hash$值.... 由于$hash(S) = \sum s[i] * seed^i$，因此去掉第$i$位的权值只需要用$hash(S) - s[i] * seed^i$ 由于字符串两两不相同，因此不存在两个串去掉 阅读全文
posted @ 2018-11-13 14:13
remoon
阅读(158)
评论(0)
推荐(0)
摘要：
显然只能有$hash$来做.... 我们需要一个东西来维护$\sum i * seed^{rank[i]}$ 很自然地联想到平衡树 如果以序列下标建立一棵平衡树，那么无法处理 因此，可以以权值为下标建立一棵平衡树，把$rank[i]$拆分成若干个$sz[ls] + 1$即可维护 具体而言，记$pos 阅读全文
posted @ 2018-11-13 12:52
remoon
阅读(285)
评论(0)
推荐(0)
浙公网安备 33010602011771号