题解 P2336 【[SCOI2012]喵星球上的点名】

2020-04-28 17:10:52



[SCOI2012]喵星球上的点名


题意:

N 只猫, M 个点名串 Si, 每一只猫都有一个姓和一个名

如果 Si 是 一只猫姓或名的子串,那么这只猫会在这次点名中答到。

求:

输出M 行 每次点名有多少个喵星人应该答到。

输出N 行 每个喵星人总共被点到多少次。

数据范围:N <= 51e4 M* <=1e5 名字串串长和点名串串长均小于 1e5


题解:

把所有的姓名串和点名串 拼在一起 (SA+get_height+ST)

如果当前点名,这只猫答到了,就说明这只猫的姓/名串的后缀和 Si的lcp为 |Si|

满足后缀和 Si的lcp为 |Si|条件的串在排好序的数组中是一段区间

分两问处理:

1.也就是我们要查询区间的颜色数

我们可以莫队/树状数组 (就是 HH的项链啦)。。。

2.也就是我们要求一只猫的姓名串,被多少个区间包含,

遇到区间左端点 左端点+1 遇到区间右端点 左端点 -1

每新遇到一类数,我们给他 + i的前缀和 - last i 的前缀和 。

这样就做完了 .......


代码:

#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;
}