icontofig | 发布于 2020-02-19 22:10:38 | 阅读量 998 | 字符串 可持久化线段树 可持久化数据结构 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 | 阅读量 227 | 二分 可持久化线段树 可持久化数据结构
发布于 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-09-11 08:47:43 | 阅读量 495 | 字符串 可持久化线段树
发布于 2019-09-11 08:47:43 | 字符串 可持久化线段树
The Preliminary Contest for ICPC Asia Xuzhou 2019 G.Colorful String PAM(回文自动机) + 可持久化线段树
题目大意给出一个字符串,求出所有回文串的字符种类数之和。 题解考场上他们都有回文自动机的板子而我没有QAQ 首先对于一个子串,其对应一个子区间,这个子区间的数据的种类数的多少我们是可以用主席树来维护的,这是众所周知的。 具体维护方法: 从第1位置往后扫,如果之前出现过相同的数据,我们就在之前出现过的位置-1,在当前位置计数+1,然后把当前位置记录下来。 但是我们怎么求所有回文串的长度和数目?Manacher是不行的,效率太低了。 于是有一个神奇的PAM,也就是回文自动机。 回文自动机中,cnt[i]表示以i结尾的最长的回文串的数目,len[i]表示以i结尾的回文串的长度为多少,pos[i]表示
继续阅读
icontofig | 发布于 2019-08-24 18:05:54 | 阅读量 679 | 可持久化线段树
发布于 2019-08-24 18:05:54 | 可持久化线段树
HDU 6703 CCPC 2019 网络赛 1002 array 可持久化线段树(主席树) + set
题目大意给定一个1----n的排列,有以下两种操作: 1.给序列中位置i的数+10000000。 2.询问未在1-----r位置出现过且≥k的最小值。 题目保证1≤k≤ 100000,强制在线。 题解这场CCPC网络赛可谓有毒,博主这题被卡常卡到心态爆炸。 首先我们来看一下这两个操作分别有什么性质。 根据k≤100000这个条件,我们每做一次1操作,就相当于直接将i位置的数删除掉,也就是i位置的数可取了,毕竟k还是比一千万小很多的。 2操作貌似没什么性质,只是我们要搞的时候注意不能取用1----r之间的所有数就是了。 因为很明显的涉及到时间戳的问题,所以肯定是主席树。 然后最容易想到的是直接用
继续阅读
icontofig | 发布于 2019-08-01 16:44:07 | 阅读量 237 | 二分 可持久化线段树
发布于 2019-08-01 16:44:07 | 二分 可持久化线段树
2019 Multi-University Training Contest 4 1008 K-th Closest Distance 二分答案+可持久化线段树(主席树)
题目大意给你一个长为n的序列,有q次询问,每次询问回答区间[l,r]中离p距离第k小的数距离p有多远(距离指在数轴上的距离,也就是差的绝对值) 题目强制在线。 题解我们首先可以把问题转化为这样: 假设询问的答案为ans,那么就代表着区间[l,r]内的数中,在范围[p-ans,p+ans]中有k个。 所以我们就可以枚举答案,然后去查询区间[l,r]内的符合要求的数的个数。 但是枚举效率过于低下,我们又发现这个答案是具有二分性的,所以我们将枚举答案改为二分答案并且检查。 然后再来看我们怎么统计区间[l,r]内在范围[p-ans,p+ans]的数的个数。 一般来讲,我们判断在范围[p,k]内的数的个
继续阅读