icontofig | 发布于 2020-02-19 22:10:38 | 阅读量 535 | 字符串 可持久化线段树 可持久化数据结构 Trie
Codeforces 547E Mike and Friends AC自动机Fail树上DFS序建可持久化线段树
Input5 5 a ab abab ababab b 1 5 1 3 5 1 1 5 2 1 5 3 1 4 5Output7 5 6 3 6题目大意给出n个字符串,q次询问,每次询问l,r,k,求问 字符串l——r中,包含字符串k(字符串k作为子串)的字符串个数是多少。 题解多模式串匹配肯定是AC自动机 但是这个问题是多个串中有多少能匹配到当前询问的这一个字串的问题,而不是经典的某个串能匹配多少个已经给出的串的问题。 AC自动机的Trie树中,某个节点的所有祖先节点表示一个或几个字符串在当前这个位置之前的字符串前缀。所以对于某个结束节点来说,他的所有祖先节点加上他本身构成了一个字符串。 而
继续阅读
icontofig | 发布于 2020-02-10 23:17:59 | 阅读量 224 | 二分 可持久化线段树 可持久化数据结构
发布于 2020-02-10 23:17:59 | 二分 可持久化线段树 可持久化数据结构
CodeForces - 484E  Sign on Fence 二分+主席树
Input5 1 2 2 3 3 3 2 5 3 2 5 2 1 5 5Output2 3 1题目大意给出一个序列,有m组询问。 每一组询问有三个参数l,r,w,问区间[l,r]中所有由连续w个元素组成的子序列中的最小值中的最大值是多少。 题解看到题目里面的最小值最大,肯定能意识到应该是用二分+check去验证元素的(因为其他能想到的方法基本都是暴力,复杂度太高,这题数据范围在105级别没法用的)。 然后问题就在于这个check如何去操作。 如果我们当前二分一个值mid,怎么检查区间l-r中是否所有的连续的w个元素中的最小值中的最大值是mid呢? 这个没法做到,我们只能去确定,是否存在连续w的
继续阅读
icontofig | 发布于 2019-11-20 12:11:47 | 阅读量 404 | 并查集 可持久化数据结构
发布于 2019-11-20 12:11:47 | 并查集 可持久化数据结构
可持久化数据结构众所周知,在竞赛界有这么一种神奇的解决方案,用以解决简单数据结构无法恢复历史版本的问题。 它就是可持久化! 如何可持久化?当然是要记录历史信息了。 但是那消耗空间不会巨大吗? 起始如果我们可以合理运用历史版本信息,我们就可以在创建新版本的时候尽可能地缩减需要的空间。 我们可以在当前版本复用未被修改地上一个版本的信息内存。 然而如何才能尽可能地去复用内存空间呢?这就需要树形结构了。 所以,对于所有的可持久化数据结构而言,都需要可持久化数组(一棵树)这样的基础。 怎么建立可持久化数组呢?可持久化数组的建立类似线段树,也就是可持久化线段树的建树过程。 所以说,可持久化线段树的建树是所
继续阅读