2016多校训练Contest5:1010 Prefix

正文索引 [隐藏]

传送门:http://acm.hdu.edu.cn/showproblem.php?pid=5790

题目翻译

有N个串,强制在线询问 l ~ r 个串之间有多少个不同的前缀。

题解

首先,我们需要建立一颗字典树来给所有前缀编号。
我们先看单个询问 [ l , r ],我们假装只有字符串 1 ~ r ,我们把一个前缀交给最右边的那个拥有它的字符串,这样一来我们只需要建立一颗线段树统计 [ l , r ] 区间之间的拥有前缀数量就可以了。
所以对于 n 个字符串,我们只需要建立 n 颗线段树,记录 1 ~ ri 的字符串的如上前缀掌握情况。于是,我们可以使用主席树解决这一问题。

代码