-
题解们：
- 1.首先可以被很多暴力给搞过去；我以前也是这样水过去的
-
2.ac自动机
- 2.1
- 抽离fail树
- 对点名建自动机，建$fail$树的时候只保留询问节点；
- 对于一个喵，子串==在自动机里匹配到的所有节点的$fail$祖先并
- 把姓和名都放到里面去跑，得到所有的点，需要把这些点在新的$fail$树里的祖先全部标记
- 具体按照dfs序排序，每个点$q[i]$的贡献就是$lca(q[i-1],q[i])$到$q[i]$那段
- 统计第一问用树上差分$q[i]$处$++$，$lca(q[i-1],q[i])$处$--$，具体第二问直接记录每个点到根有多少次点名统计直接相减；
- $O(N \ log N)$
#include<bits/stdc++.h>
#define rg register
#define il inline
#define Run(i,l,r) for(rg int i=l;i<=r;i++)
#define Don(i,l,r) for(rg int i=l;i>=r;i--)
using namespace std;
const int N=;
int n,m,o=,hd[N],a[N],b[N],s[N],tot,fl[N],fa[N],st[N],ed[N],idx;
int val[N],vis[N],que[N],head,tail,sz,cnt,size[N],tp[N],dep[N],pos[N],ans[N],deep[N];
il bool cmp(const int&x,const int&y){return st[x]<st[y];}
map<int,int>ch[N];
map<int,int>::iterator it;
struct Edge{int v,nt;}E[N];
il void adde(int u,int v){E[o]=(Edge){v,hd[u]};hd[u]=o++;}
il char gc(){
static char*p1,*p2,s[];
if(p1==p2)p2=(p1=s)+fread(s,,,stdin);
return(p1==p2)?EOF:*p1++;
}
il int rd(){
int x=,f=; char c=gc();
while(c<''||c>''){if(c=='-')f=-;c=gc();}
while(c>=''&&c<='')x=(x<<)+(x<<)+c-'',c=gc();
return x*f;
}
void get_fl(){
for(it=ch[].begin();it!=ch[].end();it++){
int v=it->second;
que[++tail]=v;
if(vis[v])adde(fa[v],v),size[v]=;
}
while(head < tail){
int u=que[++head];
for(it = ch[u].begin();it!=ch[u].end();it++){
int v = it->second, c = it->first, w=fl[u];
while(w&&!ch[w].count(c))w=fl[w];
if(!ch[w].count(c))fl[v]=;
else fl[v]=ch[w][c];
if(vis[fl[v]])fa[v]=fl[v];
else fa[v]=fa[fl[v]];
que[++tail]=v;
if(vis[v])adde(fa[v],v),size[v]=;
}
}
Don(i,tail,)size[fa[que[i]]]+=size[que[i]];
}
void dfs(int u,int T){
int son=;
st[u]=++idx;tp[u]=T;
dep[u]=dep[fa[u]]+;
deep[u]=deep[fa[u]]+vis[u];
for(int i=hd[u];i;i=E[i].nt){
int v=E[i].v;
if(!son||size[v]>size[son])son=v;
}
if(son)dfs(son,T);
for(int i=hd[u];i;i=E[i].nt){
int v=E[i].v;
if(son!=v)dfs(v,v);
}
ed[u]=idx;
}
il int lca(int x,int y){
int tx=tp[x],ty=tp[y];
while(tx!=ty){
if(dep[tx]<dep[ty])y=fa[ty],ty=tp[y];
else x=fa[tx],tx=tp[x];
}
return dep[x]<dep[y]?x:y;
}
void find(int len){
int x = , c;
Run(i,,len){
c = s[tot+i];
while(x&&!ch[x].count(c))x=fl[x];
if(!ch[x].count(c))x=;
else x=ch[x][c];
if(vis[x])que[++tail]=x;
else if(fa[x])que[++tail]=fa[x];
}
tot+=len;
}
void dfs(int u){
for(int i=hd[u];i;i=E[i].nt)
dfs(E[i].v),val[u]+=val[E[i].v];
}
int main(){
freopen("bzoj2754.in","r",stdin);
freopen("bzoj2754.out","w",stdout);
n=rd(); m=rd();
Run(i,,n){
a[i]=rd();Run(j,,a[i])s[++tot]=rd();
b[i]=rd();Run(j,,b[i])s[++tot]=rd();
}
Run(i,,m){
int x=rd(),u=,y;
Run(j,,x){
if(!ch[u][y=rd()])ch[u][y]=++sz;
u=ch[u][y];
}
vis[pos[i]=u]++;
}
get_fl();
dfs(,);
tot=;
Run(i,,n){
tail=;
find(a[i]),find(b[i]);
if(!tail)continue;
sort(que+,que+tail+,cmp);
head=;
Run(j,,tail){
if(!head||ed[que[j]]>ed[que[head]])head++;
que[head]=que[j];
}
tail=head;
val[]--,val[que[]]++;
ans[i]+=deep[que[]];
Run(j,,tail){
int tmp = lca(que[j-],que[j]);
val[tmp]--,val[que[j]]++;
ans[i] += deep[que[j]] - deep[tmp];
}
}
dfs();
Run(i,,m)printf("%d\n",val[pos[i]]);
Run(i,,n)printf("%d ",ans[i]);
return ;
}AC
-
3.后缀数组
- 3.1
- 莫队
- 将所有串用互不相等的连接符链接，为了方便让点名串后的连接符尽量小；
- 可以在SA里求出每次点名的区间，是后缀$i \ rank[i]$向后的一段；
- 问题变成统计 ①一个线段里有多少种颜色的点和 ②一种颜色的点被多少条线段覆盖；
- ①莫队模板；
- ②因为每个区间都是不同的，考虑差分，每次从莫队的区间里加入一个颜色就加上剩余的区间数，删去就减掉，就统计了中间出现的那段区间数；
- $O(N \ \sqrt N)$
- 3.2
- 树状数组
- SA的部分一样
- ①扫一遍，$pre[i]$表示倒着上一个扫到的和sa[i]颜色相同的位置，遇到一个每次$add(i,1)$,$add(pre[i],-1)$，直接统计对应区间；
- ②扫一遍，对于区间$[L,R]$，在$R$的位置$add(R,1)$ ，$L-1$的位置$add(L,-1)$ ，统计$i$到$pre[i]-1$的数量;
- 均可树状数组维护
- $O(N \ log N)$
#include<bits/stdc++.h>
#define il inline
#define rg register
using namespace std;
const int N=,M=;
int n,m,len,cnt,s[N],sub[N],tot,sa[N],ht[N],rk[N],pre[N],bl[N],pos[N],f[N][M],bin[M],l[N],mp[N],c[N],ans1[N],ans2[N];
struct data{
int x,y,z;
bool operator <(const data&A)const{return x < A.x;};
}p[N];
il char gc(){
static char*p1,*p2,s[];
if(p1==p2)p2=(p1=s)+fread(s,,,stdin);
return(p1==p2)?EOF:*p1++;
}
il int rd(){
int x=,f=; char ch=gc();
while(ch<''||ch>''){if(ch=='-')f=-;ch=gc();}
while(ch>=''&&ch<='')x=(x<<)+(x<<)+ch-'',ch=gc();
return x*f;
}
il void add(int x,int y){for(rg int i=x+;i<=len;i+=i&-i)c[i]+=y;}
il int que(int x){int re=;for(rg int i=x+;i;i-=i&-i)re+=c[i];return re;}
void discretize(){
sort(sub,sub+tot);
tot=unique(sub,sub+tot)-sub;
for(rg int i=;i<len;i++)s[i]=lower_bound(sub,sub+tot,s[i])-sub;
}
void build_sa(){
static int x[N],y[N],w[N];
for(rg int i=;i<len;i++)w[x[i]=s[i]]++;
for(rg int i=;i<tot;i++)w[i]+=w[i-];
for(rg int i=len-;~i;i--)sa[--w[x[i]]]=i;
for(rg int k=;k<len;k<<=){
int p = ;
for(rg int i=len-k;i<len;i++)y[p++]=i;
for(rg int i=;i<len;i++)if(sa[i]>=k)y[p++]=sa[i]-k;
for(rg int i=;i<tot;i++)w[i]=;
for(rg int i=;i<len;i++)w[x[i]]++;
for(rg int i=;i<tot;i++)w[i]+=w[i-];
for(rg int i=len-;~i;i--)sa[--w[x[y[i]]]]=y[i];
swap(x,y);
x[sa[]]=; p=;
for(rg int i=;i<len;i++){
x[sa[i]] = y[sa[i]]==y[sa[i-]]&&y[sa[i]+k]==y[sa[i-]+k] ? p - : p++;
}
if(p==len)break;
tot = p + ;
}
}
void build_ht(){
for(rg int i=;i<len;i++)rk[sa[i]]=i;
for(rg int i=,k=,j;i<len;i++){
if(k)k--;
j=sa[rk[i]-];
while(s[j+k]==s[i+k])k++;
f[rk[i]][]=ht[rk[i]]=k;
}
}
void build_rmq(){
for(rg int i=;i<;i++)
for(rg int j=;j<=len-bin[i];j++){
f[j][i] = min(f[j][i-],f[j+bin[i-]][i-]);
}
}
int main(){
freopen("bzoj2754.in","r",stdin);
freopen("bzoj2754.out","w",stdout);
for(int i=bin[]=;i<;i++)bin[i]=bin[i-]<<;
n=rd(); m=rd();
for(rg int i=,x;i<=n;i++){
x=rd();
for(rg int j=;j<=x;j++){
bl[len]=i;
sub[tot++]=s[len++]=rd();
}sub[tot++]=s[len]=-len,len++;
x=rd();
for(rg int j=;j<=x;j++){
bl[len]=i;
sub[tot++]=s[len++]=rd();
}sub[tot++]=s[len]=-len,len++;
}
for(rg int i=,x;i<=m;i++){
l[i]=x=rd();
bl[len]=-i;
for(rg int j=;j<=x;j++){
sub[tot++]=s[len++]=rd();
}sub[tot++]=s[len]=-len,len++;
}
discretize();
build_sa();
build_ht();
build_rmq();
for(rg int i=len-;~i;i--)if(bl[sa[i]]>){
int x = bl[sa[i]];
if(!mp[x])add(mp[x]=i,);
else{
pre[i]=mp[x],mp[x]=i;
add(pre[i],-),add(i,);
}
}else if(bl[sa[i]]<){
int x=-bl[sa[i]],y=i+;
for(rg int j=;~j;j--)if(f[y][j]>=l[x])y+=bin[j];
p[++cnt]=(data){y-,y-,};
p[++cnt]=(data){i-,y-,-};
ans1[x] = que(y-) - que(i-);
}
memset(c,,sizeof(c));
sort(p+,p+cnt+);
for(rg int i=len-,j=cnt;~i;i--){
while(j&&p[j].x==i)add(p[j].y,p[j].z),j--;
if(bl[sa[i]]>){
if(!pre[i])pre[i]=len;
ans2[bl[sa[i]]] += que(pre[i]-) - que(i-);
}
}
for(rg int i=;i<=m;i++)printf("%d\n",ans1[i]);
for(rg int i=;i<=n;i++)printf("%d ",ans2[i]);
return ;
}SA+BIT
-
4.后缀自动机
- 4.1
- 广义后缀自动机
- 至少这题和$SAM$差不多，只是新加一个单词重置$last$节点；
- 对点名串建出$SAM$之后，把姓名串在上面跑，对走过的点沿$parent$树向上跳可以找到所有子串，标记是否来过暴力统计；
- 这样两个问的方法是一样的
- $O(N \ \sqrt N )$
- 4.2
- 但其实如果建出$parent$树的话就和$1$一样，如果对$parent$树做$dfs$序维护的话就和$2$一样了，不说了；
#include<bits/stdc++.h>
#define rg register
#define il inline
using namespace std;
const int N=;
int n,m,s[N],tot,a[N],b[N],lst,cnt,pa[N],len[N],sum[N],val[N],vis[N],ans;
map<int,int>ch[N];
il char gc(){
static char*p1,*p2,s[];
if(p1==p2)p2=(p1=s)+fread(s,,,stdin);
return(p1==p2)?EOF:*p1++;
}
il int rd(){
int x=,f=; char c=gc();
while(c<''||c>''){if(c=='-')f=-;c=gc();}
while(c>=''&&c<='')x=(x<<)+(x<<)+c-'',c=gc();
return x*f;
}
il void ins(int x){
int p=lst,np; len[np=lst=++cnt]=len[p]+;
while(p&&!ch[p][x])ch[p][x]=np,p=pa[p];
if(!p){pa[np]=;return;}
int q = ch[p][x];
if(len[q]==len[p]+)pa[np]=q;
else{
int nq=++cnt;
len[nq]=len[p]+;
ch[nq]=ch[q];
pa[nq]=pa[q]; pa[q]=pa[np]=nq;
while(p&&ch[p][x]==q)ch[p][x]=nq,p=pa[p];
}
}
il void update(int x,int y){while(x&&vis[x]!=y)sum[x]++,vis[x]=y,x=pa[x];}
il void query(int x,int y){while(x&&vis[x]!=y)ans+=val[x],vis[x]=y,x=pa[x];}
int main(){
freopen("lg2336.in", "r", stdin);
freopen("lg2336.out","w",stdout);
n=rd();m=rd();
cnt=;
for(rg int i=;i<=n;i++){
lst=;a[i]=rd();
for(rg int j=;j<=a[i];j++)ins(s[++tot]=rd());
lst=;b[i]=rd();
for(rg int j=;j<=b[i];j++)ins(s[++tot]=rd());
}
tot=;
for(rg int i=;i<=n;i++){
for(rg int j=,now=;j<=a[i];j++)update(now=ch[now][s[++tot]],i);
for(rg int j=,now=;j<=b[i];j++)update(now=ch[now][s[++tot]],i);
}
for(rg int i=,l,now;i<=m;i++){
l=rd();
now=;
for(rg int j=,x;j<=l;j++){
x=rd();
if(!now)continue;
if(!ch[now].count(x))now=;
else now=ch[now][x];
}
if(now)val[now]++;
printf("%d\n",sum[now]);
}
tot=;
for(rg int i=;i<=n;i++){
ans=;
for(rg int j=,now=;j<=a[i];j++)query(now=ch[now][s[++tot]],n+i);
for(rg int j=,now=;j<=b[i];j++)query(now=ch[now][s[++tot]],n+i);
printf("%d ",ans);
}
return ;
}SAM
- 就数据来看，最快的应该是$3.1$(我没写QAQ)，再来就是$2.1，4.1，3.2$，，不算$map$的话$tarjan$写lca，理论最好的应该是$2.1$ ；