Tag-可持久化数据结构

Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

 2020-02-19 22:10:38 |  0 Comments  |  字符串 可持久化线段树 可持久化数据结构 Trie

Codeforces 547E Mike and Friends AC自动机Fail树上DFS序建可持久化线段树

Input

5 5
a
ab
abab
ababab
b
1 5 1
3 5 1
1 5 2
1 5 3
1 4 5

Output

7
5
6
3
6

题目大意

给出n个字符串,q次询问,每次询问l,r,k,求问

字符串l——r中,包含字符串k(字符串k作为子串)的字符串个数是多少。

题解

多模式串匹配肯定是AC自动机

但是这个问题是多个串中有多少能匹配到当前询问的这一个字串的问题,而不是经典的某个串能匹配多少个已经给出的串的问题。

AC自动机的Trie树中,某个节点的所有祖先节点表示一个或几个字符串在当前这个位置之前的字符串前缀。所以对于某个结束节点来说,他的所有祖先节点加上他本身构成了一个字符串。

而对于AC自动机建立的fail树来说,一个节点的fail指针指向的节点以及其trie树上的祖先一定构成了当前节点到trie树的根节点所表示的字符串的一个后缀。如果其fail指针指向的是一个结束节点,那么这个串就一定能匹配它的fail指针指向节点在trie树所代表的一个字符串,也就是完成了一个子串匹配。

于是我们可以借助这一点性质,来求解能匹配ac自动机中第k个字符串的字符串个数,方法是:

沿着当指向当前节点的fail路径的反方向走,每走到一个节点ans+1,最终无路可走时,得到的就是答案。(包括这个字符串本身)。、

但是这个题还有在区间[l,r]的字符串的限制。

考虑到普通的线段树没法做到这种询问,所以我们应该想到这个题可以用可持久化线段树来做。

可持久化线段树最大的特点就是每棵线段树的根节点都代表着一次更新的时间戳,我们可以利用这个时间戳去求区间的一个值。

但是这是一个AC自动机上的问题,准确的来说是fail树上的问题,如何建线段树?

对于树上问题,可以先想树链剖分,其本质就是求DFS序,所以我们也可以对fail树构建DFS序,然后在此基础依次添加每个串,构建可持久化线段树。

根据上面的fail树上的性质来说,通过fail路径的反方向路径构成的fail树,某个节点的子节点都是原先的fail指针指向当前节点的节点,也是我们要统计路径时走向的节点。

某个节点的子树,代表了能匹配到以此节点到trie树根节点构成的字符串的后缀的所有字符串所在的fail树的位置。

我们根据fail路径来构建DFS序,在此基础上建立可持久化线段树。在建立可持久化线段树的过程中,每添加一个字符串,都要对这个字符串在AC自动机Trie树上

 2020-02-10 23:17:59 |  0 Comments  |  二分 可持久化线段树 可持久化数据结构

CodeForces - 484E Sign on Fence 二分+主席树

Input

5
1 2 2 3 3
3
2 5 3
2 5 2
1 5 5

Output

2
3
1

题目大意

给出一个序列,有m组询问。

每一组询问有三个参数l,r,w,问区间[l,r]中所有由连续w个元素组成的子序列中的最小值中的最大值是多少。

题解

看到题目里面的最小值最大,肯定能意识到应该是用二分+check去验证元素的(因为其他能想到的方法基本都是暴力,复杂度太高,这题数据范围在105级别没法用的)。

然后问题就在于这个check如何去操作。

如果我们当前二分一个值mid,怎么检查区间l-r中是否所有的连续的w个元素中的最小值中的最大值是mid呢?

这个没法做到,我们只能去确定,是否存在连续w的区间的数全部大于等于mid。

我们假设当前二分到的值为mid,大于等于mid的数都设为1,小于mid的数都设为0,那么问题就变成了询问区间内[l,r]上最长的连续为1的子序列长度len是否大于w的问题。

但是我们注意到一些问题,序列中的数比较大,直接二分的话常数会大些,而且也没有办法对每次二分的mid建一棵线段树去check,时间上会炸掉。

这种情况下我们可以考虑将序列中的值从大到小排序,保留其原先所在的位置下标,对排完序之后的值,我们可以直接用序列进行二分。

而在排完序的情况下,可以注意到,以当前位置的值为check的值时,其构建的线段树就是上一个位置对应的check所用的线段树上在当前位置的值在原序列中的下标对应的位置插入1。

这个修改只有一次,因此可以建立可持久化线段树进行check。

当前二分的位置为mid时,对root[mid]对应的线段树进行check,检索是否可行就可以了。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int n,q;
struct height{
    int h;
    int id;
}a[maxn];
int rt[maxn];
int u,v;
const int INF = 1e9+7;
struct tree{
    int l,r;
    int lc,rc;
    int suml,sumr,sum,len;
}tr[maxn*25];
int cnt = 0;
void push_up(int now){
    tr[now].len = t
 2019-11-20 12:11:47 |  0 Comments  |  并查集 可持久化数据结构

可持久化并查集 洛谷P3401

可持久化数据结构

众所周知,在竞赛界有这么一种神奇的解决方案,用以解决简单数据结构无法恢复历史版本的问题。

它就是可持久化!

如何可持久化?当然是要记录历史信息了。

但是那消耗空间不会巨大吗?

起始如果我们可以合理运用历史版本信息,我们就可以在创建新版本的时候尽可能地缩减需要的空间。

我们可以在当前版本复用未被修改地上一个版本的信息内存。

然而如何才能尽可能地去复用内存空间呢?这就需要树形结构了。

所以,对于所有的可持久化数据结构而言,都需要可持久化数组(一棵树)这样的基础。

怎么建立可持久化数组呢?可持久化数组的建立类似线段树,也就是可持久化线段树的建树过程。

所以说,可持久化线段树的建树是所有可持久化数据结构的学习基础。

可持久化并查集

并查集是一类用于判断图中两点是否连通的数据结构,其优点是时空复杂度低,但也有缺点,就是无法进行边的删除,只能进行边的添加。

如果我们要删除一些满足特定性质的边怎么办?比如删除最近添加的几条边?

显然最简单的并查集已经无法满足这个需求,所以我们借助可持久化数组将并查集升华成可持久化并查集。

并查集中有一个非常好的优化方法叫做路径压缩,但是如果在可持久化并查集中,这种优化方法就不适用了,因为它不能保持原来的各个连通块之间的关系,这样我们恢复历史版本的时候就会出问题。

为了使回溯历史版本时不出问题,再让并查集尽可能地优化,我们这里使用另外一种优化方法:按秩合并。

按秩合并的基本思路是:合并时将并查集树深度小的树根连到并查集树深度大的树根,以尽可能缩小并查集的深度。从而减少查找祖先的时间复杂度。

这种优化方法虽然没有路径压缩更优,但是非常契合可持久化的要求,所以拿来做可持久化并查集。

这里要注意,可持久化并查集中的可持久化数组的非叶子节点是没有意义的,只是拿来记录当前内存对应的原数组的下标区间,只有叶子节点才真正表示一个历史版本下某个节点的信息。

我们拆分成多个过程来看:

一、可持久化并查集的初始化建立

这一部分跟线段树差不多,只是到叶子节点的时候,其记录的信息要按照并查集按秩合并的初始化,将fa和dep全部初始化。

int build(int l,int r){
    int now = ++cnt;
    tr[now].l = l;
    tr[now].r = r;
    tr[now].lc = tr[now].rc = tr[now].fa = tr[now].
Title - Artist
0:00