BZOJ5405 - platform

首先,我们需要知道如何利用后缀数组对一个指定的字符串计算字典序 Rank 。我们以 abaab 为例:

1
2
3
4
5
6
7
8
9
10
 a    a    b
11 10 9
a b
x 8
a b a a b
x x 7 6 5
b
4
b a a b
x 3 2 1

按照顺序进行编号,因为本质相同的字符串不重复计算次数,所以每一行的前 $height_i$ 个不计入个数,所以我们也有了一个很自然的 $O(n ^ 2)$ 做法。

接下来我们考虑正解,可以发现,每次可以看做对上面的字典序 Rank 数组进行了依次递减的区间覆盖,可以使用线段树维护。同时我们可以发现,这个 Rank 是递减的,而前缀和是递增的,所以我们可以二分出相等的那个位置。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×