Duff is Mad
给出
n
个字符串S1,S2......Sn ，
q
个询问。
每次询问给定l,r,k, 要求输出
∑ri=loccur(Si,Sk)
,. 其中
occur(S,T)
表示
S
在T中出现的次数。
n,q,∑ni=1|Si|≤105
Solution
考虑建立AC自动机，
fail
指针形成了一棵
par
树。令
End(i)
表示第
i
个字符串对应的结束结点。对于询问
(l,r,k) 其实就是把从
root
到
End(i)
上的所有节点以及他们在
par
树 上的祖先结点里面
Sl→Sr
的结束结点的个数。对于
length(x)>n−−√
的字符串
Sx
，单独DFS一遍，求出
cnt(i)
表示第
End(i)
出现了几次，求
cnt
的前缀和就可以
O(1)
回答
k=x
的询问。对于
length(x)≤n−−√
的字符串
Sx
，在
root
到
End(x)
上的所有节点的相关结点集合中加入
x
<script type="math/tex" id="MathJax-Element-3863">x</script>.DFS整棵树，给所有相关集合中的点的询问加上贡献。需要动态维护前缀和。注意到询问次数比较多，用分块维护。
Code
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#define LL long long
#define CLEAR(xxx) memset(xxx,0,sizeof(xxx))
using namespace std;
const int maxn=
150000;
char s[maxn];
int n,qq,tot=
1,lim;
int Root=
1,len[maxn],End[maxn];
vector<int> word[maxn];
vector<int> sons[maxn];
vector<int> A[maxn];
LL ans[maxn];
struct node{
int Next[
26],fa,fail;
}T[maxn];
struct Ask{
int L,R,id;
Ask(){}
Ask(
int L,
int R,
int id):L(L),R(R),id(id){}
};
vector<Ask> Q[maxn];
queue<int> q;
void Build_AC_Automaton(){
q.push(Root);
int i,j;
while(!q.empty()){
int x= q.front(); q.pop();
for(i=
0;i<
26;i++)
if(T[x].Next[i]){
int v= T[x].Next[i];
for(j=T[x].fail;j && !T[j].Next[i]; j=T[j].fail);
T[v].fail= j? T[j].Next[i]:Root;
q.push(v);
}
}
}
LL sum[maxn],f[maxn];
void dfs(
int x){
int i;
for(i=
0;i<sons[x].size();i++){
dfs(sons[x][i]);
f[x]+=f[sons[x][i]];
}
for(i=
0;i<word[x].size();i++)
sum[word[x][i]]+=f[x];
}
void SolveLongWords(){
int i,j;
for(i=
1;i<=n;i++)
if(len[i]>lim){
CLEAR(sum); CLEAR(f);
for(j=End[i];j;j=T[j].fa) f[j]=
1;
dfs(
1);
for(j=
1;j<=n;j++) sum[j]+=sum[j-
1];
for(j=
0;j<Q[i].size();j++)
ans[Q[i][j].id] = sum[Q[i][j].R]-sum[Q[i][j].L-
1];
}
}
LL Sum[maxn],delta[maxn];
int id[maxn];
void Add(
int x,
int d){
for(
int i=x;id[i]==id[x];i++) Sum[i]+=d;
for(
int i=id[x]+
1;i<=id[n];i++) delta[i]+=d;
}
LL Query(
int x){
return Sum[x]+delta[id[x]];
}
void DFS(
int x){
int i,j;
for(i=
0;i<word[x].size();i++) Add(word[x][i],
1);
for(i=
0;i<A[x].size();i++){
int o = A[x][i];
for(j=
0;j<Q[o].size();j++){
Ask t= Q[o][j];
ans[t.id]+=Query(t.R)-Query(t.L-
1);
}
}
for(i=
0;i<sons[x].size();i++) DFS(sons[x][i]);
for(i=
0;i<word[x].size();i++) Add(word[x][i],-
1);
}
int main(){
int i,j,k,x,y;
scanf(
"%d%d",&n,&qq);
lim= (
int)
sqrt(n);
for(i=
1;i<=n;i++) id[i]=(i-
1)/lim+
1;
for(i=
1;i<=n;i++){
scanf(
"%s",s+
1);
len[i]=
strlen(s+
1);
int cur= Root;
for(j=
1;j<=len[i];j++){
int c= s[j]-
'a';
if(!T[cur].Next[c])
T[cur].Next[c]= ++tot,T[tot].fa=cur;
cur= T[cur].Next[c];
if(len[i]<=lim) A[cur].push_back(i);
}
End[i] = cur;
word[cur].push_back(i);
}
Build_AC_Automaton();
for(i=
1;i<=tot;i++) sons[T[i].fail].push_back(i);
for(i=
1;i<=qq;i++){
scanf(
"%d%d%d",&x,&y,&k);
Q[k].push_back(Ask(x,y,i));
}
SolveLongWords();
DFS(
1);
for(i=
1;i<=qq;i++)
printf(
"%I64d\n",ans[i]);
return 0;
}
