Daily Archives

One Article

OI

P5161:WD与数列 – 题解

Posted by kal0rona on

主要思路

先差分,然后再来做这个不相交子串匹配的问题。

我们可以考虑用线段树来维护 endpos 集合,然后用启发式合并的方式来计算一个后缀点与当前点集之间产生的贡献。有两种情况:

  • 当前为 endpos 的最长长度、与当前位置 \(x\) 不相交的子串。这个可以直接暴力线段树上查个数。
  • 长度小于 \(maxdep\),以 \(endpos\) 在左边的情况为例:答案的贡献就是 \(x – endpos – 1\)。