luogu SP8093 后缀自动机+树状数组+dfs序

2020-12-13 15:17

阅读：267

标签：char define void turn 自动机 fine sqrt bit ++

这题解法很多，简单说几个：

1. 线段树合并，时间复杂度是 $O(nlog^2n)$ 的.

2. 暴力跳 $fail,$ 时间复杂度 $O(n\sqrt n),$ 比较暴力.

3. 建立后缀树后在 $dfs$ 序上数点，时间复杂度为 $O(nlogn),$ 十分优秀.

Code:

#include   
#define N 200007    
#define setIO(s) freopen(s".in","r",stdin) , freopen(s".out","w",stdout)    
using namespace std;          
struct ques
{ 
    int l,r,id;  
    ques(int l=0,int r=0,int id=0):l(l),r(r),id(id){}    
}q[N];  
struct P 
{ 
    int len,f,ch[27];
    vectorv;     
}t[NG[N];        
int tot,last,edges,tim,cnt;     
int hd[N],to[N],nex[N],st[N],ed[N],size[N],dfn[N],lst[N],C[N],answer[N];      
int lowbit(int t) 
{
    return t&(-t); 
}    
void update(int x,int delta) 
{
    for(;x0;x-=lowbit(x)) tmp+=C[x];  
    return tmp;     
}
bool cmp(ques a,ques b) 
{
    return a.r

luogu SP8093 后缀自动机+树状数组+dfs序

标签：char define void turn 自动机 fine sqrt bit ++

原文地址：https://www.cnblogs.com/guangheli/p/11577267.html

上一篇：C# login with cookie and fiddler2

下一篇：C#常用的命名规范

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：luogu SP8093 后缀自动机+树状数组+dfs序
文章链接：http://soscw.com/essay/34988.html

亲，登录后才可以留言！

luogu SP8093 后缀自动机+树状数组+dfs序

评论

热门文章

推荐文章

最新文章

置顶文章