~~我告诉您您可以帮我调吗~~
by FZzzz @ 2020-07-27 19:52:56
就是，加分隔符插 SAM，然后把点名的串丢上去匹配，然后第一问就是子树数颜色，第二问就是问每个颜色被多少个区间包含了，吧/fad
by FZzzz @ 2020-07-27 19:54:00
@[FZzzz](/user/174045) 求讲清楚一点qaq
by huangzirui @ 2020-07-27 19:55:26
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
struct suffix_automotion{
int maxlen[N],link[N],tot,last;
map<int,int> tr[N];
void extend(int id){
int p=last,cur=last=++tot;
maxlen[cur]=maxlen[p]+1;
for(;p && !tr[p][id];p=link[p]) tr[p][id]=cur;
if(!p) link[cur]=1;
else{
int q=tr[p][id];
if(maxlen[p]+1==maxlen[q]) link[cur]=q;
else{
int clone=++tot;
maxlen[clone]=maxlen[p]+1;
link[clone]=link[q];
tr[clone]=tr[q];
for(;p && tr[p][id]==q;p=link[p]) tr[p][id]=clone;
link[cur]=link[q]=clone;
}
}
}
}sam;
int sz[N],vis[N],a[N],ans[N],mark[N];
vector<int> fame[N],name[N];
void color(int u,int col){
while(u&&vis[u]!=col){
sz[u]++;
vis[u]=col;
u=sam.link[u];
}
}
void color2(int u,int col){
while(u&&vis[u]!=col){
ans[col]+=mark[u];
vis[u]=col;
u=sam.link[u];
}
}
int main(){
int n,m,len,x;
sam.tot=1;
int cnt=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
sam.last=1;
scanf("%d",&len);
for(int j=1;j<=len;++j){
scanf("%d",&x);
fame[i].push_back(x);
sam.extend(x);
a[++cnt]=sam.last;
}
sam.last=1;
scanf("%d",&len);
for(int j=1;j<=len;++j){
scanf("%d",&x);
name[i].push_back(x);
sam.extend(x);
a[++cnt]=sam.last;
}
}
cnt=0;
for(int i=1;i<=n;++i){
for(int j=0;j<fame[i].size();++j)
color(a[++cnt],i);
for(int j=0;j<name[i].size();++j)
color(a[++cnt],i);
}
int u=1,flag=1;
while(m--){
scanf("%d",&len);
u=1;flag=1;
for(int i=1;i<=len;++i){
scanf("%d",&x);
if(!sam.tr[u][x]) flag=0;
else u=sam.tr[u][x];
}
if(flag) mark[u]++,printf("%d\n",sz[u]);
else puts("0");
}
cnt=0;
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;++i){
for(int j=0;j<fame[i].size();++j)
color2(a[++cnt],i);
for(int j=0;j<name[i].size();++j)
color2(a[++cnt],i);
}
for(int i=1;i<=n;++i)
printf("%d ",ans[i]);
return 0;
}
```
直接扔代码，扔完就跑真刺激（
by wurzang @ 2020-07-27 19:58:30
@[FZzzz](/user/174045) 没看出来什么是 ”颜色“ 啊 QAQ
by huangzirui @ 2020-07-27 19:58:34
@[huangzirui](/user/35891) 啊，就是拍扁到 dfs 序上面变成区间数颜色，然后第一问就直接 HH 的项链那样做，第二问，如果一个区间是 $[l,r]$，扫描线扫到 $l$ 的时候给 $[l,n]$ 加上 $1$，扫到 $r+1$ 给 $[l,n]$ 减去 $1$，然后一个位置的贡献就是他的权值减去他祖先的权值吧/kk
by FZzzz @ 2020-07-27 20:00:10
第二问也可以线段树合并
by Niko！ @ 2020-07-27 20:00:14
在线段树上打标记
by Niko！ @ 2020-07-27 20:00:29
@[huangzirui](/user/35891) 就是，如果前缀节点的最后一个字符是属于第 $i$ 个人名的，那就把它染成第 $i$ 种颜色/kk
by FZzzz @ 2020-07-27 20:01:07
祖先-->前驱
不知道为啥打错了/kk
by FZzzz @ 2020-07-27 20:01:33