bzoj2754 scoi2012 喵星球的點名

http://www.elijahqi.win/archives/615

題目描述

a180285 幸運地被選做了地球到喵星球的留學生。他發現喵星人在上課前的點名現象非常有趣。

假設課堂上有 N 個喵星人，每個喵星人的名字由姓和名構成。喵星球上的老師會選擇M 個串來點名，每次讀出一個串的時候，如果這個串是一個喵星人的姓或名的子串，那麼這個喵星人就必須答到。

然而，由于喵星人的字碼過于古怪，以至于不能用 ASCII 碼來表示。為了友善描述，a180285 決定用數串來表示喵星人的名字。

現在你能幫助 a180285 統計每次點名的時候有多少喵星人答到，以及 M 次點名結束後每個喵星人答到多少次嗎？

輸入輸出格式

輸入格式：

現在定義喵星球上的字元串給定方法：

先給出一個正整數 L ，表示字元串的長度，接下來L個整數表示字元串的每個字元。

輸入的第一行是兩個整數 N 和 M。

接下來有 N 行， 每行包含第 i 個喵星人的姓和名兩個串。 姓和名都是标準的喵星球上的字元串。

接下來有 M 行，每行包含一個喵星球上的字元串，表示老師點名的串。

輸出格式：

對于每個老師點名的串輸出有多少個喵星人應該答到。

然後在最後一行輸出每個喵星人被點到多少次。

輸入輸出樣例

輸入樣例#1：

2 3

6 8 25 0 24 14 8 6 18 0 10 20 24 0

7 14 17 8 7 0 17 0 5 8 25 0 24 0

4 8 25 0 24

4 7 0 17 0

4 17 0 8 25

輸出樣例#1：

2

1

1 2

說明

事實上樣例給出的資料如果翻譯成地球上的語言可以這樣來看

2 3 izayoi sakuya

orihara izaya

izay hara raiz

對于 30%的資料，保證：

1<=N,M<=1000,喵星人的名字總長不超過 4000，點名串的總長不超過 2000，

對于 100%的資料，保證：

1<=N<=20000 ，1<=M<=50000. 喵星人的名字總長和點名串的總長分别不超過100000,保證喵星人的字元串中作為字元存在的數不超過 10000

有了之前的經曆，二分的速度似乎還不如暴力搞搞速度快呢

這裡相比上一個tjoi2013需要限制一下不要查到問詢的字元串裡去 并且假如是屬于同一塊那麼tmp記錄的答案隻統計一次

#include<cstdio>
#include<cstring>
#define N 2020010
inline int read(){
    int x=;char ch=getchar();
    while (ch<'0'||ch>'9') ch=getchar();
    while (ch<='9'&&ch>='0') {x=x*10+ch-'0';ch=getchar();}
    return x;
}
int n,m,a[N],n1,m1,bl[N],count[N],rank[N<<],rank1[N],sa[N],height[N],k,tmp[N],visit[N],ans[N];
struct node{
    int st,len;
}data[];
int main(){
//    freopen("2336.in","r",stdin);
    n1=read();m1=read();n=;m=;
    for (int i=;i<=n1;++i){
        int tmp=read();
        for (int j=;j<tmp;++j) a[n+j]=read(),bl[n+j]=i;n+=tmp;a[n++]=++m;
        tmp=read();
        for (int j=;j<tmp;++j) a[n+j]=read(),bl[n+j]=i;n+=tmp;a[n++]=++m;
    }int last=n-;
    for (int i=;i<=m1;++i){
        int tmp=read();
        data[i].st=n;data[i].len=tmp;
        for (int j=;j<tmp;++j) a[n+j]=read();n+=tmp;a[n++]=++m;
    }n-=;
//    printf("%d\n",n);
    //for (int i=;i<=n;++i) printf("%d\n",a[i]);
    for (int i=;i<=n;++i) count[a[i]]=;
    for (int i=;i<=m;++i) count[i]+=count[i-];
    for (int i=;i<=n;++i) rank[i]=count[a[i]];
    k=;count[]=;
    for (int p=;k!=n;p<<=,m=k){
        for (int i=;i<=m;++i) count[i]=;
        for (int i=;i<=n;++i) count[rank[i+p]]++;
        for (int i=;i<=m;++i) count[i]+=count[i-];
        for (int i=n;i>=;--i) tmp[count[rank[i+p]]--]=i;
        for (int i=;i<=m;++i) count[i]=;
        for (int i=;i<=n;++i) count[rank[i]]++;
        for (int i=;i<=m;++i) count[i]+=count[i-];
        for (int i=n;i>=;--i) sa[count[rank[tmp[i]]]--]=tmp[i];
        memcpy(rank1,rank,sizeof(rank)>>);
        rank[sa[]]=k=;
        for (int i=;i<=n;++i){
            if (rank1[sa[i]]!=rank1[sa[i-]]||rank1[sa[i]+p]!=rank1[sa[i-]+p]) ++k;
            rank[sa[i]]=k;
        }
    }
    k=;
    for (int i=;i<=n;++i){
        if (rank[i]==) continue;
        k=k==?:k-;
        while (a[i+k]==a[sa[rank[i]-]+k]) ++k;
        height[rank[i]]=k;
    }
//    for (int i=;i<=n;++i) printf("%d ",sa[i]);printf("\n");
//    for (int i=;i<=n;++i) printf("%d ",height[i]);
    for (int i=;i<=m1;++i){
        int l=rank[data[i].st],r=rank[data[i].st]+;
        while (height[l]>=data[i].len) --l;
        while (height[r]>=data[i].len) ++r;--r;
        int tmp=;
        for (int j=l;j<=r;++j){
            if (sa[j]>last) continue;//超過了答案尋找的範圍
            if (visit[bl[sa[j]]]==i) continue; 
            tmp++;ans[bl[sa[j]]]++;visit[bl[sa[j]]]=i;
        }
        printf("%d\n",tmp);
    }
    for (int i=;i<=n1;++i) printf("%d ",ans[i]);
    return ;
}
           

二分查找x

#include<cstdio>
#include<cstring>
#define N 2020010
inline int read(){
    int x=;char ch=getchar();
    while (ch<'0'||ch>'9') ch=getchar();
    while (ch<='9'&&ch>='0') {x=x*10+ch-'0';ch=getchar();}
    return x;
}
int n,m,a[N],n1,m1,bl[N],count[N],rank[N<<],rank1[N],sa[N],height[N],k,tmp[N],visit[N],ans[N],l,r,fmin[N][],Log[N];
struct node{
    int st,len;
}data[];
inline int min(int x,int y){return x<y?x:y;}
inline int lcp(int x,int y){
    x++;int t=Log[y-x+];
    return min(fmin[x][t],fmin[y-(<<t)+][t]);
}
void check(int st,int len){
    int l1,r1;
    if (height[st]<len) l1=st;else{
        int ll=,rr=st-;
        while (ll<=rr){
            int mid=(ll+rr)>>;
            if(lcp(mid,st)>=len) rr=mid-;else ll=mid+;
        }
        l1=ll;
    }
    if (height[st+]<len) r1=st;else{
        int ll=st+,rr=n;
        while (ll<=rr){
            int mid=(ll+rr)>>;
            if (lcp(st,mid)>=len) ll=mid+;else rr=mid-;
        }
        r1=rr;
    }
    l=l1;r=r1;
}
int main(){
    freopen("2336.in","r",stdin);
    n1=read();m1=read();n=;m=;
    for (int i=;i<=n1;++i){
        int tmp=read();
        for (int j=;j<tmp;++j) a[n+j]=read(),bl[n+j]=i;n+=tmp;a[n++]=++m;
        tmp=read();
        for (int j=;j<tmp;++j) a[n+j]=read(),bl[n+j]=i;n+=tmp;a[n++]=++m;
    }int last=n-;
    for (int i=;i<=m1;++i){
        int tmp=read();
        data[i].st=n;data[i].len=tmp;
        for (int j=;j<tmp;++j) a[n+j]=read();n+=tmp;a[n++]=++m;
    }n-=;
//  printf("%d\n",n);
    //for (int i=;i<=n;++i) printf("%d\n",a[i]);
    for (int i=;i<=n;++i) count[a[i]]=;
    for (int i=;i<=m;++i) count[i]+=count[i-];
    for (int i=;i<=n;++i) rank[i]=count[a[i]];
    k=;count[]=;
    for (int p=;k!=n;p<<=,m=k){
        for (int i=;i<=m;++i) count[i]=;
        for (int i=;i<=n;++i) count[rank[i+p]]++;
        for (int i=;i<=m;++i) count[i]+=count[i-];
        for (int i=n;i>=;--i) tmp[count[rank[i+p]]--]=i;
        for (int i=;i<=m;++i) count[i]=;
        for (int i=;i<=n;++i) count[rank[i]]++;
        for (int i=;i<=m;++i) count[i]+=count[i-];
        for (int i=n;i>=;--i) sa[count[rank[tmp[i]]]--]=tmp[i];
        memcpy(rank1,rank,sizeof(rank)>>);
        rank[sa[]]=k=;
        for (int i=;i<=n;++i){
            if (rank1[sa[i]]!=rank1[sa[i-]]||rank1[sa[i]+p]!=rank1[sa[i-]+p]) ++k;
            rank[sa[i]]=k;
        }
    }
    k=;
    Log[]=-;
    for (int i=;i<=n;++i) Log[i]=Log[i>>]+;
    for (int i=;i<=n;++i){
        if (rank[i]==) continue;
        k=k==?:k-;
        while (a[i+k]==a[sa[rank[i]-]+k]) ++k;
        height[rank[i]]=k;
    }
    for (int i=;i<=n;++i) fmin[i][]=height[i];
    for (int j=;j<=Log[n];++j){
        for (int i=;i<=n-(<<j)+;++i){
            fmin[i][j]=min(fmin[i][j-],fmin[i+(<<(j-))][j-]);
        }
    }
//  for (int i=;i<=n;++i) printf("%d ",sa[i]);printf("\n");
//  for (int i=;i<=n;++i) printf("%d ",height[i]);
    for (int i=;i<=m1;++i){
        check(rank[data[i].st],data[i].len);
        int tmp=;
        for (int j=l;j<=r;++j){
            if (sa[j]>last) continue;//超過了答案尋找的範圍
            if (visit[bl[sa[j]]]==i) continue; 
            tmp++;ans[bl[sa[j]]]++;visit[bl[sa[j]]]=i;
        }
        printf("%d\n",tmp);
    }
    for (int i=;i<=n1;++i) printf("%d ",ans[i]);
    return ;
}