P2336 [SCOI2012]喵星球上的点名

题目描述

a180285 幸运地被选做了地球到喵星球的留学生。他发现喵星人在上课前的点名现象非常有趣。

假设课堂上有 \(N\) 个喵星人，每个喵星人的名字由姓和名构成。喵星球上的老师会选择 \(M\) 个串来点名，每次读出一个串的时候，如果这个串是一个喵星人的姓或名的子串，那么这个喵星人就必须答到。

然而，由于喵星人的字码过于古怪，以至于不能用 ASCII 码来表示。为了方便描述，a180285 决定用数串来表示喵星人的名字。

现在你能帮助 a180285 统计每次点名的时候有多少喵星人答到，以及 \(M\) 次点名结束后每个喵星人答到多少次吗？

输入输出格式

输入格式：

现在定义喵星球上的字符串给定方法：

先给出一个正整数 \(L\) ，表示字符串的长度，接下来\(L\)个整数表示字符串的每个字符。

输入的第一行是两个整数 \(N\) 和 \(M\)。

接下来有 \(N\) 行，每行包含第 \(i\) 个喵星人的姓和名两个串。姓和名都是标准的喵星球上的字符串。

接下来有 \(M\) 行，每行包含一个喵星球上的字符串，表示老师点名的串。

输出格式：

对于每个老师点名的串输出有多少个喵星人应该答到。

然后在最后一行输出每个喵星人被点到多少次。

说明

\(n\le 5\times 10^4,m\le 10^5\)，串总长\(\le 10^5\)

先建广义SAM

发现点名是子树问题，转换到dfs序

第一问就是区间求颜色数，第二问是统计每种颜色被多少区间覆盖。

用莫队就可以了，在新加入颜色和删去颜色的时候处理一下就行了。

Code:

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <map>

const int N=2e5+10;

std::map <int,int> ch[N];

int col[N],par[N],len[N],las=1,tot=1,id;

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,ch[y]=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,n,m,m_;

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,fi;

    node(){}

    node(int id,int l,int r,int fi){this->id=id,this->l=l,this->r=r,this->fi=fi;}

    bool friend operator <(node a,node b){return a.fi==b.fi?a.l<b.l:a.fi<b.fi;}

}q[N];

int ans[N],sum[N],st[N],tax[N],su;

void add(int p)

{

    int c=col[ha[p]];

    if(!tax[c]) ++su,st[c]=id;

    ++tax[c];

}

void del(int p)

{

    int c=col[ha[p]];

    --tax[c];

    if(!tax[c]) --su,sum[c]+=id-st[c];

}

int main()

{

    scanf("%d%d",&n,&m);

    for(id=1;id<=n;id++)

    {

        int Len;las=1;

        scanf("%d",&Len);

        for(int c,i=1;i<=Len;i++) scanf("%d",&c),extend(c);

        las=1;scanf("%d",&Len);

        for(int c,i=1;i<=Len;i++) scanf("%d",&c),extend(c);

    }

    for(int i=2;i<=tot;i++) add(par[i],i);

    dfs(1);int B=sqrt(dfsclock)+1;

    for(int i=1;i<=m;i++)

    {

        int Len,now=1;

        scanf("%d",&Len);

        for(int c,j=1;j<=Len;j++)

        {

            scanf("%d",&c);

            now=ch[now][c];

        }

        if(now) q[++m_]=node(i,dfn[now],low[now],low[now]/B);

    }

    std::sort(q+1,q+1+m_);

    int l=q[1].l,r=l-1;

    for(id=1;id<=m_;id++)

    {

        while(q[id].l<l) add(--l);

        while(q[id].l>l) del(l++);

        while(q[id].r<r) del(r--);

        while(q[id].r>r) add(++r);

        ans[q[id].id]=su;

    }

    while(l<=r) del(l++);

    for(int i=1;i<=m;i++) printf("%d\n",ans[i]);

    for(int i=1;i<=n;i++) printf("%d ",sum[i]);

    return 0;

}

2019.1.10

巴特西

洛谷 P2336 [SCOI2012]喵星球上的点名解题报告

P2336 [SCOI2012]喵星球上的点名

题目描述

输入输出格式

输入格式：

输出格式：

说明

最新文章

热门文章

巴特西

洛谷 P2336 [SCOI2012]喵星球上的点名 解题报告

P2336 [SCOI2012]喵星球上的点名

题目描述

输入输出格式

输入格式：

输出格式：

说明

最新文章

热门文章

洛谷 P2336 [SCOI2012]喵星球上的点名解题报告