P5768 [CQOI2016] 路由表 题解

· · 题解

下文记 B 为二进制位数，即 32。

Subtask 1

M\le10^3

直接暴力枚举 l,r，然后每次判断是否更新即可。时间复杂度 O(BM^2)。

Subtask 2

M\le10^5

时间复杂度为 O(nB^2\log n) 的做法，最早的时候居然被看成了 O(nB\log n)。

进入正题，首先我们把 [l,r] 差分成为 [1,r]-[1,l-1]，然后我们转化成了前缀的查询。

然后我们枚举长度 D，然后就可以二分找到第一次变成 D 的位置 pos_D。

那么我们最终显然需要的是一个 pos 的上升序列，单调栈维护即可。

对于二分的 check，我们即判断插入了 [1,mid] 之后是否存在一个长度为 D 的匹配。

首先我们用 Trie 可以 O(B) 判断一次插入完成后是否存在长度为 D 的匹配，那么对于动态查询插入数量，发现空间限制比较大，我们就直接上可持久化 Trie 即可。

时间复杂度 O(MB^2\log M)。

Subtask 3

M\le 10^6

首先查询数量的 O(M) 显然不能省，然后我们来看看这 3 个 \log M 级的数：分别为匹配的长度，Trie 遍历，和二分最早的位置。

那么我们可以考虑消去第 3 个 \log，容易发现的是，对于同一次查询，字符串没变，所以可持久化之前到达的点应该是不变的。

因此，我们在 Trie 上再维护个信息，表示的是以这个点为终点，第一次到达它的版本。

然后我们只需要查询 r 这个版本下第一次到达 s_r 的版本，这个值就是 pos_D。

时间复杂度 O(MB\log M)，空间复杂度 O(MB)。