[bzoj3879][后缀自动机][虚树]SvT

本文主要是介绍[bzoj3879][后缀自动机][虚树]SvT，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

(我并不想告诉你题目名字是什么鬼)

有一个长度为n的仅包含小写字母的字符串S,下标范围为[1,n].

现在有若干组询问,对于每一个询问,我们给出若干个后缀(以其在S中出现的起始位置来表示),求这些后缀两两之间的LCP(LongestCommonPrefix)的长度之和.一对后缀之间的LCP长度仅统计一遍.

Input

第一行两个正整数n,m,分别表示S的长度以及询问的次数.

接下来一行有一个字符串S.

接下来有m组询问,对于每一组询问,均按照以下格式在一行内给出:

首先是一个整数t,表示共有多少个后缀.接下来t个整数分别表示t个后缀在字符串S中的出现位置.

Output

对于每一组询问,输出一行一个整数,表示该组询问的答案.由于答案可能很大,仅需要输出这个答案对于23333333333333333(一个巨大的质数)取模的余数.

Sample Input

7 3

popoqqq

1 4

2 3 5

4 1 2 5 6

Sample Output

0

0

2

HINT

样例解释:

对于询问一,只有一个后缀”oqqq”,因此答案为0.

对于询问二,有两个后缀”poqqq”以及”qqq”,两个后缀之间的LCP为0,因此答案为0.

对于询问三,有四个后缀”popoqqq”,”opoqqq”,”qqq”,”qq”,其中只有”qqq”,”qq”两个后缀之间的LCP不为0,且长度为2,因此答案为2.

对于100%的测试数据,有S<=5*10^{5,且Σt<=3*10}6.

特别注意:由于另一世界线的某些参数发生了变化,对于一组询问,即使一个后缀出现了多次,也仅算一次.

题解

存板
题解在SAM的一些题里面…

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
using namespace std;
inline int read()
{int f=1,x=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
int stack[20];
inline void write(LL x)
{if(x<0){putchar('-');x=-x;}if(!x){putchar('0');return;}int top=0;while(x)stack[++top]=x%10,x/=10;while(top)putchar(stack[top--]+'0');
}
inline void pr1(int x){write(x);putchar(' ');}
inline void pr2(LL x){write(x);putchar('\n');}
const int MAXN=2*500005;
struct SAM
{int son[30],dep,parent;
}tr[MAXN];int cnt,lst,root;
void add(int x)
{int np=++cnt,p=lst;tr[np].dep=tr[p].dep+1;while(p&&tr[p].son[x]==0)tr[p].son[x]=np,p=tr[p].parent;if(!p)tr[np].parent=root;else{int q=tr[p].son[x];if(tr[q].dep==tr[p].dep+1)tr[np].parent=q;else{int nq=++cnt;tr[nq]=tr[q];tr[nq].dep=tr[p].dep+1;tr[q].parent=tr[np].parent=nq;while(p&&tr[p].son[x]==q)tr[p].son[x]=nq,p=tr[p].parent;}}lst=np;
}
struct edge{int x,y,next;}a[2*MAXN];int len,last[MAXN];
void ins(int x,int y){len++;a[len].x=x;a[len].y=y;a[len].next=last[x];last[x]=len;}
int bin[25],fa[25][MAXN],dep[MAXN],in[MAXN],pos[MAXN],dfn;
void pre_tree_node(int x)
{in[x]=++dfn;for(int i=1;bin[i]<=dep[x];i++)fa[i][x]=fa[i-1][fa[i-1][x]];for(int k=last[x];k;k=a[k].next){int y=a[k].y;fa[0][y]=x;dep[y]=dep[x]+1;pre_tree_node(y);}
}
int lca(int x,int y)
{if(dep[x]<dep[y])swap(x,y);for(int i=20;i>=0;i--)if(bin[i]<=dep[x]&&dep[fa[i][x]]>=dep[y])x=fa[i][x];if(x==y)return x;for(int i=20;i>=0;i--)if(bin[i]<=dep[x]&&fa[i][x]!=fa[i][y])x=fa[i][x],y=fa[i][y];return fa[0][x];
}
char ch[MAXN];
int m,id[MAXN],vis[MAXN],ok[MAXN],tim,ln;
bool cmp(int n1,int n2){return in[pos[n1]]<in[pos[n2]];}
int sta[MAXN],tp;
void insert(int u)
{if(tp<=1){sta[++tp]=u;return ;}int LA=lca(sta[tp],u);if(LA==sta[tp]){if(sta[tp]!=u)sta[++tp]=u;return ;}while(tp>1&&in[sta[tp-1]]>=in[LA])ins(sta[tp-1],sta[tp]),tp--;if(sta[tp]!=LA)ins(LA,sta[tp]),sta[tp]=LA;sta[++tp]=u;
}
LL ans,tot[MAXN];
int gg[MAXN];
void solve(int x)
{tot[x]=ok[x];ok[x]=0;for(int k=last[x];k;k=a[k].next){int y=a[k].y;solve(y);ans+=1LL*tot[x]*tot[y]*tr[x].dep;tot[x]+=tot[y];}
}
int main()
{bin[0]=1;for(int i=1;i<=20;i++)bin[i]=bin[i-1]<<1;int n=read();m=read();scanf("%s",ch+1);reverse(ch+1,ch+1+n);cnt=lst=root=1;for(int i=1;i<=n;i++)add(ch[i]-'a'+1),pos[i]=lst;for(int i=1;i<=cnt;i++)if(tr[i].parent)ins(tr[i].parent,i);pre_tree_node(1);while(m--){int N=read();tim++;ln=0;for(int i=1;i<=N;i++){int x=n-read()+1;if(vis[x]==tim)continue;vis[x]=tim;id[++ln]=x;ok[pos[x]]=1;}sort(id+1,id+1+ln,cmp);for(int i=1;i<=len;i++)last[a[i].x]=last[a[i].y]=0;len=tp=0;sta[tp=1]=1;for(int i=1;i<=ln;i++)insert(pos[id[i]]);while(tp>1)ins(sta[tp-1],sta[tp]),tp--;ans=0;solve(1);pr2(ans);}return 0;
}