【bzoj2754】【scoi2012】喵星球上的点名

时间:2023-01-23 08:56:55

【bzoj2754】【scoi2012】喵星球上的点名

  • 题解们:

    • 1.首先可以被很多暴力给搞过去;我以前也是这样水过去的
    • 2.ac自动机
      • 2.1
      • 抽离fail树
      • 对点名建自动机,建$fail$树的时候只保留询问节点;
      • 对于一个喵,子串==在自动机里匹配到的所有节点的$fail$祖先并
      • 把姓和名都放到里面去跑,得到所有的点,需要把这些点在新的$fail$树里的祖先全部标记
      • 具体按照dfs序排序,每个点$q[i]$的贡献就是$lca(q[i-1],q[i])$到$q[i]$那段
      • 统计第一问用树上差分$q[i]$处$++$,$lca(q[i-1],q[i])$处$--$,具体第二问直接记录每个点到根有多少次点名统计直接相减;
      • $O(N \ log N)$
      • 【bzoj2754】【scoi2012】喵星球上的点名【bzoj2754】【scoi2012】喵星球上的点名
          1 #include<bits/stdc++.h>
          2 #define rg register
          3 #define il inline 
          4 #define Run(i,l,r) for(rg int i=l;i<=r;i++)
          5 #define Don(i,l,r) for(rg int i=l;i>=r;i--)
          6 using namespace std;
          7 const int N=200010;
          8 int n,m,o=1,hd[N],a[N],b[N],s[N],tot,fl[N],fa[N],st[N],ed[N],idx;
          9 int val[N],vis[N],que[N],head,tail,sz,cnt,size[N],tp[N],dep[N],pos[N],ans[N],deep[N];
         10 il bool cmp(const int&x,const int&y){return st[x]<st[y];}
         11 map<int,int>ch[N];
         12 map<int,int>::iterator it;
         13 struct Edge{int v,nt;}E[N];
         14 il void adde(int u,int v){E[o]=(Edge){v,hd[u]};hd[u]=o++;}
         15 il char gc(){
         16     static char*p1,*p2,s[1000000];
         17     if(p1==p2)p2=(p1=s)+fread(s,1,1000000,stdin);
         18     return(p1==p2)?EOF:*p1++;
         19 }
         20 il int rd(){
         21     int x=0,f=1; char c=gc();
         22     while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc();}
         23     while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+c-'0',c=gc();
         24     return x*f;
         25 }
         26 void get_fl(){
         27     for(it=ch[0].begin();it!=ch[0].end();it++){
         28         int v=it->second;
         29         que[++tail]=v;
         30         if(vis[v])adde(fa[v],v),size[v]=1;
         31     }
         32     while(head < tail){
         33         int u=que[++head];
         34         for(it = ch[u].begin();it!=ch[u].end();it++){
         35             int v = it->second, c = it->first, w=fl[u];
         36             while(w&&!ch[w].count(c))w=fl[w];
         37             if(!ch[w].count(c))fl[v]=0;
         38             else fl[v]=ch[w][c];
         39             if(vis[fl[v]])fa[v]=fl[v];
         40             else fa[v]=fa[fl[v]];
         41             que[++tail]=v;
         42             if(vis[v])adde(fa[v],v),size[v]=1;
         43         }
         44     }
         45     Don(i,tail,1)size[fa[que[i]]]+=size[que[i]];
         46 }
         47 void dfs(int u,int T){
         48     int son=0;
         49     st[u]=++idx;tp[u]=T;
         50     dep[u]=dep[fa[u]]+1;
         51     deep[u]=deep[fa[u]]+vis[u];
         52     for(int i=hd[u];i;i=E[i].nt){
         53         int v=E[i].v;
         54         if(!son||size[v]>size[son])son=v;
         55     }
         56     if(son)dfs(son,T);
         57     for(int i=hd[u];i;i=E[i].nt){
         58         int v=E[i].v;
         59         if(son!=v)dfs(v,v);
         60     }
         61     ed[u]=idx;
         62 }
         63 il int lca(int x,int y){
         64     int tx=tp[x],ty=tp[y];
         65     while(tx!=ty){
         66         if(dep[tx]<dep[ty])y=fa[ty],ty=tp[y]; 
         67         else x=fa[tx],tx=tp[x];
         68     }
         69     return dep[x]<dep[y]?x:y;
         70 }
         71 void find(int len){
         72     int x = 0 , c;
         73     Run(i,1,len){
         74         c = s[tot+i];
         75         while(x&&!ch[x].count(c))x=fl[x];
         76         if(!ch[x].count(c))x=0;
         77         else x=ch[x][c];
         78         if(vis[x])que[++tail]=x;
         79         else if(fa[x])que[++tail]=fa[x];
         80     }
         81     tot+=len;
         82 }
         83 void dfs(int u){
         84     for(int i=hd[u];i;i=E[i].nt)
         85         dfs(E[i].v),val[u]+=val[E[i].v];
         86 }
         87 int main(){
         88     freopen("bzoj2754.in","r",stdin);
         89     freopen("bzoj2754.out","w",stdout);
         90     n=rd(); m=rd();
         91     Run(i,1,n){
         92         a[i]=rd();Run(j,1,a[i])s[++tot]=rd();
         93         b[i]=rd();Run(j,1,b[i])s[++tot]=rd();
         94     }
         95     Run(i,1,m){
         96         int x=rd(),u=0,y;
         97         Run(j,1,x){
         98             if(!ch[u][y=rd()])ch[u][y]=++sz;
         99             u=ch[u][y];
        100         }
        101         vis[pos[i]=u]++;
        102     }
        103     get_fl();
        104     dfs(0,0);
        105     tot=0;
        106     Run(i,1,n){
        107         tail=0;
        108         find(a[i]),find(b[i]);
        109         if(!tail)continue;
        110         sort(que+1,que+tail+1,cmp);
        111         head=0;
        112         Run(j,1,tail){
        113             if(!head||ed[que[j]]>ed[que[head]])head++;
        114             que[head]=que[j];
        115         }
        116         tail=head;
        117         val[0]--,val[que[1]]++;
        118         ans[i]+=deep[que[1]]; 
        119         Run(j,2,tail){
        120             int tmp = lca(que[j-1],que[j]);
        121             val[tmp]--,val[que[j]]++; 
        122             ans[i] += deep[que[j]] - deep[tmp];
        123         }
        124     }
        125     dfs(0);
        126     Run(i,1,m)printf("%d\n",val[pos[i]]);
        127     Run(i,1,n)printf("%d ",ans[i]);
        128     return 0;
        129 }
        AC
    • 3.后缀数组
      • 3.1
      • 莫队
      • 将所有串用互不相等的连接符链接,为了方便让点名串后的连接符尽量小;
      • 可以在SA里求出每次点名的区间,是后缀$i \ rank[i]$向后的一段;
      • 问题变成统计 ①一个线段里有多少种颜色的点和 ②一种颜色的点被多少条线段覆盖;
      • ①莫队模板;
      • ②因为每个区间都是不同的,考虑差分,每次从莫队的区间里加入一个颜色就加上剩余的区间数,删去就减掉,就统计了中间出现的那段区间数;
      • $O(N \ \sqrt N)$
      • 3.2
      • 树状数组
      • SA的部分一样
      • ①扫一遍,$pre[i]$表示倒着上一个扫到的和sa[i]颜色相同的位置,遇到一个每次$add(i,1)$,$add(pre[i],-1)$,直接统计对应区间;
      • ②扫一遍,对于区间$[L,R]$,在$R$的位置$add(R,1)$ ,$L-1$的位置$add(L,-1)$ ,统计$i$到$pre[i]-1$的数量;
      • 均可树状数组维护
      • $O(N \ log N)$
      • 【bzoj2754】【scoi2012】喵星球上的点名【bzoj2754】【scoi2012】喵星球上的点名
          1 #include<bits/stdc++.h>
          2 #define il inline
          3 #define rg register
          4 using namespace std;
          5 const int N=300010,M=20;
          6 int n,m,len,cnt,s[N],sub[N],tot,sa[N],ht[N],rk[N],pre[N],bl[N],pos[N],f[N][M],bin[M],l[N],mp[N],c[N],ans1[N],ans2[N];
          7 struct data{
          8     int x,y,z;
          9     bool operator <(const data&A)const{return x < A.x;};
         10 }p[N];
         11 il char gc(){
         12     static char*p1,*p2,s[1000000];
         13     if(p1==p2)p2=(p1=s)+fread(s,1,1000000,stdin);
         14     return(p1==p2)?EOF:*p1++;
         15 }
         16 il int rd(){
         17     int x=0,f=1; char ch=gc();
         18     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=gc();}
         19     while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+ch-'0',ch=gc();
         20     return x*f;
         21 }
         22 il void add(int x,int y){for(rg int i=x+1;i<=len;i+=i&-i)c[i]+=y;}
         23 il int que(int x){int re=0;for(rg int i=x+1;i;i-=i&-i)re+=c[i];return re;}
         24 void discretize(){
         25     sort(sub,sub+tot);
         26     tot=unique(sub,sub+tot)-sub;
         27     for(rg int i=0;i<len;i++)s[i]=lower_bound(sub,sub+tot,s[i])-sub;
         28 }
         29 void build_sa(){
         30     static int x[N],y[N],w[N];
         31     for(rg int i=0;i<len;i++)w[x[i]=s[i]]++;
         32     for(rg int i=1;i<tot;i++)w[i]+=w[i-1];
         33     for(rg int i=len-1;~i;i--)sa[--w[x[i]]]=i;
         34     for(rg int k=1;k<len;k<<=1){
         35         int p = 0;
         36         for(rg int i=len-k;i<len;i++)y[p++]=i;
         37         for(rg int i=0;i<len;i++)if(sa[i]>=k)y[p++]=sa[i]-k;
         38         for(rg int i=0;i<tot;i++)w[i]=0;
         39         for(rg int i=0;i<len;i++)w[x[i]]++;
         40         for(rg int i=1;i<tot;i++)w[i]+=w[i-1];
         41         for(rg int i=len-1;~i;i--)sa[--w[x[y[i]]]]=y[i];
         42         swap(x,y);
         43         x[sa[0]]=0; p=1;
         44         for(rg int i=1;i<len;i++){
         45             x[sa[i]] = y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k] ? p - 1 : p++;
         46         }
         47         if(p==len)break;
         48         tot = p + 1;
         49     }
         50 }
         51 void build_ht(){
         52     for(rg int i=0;i<len;i++)rk[sa[i]]=i;
         53     for(rg int i=0,k=0,j;i<len;i++){
         54         if(k)k--;
         55         j=sa[rk[i]-1];
         56         while(s[j+k]==s[i+k])k++;
         57         f[rk[i]][0]=ht[rk[i]]=k;
         58     }
         59 }
         60 void build_rmq(){
         61     for(rg int i=1;i<20;i++)
         62     for(rg int j=0;j<=len-bin[i];j++){
         63         f[j][i] = min(f[j][i-1],f[j+bin[i-1]][i-1]);
         64     }
         65 }
         66 int main(){
         67     freopen("bzoj2754.in","r",stdin);
         68     freopen("bzoj2754.out","w",stdout);
         69     for(int i=bin[0]=1;i<20;i++)bin[i]=bin[i-1]<<1;
         70     n=rd(); m=rd();
         71     for(rg int i=1,x;i<=n;i++){
         72         x=rd();
         73         for(rg int j=1;j<=x;j++){
         74             bl[len]=i;
         75             sub[tot++]=s[len++]=rd();
         76         }sub[tot++]=s[len]=-len,len++;
         77         x=rd();
         78         for(rg int j=1;j<=x;j++){
         79             bl[len]=i;
         80             sub[tot++]=s[len++]=rd();
         81         }sub[tot++]=s[len]=-len,len++;
         82     }
         83     for(rg int i=1,x;i<=m;i++){
         84         l[i]=x=rd();
         85         bl[len]=-i;
         86         for(rg int j=1;j<=x;j++){
         87             sub[tot++]=s[len++]=rd();
         88         }sub[tot++]=s[len]=-len,len++;
         89     }
         90     discretize();
         91     build_sa();
         92     build_ht();
         93     build_rmq();
         94     for(rg int i=len-1;~i;i--)if(bl[sa[i]]>0){
         95         int x = bl[sa[i]]; 
         96         if(!mp[x])add(mp[x]=i,1);
         97         else{
         98             pre[i]=mp[x],mp[x]=i;
         99             add(pre[i],-1),add(i,1);
        100         }
        101     }else if(bl[sa[i]]<0){
        102         int x=-bl[sa[i]],y=i+1;
        103         for(rg int j=19;~j;j--)if(f[y][j]>=l[x])y+=bin[j];
        104         p[++cnt]=(data){y-1,y-1,1};
        105         p[++cnt]=(data){i-1,y-1,-1};
        106         ans1[x] = que(y-1) - que(i-1);
        107     }
        108     memset(c,0,sizeof(c)); 
        109     sort(p+1,p+cnt+1);
        110     for(rg int i=len-1,j=cnt;~i;i--){
        111         while(j&&p[j].x==i)add(p[j].y,p[j].z),j--;
        112         if(bl[sa[i]]>0){
        113             if(!pre[i])pre[i]=len;
        114             ans2[bl[sa[i]]] += que(pre[i]-1) - que(i-1);
        115         }
        116     }
        117     for(rg int i=1;i<=m;i++)printf("%d\n",ans1[i]);
        118     for(rg int i=1;i<=n;i++)printf("%d ",ans2[i]);
        119     return 0;
        120 }
        SA+BIT
    • 4.后缀自动机
      • 4.1
      • 广义后缀自动机
      • 至少这题和$SAM$差不多,只是新加一个单词重置$last$节点;
      • 对点名串建出$SAM$之后,把姓名串在上面跑,对走过的点沿$parent$树向上跳可以找到所有子串,标记是否来过暴力统计;
      • 这样两个问的方法是一样的
      • $O(N \ \sqrt N )$ 
      • 4.2
      • 但其实如果建出$parent$树的话就和$1$一样,如果对$parent$树做$dfs$序维护的话就和$2$一样了,不说了;
      • 【bzoj2754】【scoi2012】喵星球上的点名【bzoj2754】【scoi2012】喵星球上的点名
         1 #include<bits/stdc++.h>
         2 #define rg register
         3 #define il inline 
         4 using namespace std;
         5 const int N=400010;
         6 int n,m,s[N],tot,a[N],b[N],lst,cnt,pa[N],len[N],sum[N],val[N],vis[N],ans;
         7 map<int,int>ch[N]; 
         8 il char gc(){
         9     static char*p1,*p2,s[1000000];
        10     if(p1==p2)p2=(p1=s)+fread(s,1,1000000,stdin);
        11     return(p1==p2)?EOF:*p1++;
        12 }
        13 il int rd(){
        14     int x=0,f=1; char c=gc();
        15     while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc();}
        16     while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+c-'0',c=gc();
        17     return x*f;
        18 }
        19 il void ins(int x){
        20     int p=lst,np; len[np=lst=++cnt]=len[p]+1;
        21     while(p&&!ch[p][x])ch[p][x]=np,p=pa[p];
        22     if(!p){pa[np]=1;return;}
        23     int q = ch[p][x];
        24     if(len[q]==len[p]+1)pa[np]=q;
        25     else{
        26         int nq=++cnt;
        27         len[nq]=len[p]+1;
        28         ch[nq]=ch[q];
        29         pa[nq]=pa[q]; pa[q]=pa[np]=nq;
        30         while(p&&ch[p][x]==q)ch[p][x]=nq,p=pa[p];
        31     }
        32 }
        33 il void update(int x,int y){while(x&&vis[x]!=y)sum[x]++,vis[x]=y,x=pa[x];}
        34 il void query(int x,int y){while(x&&vis[x]!=y)ans+=val[x],vis[x]=y,x=pa[x];}
        35 int main(){
        36     freopen("lg2336.in", "r", stdin);
        37     freopen("lg2336.out","w",stdout);
        38     n=rd();m=rd();
        39     cnt=1;
        40     for(rg int i=1;i<=n;i++){
        41         lst=1;a[i]=rd();
        42         for(rg int j=1;j<=a[i];j++)ins(s[++tot]=rd());
        43         lst=1;b[i]=rd();
        44         for(rg int j=1;j<=b[i];j++)ins(s[++tot]=rd());
        45     }
        46     tot=0;
        47     for(rg int i=1;i<=n;i++){
        48         for(rg int j=1,now=1;j<=a[i];j++)update(now=ch[now][s[++tot]],i);
        49         for(rg int j=1,now=1;j<=b[i];j++)update(now=ch[now][s[++tot]],i);
        50     }
        51     for(rg int i=1,l,now;i<=m;i++){
        52         l=rd(); 
        53         now=1;
        54         for(rg int j=1,x;j<=l;j++){
        55             x=rd();
        56             if(!now)continue;
        57             if(!ch[now].count(x))now=0;
        58             else now=ch[now][x];
        59         }
        60         if(now)val[now]++;
        61         printf("%d\n",sum[now]);
        62     }
        63     tot=0;
        64     for(rg int i=1;i<=n;i++){
        65         ans=0;
        66         for(rg int j=1,now=1;j<=a[i];j++)query(now=ch[now][s[++tot]],n+i);
        67         for(rg int j=1,now=1;j<=b[i];j++)query(now=ch[now][s[++tot]],n+i);
        68         printf("%d ",ans);
        69     }
        70     return 0;
        71 }
        SAM
    • 就数据来看,最快的应该是$3.1$(我没写QAQ),再来就是$2.1,4.1,3.2$,,不算$map$的话$tarjan$写lca,理论最好的应该是$2.1$ ;