icontofig | 发布于 2019-09-11 08:47:43 | 阅读量 385 | 字符串 可持久化线段树
发布于 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 | 阅读量 596 | 可持久化线段树
发布于 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 | 阅读量 223 | 二分 可持久化线段树
发布于 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]内的数的个
继续阅读