题解 P2336 【[SCOI2012]喵星球上的点名】
whyl
2020-04-28 17:10:52
***
[SCOI2012]喵星球上的点名
***
题意：
有 *N* 只猫， *M* 个点名串 *S*i， 每一只猫都有一个姓和一个名
如果 *S*i 是 一只猫姓或名的子串，那么这只猫会在这次点名中答到。
求：
输出*M* 行 每次点名有多少个喵星人应该答到。
输出*N* 行 每个喵星人总共被点到多少次。
数据范围：*N* <= 5*1e4 *M* <=1e5 名字串串长和点名串串长均小于 1e5
***
题解：
把所有的姓名串和点名串 拼在一起 （SA+get_height+ST)
如果当前点名，这只猫答到了，就说明这只猫的姓/名串的后缀和 *S*i的lcp为 |*S*i|
满足后缀和 *S*i的lcp为 |*S*i|条件的串在排好序的数组中是一段区间
分两问处理：
1.也就是我们要查询区间的颜色数
我们可以莫队/树状数组 （就是 HH的项链啦）。。。
2.也就是我们要求一只猫的姓名串，被多少个区间包含，
遇到区间左端点 左端点+1 遇到区间右端点 左端点 -1
每新遇到一类数，我们给他 + i的前缀和 - last i 的前缀和 。
这样就做完了 .......
***
代码：
```c++
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x=0,f=1;
char p=getchar();
while(!isdigit(p)){
if(p=='-') f=-1;
p=getchar();
}
while(isdigit(p)) x=(x<<3)+(x<<1)+(p^48),p=getchar();
return x*f;
}
const int maxn=8e5+5;
int n,m,sa[maxn],height[maxn],st[400005][20],id[maxn],las[maxn],tot[maxn];
int a[maxn],node_cnt,ans[maxn],beg[maxn],inf=10002,rid[maxn];
int tree[maxn],c[maxn],x[maxn],y[maxn],rk[maxn],lg[maxn],lenth[maxn];
vector<pair<int,int> > vec[maxn];
vector<pair<int,int> > vec1[maxn];
inline int lowbit(int i){return (i&(-i));}
inline void add(int i,int x){for(;i<=node_cnt;i+=lowbit(i)) tree[i]+=x;}
inline int ask(int i){int ret=0;for(;i;i-=lowbit(i)) ret+=tree[i];return ret;}
inline void SA(){
for(int i=1;i<=node_cnt;i++) c[x[i]=a[i]]++;
for(int i=1;i<=inf;i++) c[i]+=c[i-1];
for(int i=1;i<=node_cnt;i++) sa[c[x[i]]--]=i;
for(int k=1;k<=node_cnt;k<<=1){
int num=0;
for(int i=node_cnt-k+1;i<=node_cnt;i++) y[++num]=i;
for(int i=1;i<=node_cnt;i++) if(sa[i]>k) y[++num]=sa[i]-k;
for(int i=0;i<=inf;i++) c[i]=0;
for(int i=1;i<=node_cnt;i++) c[x[i]]++;
for(int i=1;i<=inf;i++) c[i]+=c[i-1];
for(int i=node_cnt;i>=1;i--) sa[c[x[y[i]]]--]=y[i];
swap(x,y);num=1;x[sa[1]]=1;
for(int i=2;i<=node_cnt;i++) x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
if(num==node_cnt) break;
inf=num;
}
}
inline void get_height(){
for(int i=1;i<=node_cnt;i++) rk[sa[i]]=i;
int k=0;
for(int i=1;i<=node_cnt;i++){
if(rk[i]==1) continue;
if(k) k--;
int j=sa[rk[i]-1];
for(;i+k<=node_cnt&&j+k<=node_cnt&&a[i+k]==a[j+k];) k++;
height[rk[i]]=k;
}
for(int i=1;i<=node_cnt;i++) st[i][0]=height[i];
for(int i=1;i<=node_cnt;i++) rid[rk[i]]=id[i];
for(int j=1;j<=19;j++) for(int i=1;i+(1<<j)-1<=node_cnt;i++) st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
inline int query(int l,int r){
l++;
if(l>r) return 1e9;
int t=lg[r-l+1];
return min(st[l][t],st[r-(1<<t)+1][t]);
}
inline void find(int i,int len){
int l=1,r=rk[beg[i]],res=0,pos=rk[beg[i]],res1=0;
while(l<=r){
int mid=(l+r)>>1;
if(query(mid,pos)>=len) res=mid,r=mid-1;
else l=mid+1;
}
l=pos;r=node_cnt;
while(l<=r){
int mid=(l+r)>>1;
if(query(pos,mid)>=len) res1=mid,l=mid+1;
else r=mid-1;
}
vec[res1].push_back(make_pair(res,i));
vec1[res].push_back(make_pair(res,1));vec1[res1].push_back(make_pair(res,-1));
}
inline void solve1(){
for(int i=1;i<=node_cnt;i++){
if(rid[i]){
if(las[rid[i]]) add(las[rid[i]],-1);
add(i,1);
las[rid[i]]=i;
}
for(int j=0;j<vec[i].size();j++){
int l=vec[i][j].first,pos=vec[i][j].second;
ans[pos]=ask(i)-ask(l-1);
}
}
}
inline void solve2(){
memset(las,0,sizeof(las));memset(tree,0,sizeof(tree));
for(int i=1;i<=node_cnt;i++){
for(int j=0;j<vec1[i].size();j++){
int pos=vec1[i][j].first,dat=vec1[i][j].second;
add(pos,dat);
}
if(rid[i]){
tot[rid[i]]+=ask(i)-ask(las[rid[i]]);
las[rid[i]]=i;
}
}
}
int main(){
n=read();m=read();
for(int i=1;i<=n;i++){
int len=read();
for(int j=1;j<=len;j++) a[++node_cnt]=read(),id[node_cnt]=i;
a[++node_cnt]=++inf;len=read();
for(int j=1;j<=len;j++) a[++node_cnt]=read(),id[node_cnt]=i;
a[++node_cnt]=++inf;
}
for(int i=1;i<=m;i++){
int len=read();beg[i]=node_cnt+1;lenth[i]=len;
for(int j=1;j<=len;j++) a[++node_cnt]=read();
a[++node_cnt]=++inf;
}
for(int i=2;i<=node_cnt;i++) lg[i]=lg[i>>1]+1;
SA();get_height();
for(int i=1;i<=m;i++) find(i,lenth[i]);
solve1();
for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
solve2();
for(int i=1;i<=n;i++) printf("%d ",tot[i]);
return 0;
}
```