SP8093 JZPGYZ - Sevenk Love Oimaster
题目大意
给定(n(nle 10000))个模板串，以及(m(mle 60000))个查询串（模板串总长(le 100000)，询问串总长(le 360000)）
依次查询每一个查询串是多少个模板串的子串
先对模板串建广义SAM（每次新串las=1的那种）
然后考虑每个点都有一个所属的模板串，它可以对par树上到跟的那条链产生贡献，可以暴力加，据说均摊(O(nsqrt n))，不清楚...
反正是链的问题，不如直接转换成子树问题。
然后发现询问就变成了查询某个点子树和，放到dfs序上发现是区间数颜色，可以离线
于是像HH的项链那样直接树状数组维护一下就可以了。
Code:
#include <cstdio>
#include <cstring>
#include <algorithm>
const int N=2e5+10;
int len[N],par[N],ch[N][26],col[N],id,tot=1,las=1;
void extend(int c)
{
int now=++tot,p=las;
len[now]=len[p]+1,col[now]=id;
while(p&&!ch[p][c]) ch[p][c]=now,p=par[p];
if(!p) par[now]=1;
else
{
int x=ch[p][c];
if(len[x]==len[p]+1) par[now]=x;
else
{
int y=++tot;
len[y]=len[p]+1,par[y]=par[x],col[y]=id;
memcpy(ch[y],ch[x],sizeof ch[x]);
while(p&&ch[p][c]==x) ch[p][c]=y,p=par[p];
par[now]=par[x]=y;
}
}
las=now;
}
int head[N],to[N],Next[N],cnt;
void add(int u,int v)
{
to[++cnt]=v,Next[cnt]=head[u],head[u]=cnt;
}
int dfn[N],low[N],ha[N],dfsclock;
void dfs(int now)
{
ha[dfn[now]=++dfsclock]=now;
for(int i=head[now];i;i=Next[i]) dfs(to[i]);
low[now]=dfsclock;
}
struct node
{
int id,l,r;
node(){}
node(int id,int l,int r){this->id=id,this->l=l,this->r=r;}
bool friend operator <(node n1,node n2){return n1.r<n2.r;}
}q[N];
int n,m,m_,pre[N],su[N],ans[N];
char s[N];
void modify(int x,int d){while(x<=dfsclock)su[x]+=d,x+=x&-x;}
int query(int x){int s=0;while(x)s+=su[x],x-=x&-x;return s;}
int main()
{
scanf("%d%d",&n,&m);
for(id=1;id<=n;id++)
{
scanf("%s",s+1);
las=1;int k=strlen(s+1);
for(int j=1;j<=k;j++) extend(s[j]-'a');
}
for(int i=2;i<=tot;i++) add(par[i],i);
dfs(1);
for(int i=1;i<=m;i++)
{
scanf("%s",s+1);
int now=1,k=strlen(s+1);
for(int j=1;j<=k;j++)
{
now=ch[now][s[j]-'a'];
if(!now) break;
}
if(now) q[++m_]=node(i,dfn[now],low[now]);
}
std::sort(q+1,q+1+m_);
for(int j=1,i=1;i<=dfsclock;i++)
{
int color=col[ha[i]];
if(pre[color]) modify(pre[color],-1);
modify(pre[color]=i,1);
while(j<=m_&&q[j].r<=i) ans[q[j].id]=query(q[j].r)-query(q[j].l-1),++j;
}
for(int i=1;i<=m;i++) printf("%d
",ans[i]);
return 0;
}
2019.1.10