字符串 可持久化线段树 可持久化数据结构 Trie    发布于 2020-02-19   1295人围观   0条评论

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   233人围观   0条评论

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-09-11   523人围观   0条评论

题目大意

给出一个字符串,求出所有回文串的字符种类数之和。

题解

考场上他们都有回文自动机的板子而我没有QAQ

首先对于一个子串,其对应一个子区间,这个子区间的数据的种类数的多少我们是可以用主席树来维护的,这是众所周知的。

具体维护方法:

从第1位置往后扫,如果之前出现过相同的数据,我们就在之前出现过的位置-1,在当前位置计数+1,然后把当前位置记录下来。

但是我们怎么求所有回文串的长度和数目?Manacher是不行的,效率太低了。

于是有一个神奇的PAM,也就是回文自动机。

回文自动机中,cnt[i]表示以i结尾的最长的回文串的数目,len[i]表示以i结尾的回文串的长度为多少,pos[i]表示以i为结尾的回文串在原串的位置是哪里。

这样的PAM的时间复杂度是O(n*log(字符集大小))的

这样我们就很容易能够求得答案了。

最终答案是ans = n + Σ query(root[pos[i]],1,siz,pos[i]-len[i]+1,pos[i]) * cnt[i];

据说还有后缀自动机SAM的做法,这个我也不怎么会……所以就不写了,等以后学QAQ。

如果对回文自动机不了解的可以去找博客https://www.cnblogs.com/nbwzyzngyl/p/8260921.html

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5+10;
typedef long long ll;
struct seg{
    int ch[2];
    int val;
}tr[maxn*25];
int root[maxn];
char s[maxn];
int siz = 0;
struct PAM{
    int p,last,cur,n,S[maxn],len[maxn],pos[maxn],cnt[maxn],fail[maxn];
    int nt[maxn][26];
    int new_node(int l){
        for(int i = 0;i < 26;++i)
            nt[p][i] = 0;
        len[p] = l;
        cnt[p] = 0;
        return p++;
    }
    inline v
查看更多
可持久化线段树    发布于 2019-08-24   733人围观   1条评论

题目大意

给定一个1----n的排列,有以下两种操作:

1.给序列中位置i的数+10000000。

2.询问未在1-----r位置出现过且≥k的最小值。

题目保证1≤k≤ 100000,强制在线。

题解

这场CCPC网络赛可谓有毒,博主这题被卡常卡到心态爆炸。

首先我们来看一下这两个操作分别有什么性质。

根据k≤100000这个条件,我们每做一次1操作,就相当于直接将i位置的数删除掉,也就是i位置的数可取了,毕竟k还是比一千万小很多的。

2操作貌似没什么性质,只是我们要搞的时候注意不能取用1----r之间的所有数就是了。

因为很明显的涉及到时间戳的问题,所以肯定是主席树。

然后最容易想到的是直接用带修主席树,利用权值线段树的思想,维护时间戳r时数字区间x---y之间出现的数的总个数。

这样是nlog2n的做法,貌似有人就这么过了……

可是博主并不会带修主席树。

于是博主想,直接使用普通主席树,既然1操作相当于删除,那么我就用一个set去保存当前所有被删除过的数。在求的时候,先二分答案mid,看k---mid之间是否所有数都出现过,如果没出现过就往左,否则往右,找到最初始的答案。然后再去set里面对k取lower_bound,取两个答案中的最小值。

这个做法是nlog2n的,理论上是能过的,不过……博主比赛的时候被卡常卡到心态炸裂……

于是在比赛后又想……能不能去掉那个二分啊……

于是博主又想到了……主席树反向建立,就是相当于对于每一位讲,每向前推进一位,当前这一位的数就变得可用了。那么我们建立的时候root[n]是完全没有数可用的,root[n-1]可用n位置的数。于是在主席树维护的东西上做了一点变动,不再维护每个权值出现的次数,而是改为:叶子节点的权值如果当前可用,那么就直接保存当前节点的权值,非叶子节点的节点保存所辖权值范围的所有权值中可用权值的最小值。在查询的时候,set的操作还是不变,主席树部分的查询改为,查询时间戳为r时刻的k---n的权值区间可用权值中的最小权值。这样我们就把二分的部分给省去了。整体时间复杂度nlogn。

然后博主满怀信心的交了上去,又迎来了一发TLE。

博主开始怀疑人生了……

博主强行把自己的内存池指针式写法改成数组式写法,并且min函数改为手写min而非stlmin,终于算是卡过去了……1278ms。。。而且还是得使用比较快的取消关联的cin cout。。。

那些不超过1s的

查看更多
二分 可持久化线段树    发布于 2019-08-01   246人围观   0条评论

题目大意

给你一个长为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]内的数的个数,可以使用权值线段树,维护区间内所有数个数总和,然后查询。

但是此题还要求我们在限定的区间[l,r]内去寻找,所以我们就要使用可持久化权值线段树,也就是主席树维护。

主席树的最经典功能就是可以在静态区间内(无修改操作)查询排名第k的数,而这种功能的实现,实际上也是靠权值线段树统计区间内有多少小于x的数来实现的。

所以我们可以直接使用主席树的权值线段树所有的功能,直接寻找区间[l,r]内在范围[p-ans,p+ans]内的数。

(主席树的root[r]为时刻r的权值线段树的根,也就是表示区间1——r存储的权值线段树的根,当理解这一点以后主席树就没有那么难了)。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
using namespace std;
int get_num(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if(c == '-')
        flag = true;
    else num = c - '0';
    while(isdigit(c = getchar()))
        num = (num<<3) + (num<<1) + c - '0';
    return (flag ? -1 
查看更多