menu zcmimi's blog
LG 2336 [SCOI2012]喵星球上的点名
查看原题

点击跳转

有多种做法

AC自动机暴力

AC自动机+树状数组+lca+dfs序

后缀数组+ST表+树状数组

AC自动机暴力

原数据可以过,后来添加了加强数据就tle了

对点名串建立AC自动机,枚举名字在上面匹配,跳fail树统计

记得用于标记是否访问的数组不能用memset清零,要按原来的修改回去

玄学复杂度

#include<bits/stdc++.h>
#include<bits/extc++.h>
namespace IO{const int str=1<<20;static char in_buf[str],*in_s,*in_t;bool __=0;char gc(){return (in_s==in_t)&&(in_t=(in_s=in_buf)+fread(in_buf,1,str,stdin)),in_s==in_t?EOF:*in_s++;}void in(char &ch){if(__)return;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF)__=1;else ch=c;}void in(char *ch){*ch='\0';if(__)return;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF){__=1;return;}*ch=c;ch++;while((c=gc())!=EOF&&!isspace(c))*ch=c,ch++;if(c==EOF)__=1;*ch='\0';}template<typename T>void in(T &x){if(__)return;char c=gc();bool f=0;while(c!=EOF&&(c<'0'||c>'9'))f^=(c=='-'),c=gc();if(c==EOF){__=1;return;}x=0;while(c!=EOF&&'0'<=c&&c<='9')x=x*10+c-48,c=gc();if(c==EOF)__=1;if(f)x=-x;}template<typename T,typename ... arr>void in(T &x,arr & ... y){in(x),in(y...);}const char ln='\n';static char out_buf[str],*out_s=out_buf,*out_t=out_buf+str;void flush(){fwrite(out_buf,1,out_s-out_buf,stdout);out_s=out_buf;}void pt(char c){(out_s==out_t)?(fwrite(out_s=out_buf,1,str,stdout),*out_s++=c):(*out_s++=c);}void out(const char* s){while(*s)pt(*s++);}void out(char* s){while(*s)pt(*s++);}void out(char c){pt(c);}template<typename T>void out(T x){if(!x){pt('0');return;}if(x<0)pt('-'),x=-x;char a[50],t=0;while(x)a[t++]=x%10,x/= 10;while(t--)pt(a[t]+'0');}template<typename T,typename ... arr>void out(T x,arr & ... y){out(x),out(y...);}}using namespace IO;
#define fur(i,x,y) for(int i=x;i<=y;++i)
const int N=100001;
using std::list,__gnu_pbds::gp_hash_table;
int fail[N],sz,q[N],ans[N],ANS[N],vi[N],VI[N],vp,VP;
list<int>s1[50001],s2[50001],ed[N];
gp_hash_table<int,int>c[N];
bool vis[N],VIS[N];
int main(){
    int n,m,tot,now,v;
    in(n,m);
    fur(i,1,n){
        in(tot);while(tot--)in(v),s1[i].push_back(v);
        in(tot);while(tot--)in(v),s2[i].push_back(v);
    }
    fur(i,1,m){
        now=0,in(tot);
        while(tot--){
            in(v);
            if(!c[now][v])c[now][v]=++sz;
            now=c[now][v];
        }
        ed[now].push_back(i);
    }
    int h=0,t=0;
    for(auto to:c[0])
        fail[to.second]=0,q[t++]=to.second;
    while(h<t){
        int now=q[h++];
        for(auto to:c[now]){
            int k=fail[now];
            while(k&&!c[k][to.first])k=fail[k];
            fail[to.second]=c[k][to.first],q[t++]=to.second;
        }
    }
    fur(i,1,n){
        now=0;
        for(auto x:s1[i]){
            while(now&&!c[now][x])now=fail[now];
            now=c[now][x];
            for(t=now;t;t=fail[t])if(!vis[t]){
                vis[t]=1,vi[++vp]=t;
                for(int to:ed[t])if(!VIS[to])
                    VIS[to]=1,VI[++VP]=to,
                    ++ans[to],++ANS[i];
            }
        }
        now=0;
        for(auto x:s2[i]){
            while(now&&!c[now][x])now=fail[now];
            now=c[now][x];
            for(t=now;t;t=fail[t])if(!vis[t]){
                vis[t]=1,vi[++vp]=t;
                for(int to:ed[t])if(!VIS[to])
                    VIS[to]=1,VI[++VP]=to,
                    ++ans[to],++ANS[i];
            }
        }
        while(vp)vis[vi[vp--]]=0;
        while(VP)VIS[VI[VP--]]=0;
    }
    fur(i,1,m)out(ans[i]),pt('\n');
    fur(i,1,n)out(ANS[i]),pt(' ');
    flush();
}

后缀树组正解

后缀数组+rmq+二分+后缀数组

我们将所有姓名串和点名串拼在一起,中间用原串中不会出现的数隔开,对每个点记录它是哪个串的。

求出sa,rnk,height数组,建立height数组的rmq

接着转化问题

第一问:

设当前询问的字符串在串起来的字符串中起始位置为i,排名为rnk_i,长度为len_i

求在所有后缀中,与当前询问的字符串后缀\operatorname{LCP}等于当前字符串长度的,属于多少个名字

可以通过二分求出范围,然后判断

问题也就转化成: 求给定范围内颜色数目, (HH的项链)

第二问也就转化成: 求每个颜色被多少个询问区间覆盖

访问到L处给树状数组bit[L]++,到R时bit[L]--,到i时查询sum(i)-sum(pre[i])

#include<bits/stdc++.h>
#define gc getchar()
#define fur(i,x,y) for(int i=x;i<=y;++i)
int rd(){int x=0;char c;bool f=0;for(c=gc;c<'0'||'9'<c;c=gc)f^=c=='-';for(x=c-48,c=gc;'0'<=c&&c<='9';x=x*10+c-48,c=gc);return f?-x:x;}
const int N=300011;
int nn,q,n,m,col[N],s[N],sa[N],rnk[N],height[N],len[N],tax[N],tp[N];
void qsort(){
    fur(i,0,m)tax[i]=0;
    fur(i,1,n)++tax[rnk[i]];
    fur(i,1,m)tax[i]+=tax[i-1];
    for(int i=n;i;--i)sa[tax[rnk[tp[i]]]--]=tp[i];
}
void suffix(){
    m=11111;
    fur(i,1,n)tp[i]=i,rnk[i]=s[i];
    qsort();
    for(int w=1,p=0;p<n;m=p,w<<=1){
        p=0;
        fur(i,1,w)tp[++p]=n-w+i;
        fur(i,1,n)if(sa[i]>w)tp[++p]=sa[i]-w;
        qsort();
        std::swap(tp,rnk);
        rnk[sa[1]]=p=1;
        fur(i,2,n)rnk[sa[i]]=p+=tp[sa[i]]^tp[sa[i-1]]||tp[sa[i]+w]^tp[sa[i-1]+w];
    }
}
void gh(){
    int k=0,j;fur(i,1,n){
        if(k)--k;
        j=sa[rnk[i]-1];
        while(s[i+k]==s[j+k]&&i+k<=n&&j+k<=n)++k;
        height[rnk[i]]=k;
    }
}
int f[19][N];
int min(int x,int y){return x<y?x:y;}
void st(){
    fur(i,1,n)f[0][i]=height[i];
    fur(i,1,18)
        fur(j,1,n-(1<<i)+1)
            f[i][j]=min(f[i-1][j],f[i-1][j+(1<<i-1)]);
}
int ask(int l,int r){
    if(l==r)return -1u>>1;
    if(l>r)l^=r,r^=l,l^=r;
    ++l;
    int k=log2(r-l+1);
    return min(f[k][l],f[k][r-(1<<k)+1]);
}
int t1[N],t2[N];
void upd(int*tr,int x,int v){if(x)for(;x<=n;x+=x&-x)tr[x]+=v;}
int qry(int*tr,int x){int res=0;for(;x;x-=x&-x)res+=tr[x];return res;}
int qry(int*tr,int x,int y){return qry(tr,y)-qry(tr,x-1);}
int pre[N],b[N],que[N],lp[N];
struct node{
    int id,l,r;
    bool operator<(node t){return r<t.r;}
}p[N];
int a1[N],a2[N];
int main(){
    nn=rd(),q=rd();
    fur(i,1,nn){
        for(int x=rd();x--;)col[++n]=i,s[n]=rd();s[++n]=10001;
        for(int x=rd();x--;)col[++n]=i,s[n]=rd();s[++n]=10001;
    }
    fur(i,1,q){
        len[n+1]=rd(),que[n+1]=i;
        for(int j=len[n+1];j--;)col[++n]=-i,s[n]=rd();s[++n]=10001;
    }
    suffix(),gh(),st();
    fur(i,1,n){
        if(col[sa[i]]>0){// 求出pre数组
            pre[i]=b[col[sa[i]]];
            b[col[sa[i]]]=i;
        }
        if(que[i]){// 二分出询问范围
            p[que[i]].id=que[i];
            int l=1,r=rnk[i];
            while(l<r){
                int mid=l+r>>1;
                if(ask(mid,rnk[i])>=len[i])r=mid;
                else l=mid+1;
            }
            lp[que[i]]=p[que[i]].l=l;
            l=rnk[i],r=n;
            while(l<r){
                int mid=l+r+1>>1;
                if(ask(mid,rnk[i])>=len[i])l=mid;
                else r=mid-1;
            }
            p[que[i]].r=r;
        }
    }
    std::sort(p+1,p+q+1);
    std::sort(lp+1,lp+q+1);
    for(int i=1,j=1,k=1;i<=n;++i){
        int t=0;for(;j<=q&&lp[j]==i;++j)++t;
        upd(t2,i,t);
        if(col[sa[i]]>0)
            a2[col[sa[i]]]+=qry(t2,pre[i]+1,i),
            upd(t1,i,1),upd(t1,pre[i],-1);
        for(;k<=q&&p[k].r==i;++k){
            a1[p[k].id]=qry(t1,p[k].l,p[k].r);
            upd(t2,p[k].l,-1);
        }
    }
    fur(i,1,q)printf("%d\n",a1[i]);
    fur(i,1,nn)printf("%d ",a2[i]);
}
LG 2336 [SCOI2012]喵星球上的点名

评论加载中...

Search
search