ejudge's blog

Blogs

象题题解

2021-07-03 16:10:13 By ejudge

首先将所有字符串拼在一起做后缀数组。

我们需要求出每个后缀有多少个前缀满足条件(记为 $f_i$)。

对于每个后缀,预处理出往后扩展到哪里会满足条件。对于这样的一段区间,公共前缀就是height的最小值(记为 $x$ )。

一个区间 $(l,r,x)$ 对 $f$ 有以下影响:

  1. 对于 $l \leq i \leq r$,$f_i\leftarrow\max(f_i,x)$。
  2. 对于 $i>r$,$f_i \leftarrow \max(f_i,\max(h_l \cdots h_i))$

对于(1)维护一个单调队列,对于(2)直接记录 $l$ 的最大值即可。

时间复杂度 $O(N\log N)$

Comments

No comments yet.

Post a comment

You can refer to mike by using "@mike", and "mike" will be highlighted. If you want to type the character "@", please use "@@" instead.

You can enter "/kel" to use the emoticon "kel".