BZOJ-2780. Sevenk Love Oimaster

题目给出 n 个字符串 s_1, s_2, \cdots, s_n,以及 m 个询问 q_1, q_2, \cdots, q_m,每个询问是一个字符串,要求计算 q_i 在多少个 s_1, s_2, \cdots, s_n 中出现过

例如 s_1=abcabc, s_2=ca, s_3=a,那么 abcs_1 中出现过,as_1, s_2, s_3 中出现过

数据范围:1 \leq n \leq 10^4, 1\leq q \leq 6\cdot 10^4, \sum_{i=0}^n |s_i| \leq 10^5, \sum_{i=0}^m |q_i| \leq 3.6 \cdot 10^5

题目连接:BZOJ-2780SPOJ-JZPGYZ

这题是给出多个母串,询问给定串在多少个母串中出现过,并且允许离线

考虑先给 s_1, s_2, \cdots, s_n 建立广义后缀自动机,关于建立方法可以参见《2015年国家队论文》中刘研绎的《后缀自动机在字典树上的拓展》

然后对于某个询问 q_i 来说,将其放在自动机上运行(注意不能走 parent 边),最后如果走到某个状态 T,那么,如果 q_is_j 出现过,顺着 s_j 路径上某个节点的 parent 往上走一定会走到 T

所以问题就变成了,在 parent 树中询问 T 节点的子树中有多少个不同的串,可以先求出 parent 树的 DFS 序,这样子树就变成连续的一段区间,问题变成询问某段区间有多少个不同的数字(注意因为广义后缀自动机上一个节点可能代表多个串,所以每个节点都要用链表记录下有多少个串)

这个问题在线的话可以用可持久化线段树 \mathcal O(n\log n) 来做,但是这题允许离线,可以用莫队算法来解决,但是复杂度是 \mathcal O(n \sqrt n),这里有一种用树状数组解决的办法,可以做到 \mathcal O(n\log n) 的时间解决

首先可以将询问按照右端点排序,然后从左往右处理每个节点,现在考虑一个数字出现在两个不同位置,由于询问是按照右端点排序的,也就是出现在左边的那个数能够影响到的节点出现在右边的那个数一定能够影响到,所以当处理到某个点的时候,将这个点的数字上一次出现的位置的值减 1,这个位置的值加 1,然后处理所有右端点在当前位置的询问(这个方法可以先去做这题,它就是询问某个区间内有多少个不同数字)

到此这题解决,时间复杂度是 \mathcal (m\log m + m\log n + n |\sum|)|\sum| 是字符集大小

 

Miskcoo's Space,版权所有丨如未注明,均为原创
转载请注明转自:http://blog.miskcoo.com/2015/05/bzoj-2780

miskcoo

顺利从福州一中毕业!感觉大学周围都是聚聚十分可怕QAQ 想要联系的话欢迎发邮件:miskcoo [at] gmail [dot] com

Leave a Reply

Your email address will not be published. Required fields are marked *

NOTE: If you want to add mathematical formulas, use $$ to wrap them. For example, use $$x_0$$ to get $$x_0$$.

If you want to get a newline, hit Enter twice, that is, use double newlines to get a newline.