loj6031「雅礼集训 2017 Day1」字符串

ゞ浴缸里的玫瑰 2023-10-11 11:20 35阅读 0赞

[题目][Link 1]

首先先对\\(s\\)建一个\\(\\operatorname\{SAM\}\\)，设\\(w=kq\\)

发现\\(k,q\\leq 10^5\\)，但是\\(w\\leq 10^5\\)，于是套路地根号讨论一下

如果\\(k\\leq \\sqrt\{w\}\\)，那么说明单个询问串都很短，我们完全可以暴力长度为\\(k\\)的字符串的所有子串，之后二分查询一下这个子串在\\(\[a,b\]\\)的询问里出现的次数，这个子串在\\(s\\)出现的次数直接边走边查就好了，这边的复杂度是\\(O(qk^2\\log m)=O(w\\sqrt\{w\}\\log m)\\)

如果\\(k>\\sqrt\{w\}\\)，那么说明单个询问串很长，但是询问个数\\(q\\leq \\sqrt\{w\}\\)，于是我们直接扫\\(\[a,b\]\\)范围内的所有区间，考虑到子串\\(\[l,r\]\\)在\\(s\\)中出现了多少次可以转化为\\(s\\)有多少个前缀和前缀\\(r\\)的\\(\\operatorname\{LCS\}\\)长度不小于\\(r-l+1\\)，于是直接树上倍增求解，复杂度\\(O(qm\\log n)=O(m\\sqrt\{w\}\\log n)\\)

代码

#include<bits/stdc++.h>
    #define re register
    #define LL long long
    inline int read() {
        char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();
        while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
    }
    const int maxn=2e5+5;
    int fa[maxn],A[maxn],tax[maxn],son[maxn][26],len[maxn],sz[maxn];
    int n,m,k,q,lst,cnt;
    char S[maxn>>1];
    inline void ins(int c) {
        int p=++cnt,f=lst;lst=p;
        len[p]=len[f]+1,sz[p]=1;
        while(f&&!son[f][c]) son[f][c]=p,f=fa[f];
        if(!f) {fa[p]=1;return;}
        int x=son[f][c];
        if(len[f]+1==len[x]) {fa[p]=x;return;}
        int y=++cnt;
        len[y]=len[f]+1,fa[y]=fa[x],fa[p]=fa[x]=y;
        for(re int i=0;i<26;i++) son[y][i]=son[x][i];
        while(f&&son[f][c]==x) son[f][c]=y,f=fa[f];
    }
    namespace sub1 {
        int id[350][350],tot;
        std::vector<int> v[maxn>>1];
        inline int find(int t,int x) {
            int l=0,r=v[t].size()-1,h=-1;
            while(l<=r) {
                int mid=l+r>>1;
                if(v[t][mid]<=x) h=mid,l=mid+1;
                    else r=mid-1;
            }
            return h+1;
        }
        void solve() {
            for(re int i=1;i<=k;++i)
                for(re int j=i;j<=k;++j) id[i][j]=++tot; 
            for(re int x,y,i=1;i<=m;i++) {
                x=read()+1,y=read()+1;
                v[id[x][y]].push_back(i);
            }
            for(re int x,y,i=1;i<=q;i++) {
                scanf("%s",S+1);x=read(),y=read()+1;
                LL ans=0;
                for(re int now=1,j=1;j<=k;++j,now=1) 
                    for(re int p=j;p<=k;++p) {
                        now=son[now][S[p]-'a'];
                        if(!now) break;
                        ans+=1ll*sz[now]*(find(id[j][p],y)-find(id[j][p],x));
                    }
                printf("%lld\n",ans);
            }
        }
    }
    namespace sub2 {
        int ql[maxn>>1],qr[maxn>>1],deep[maxn];
        int lg[maxn>>1],pos[maxn>>1],ml[maxn>>1],f[18][maxn];
        void solve() {
            for(re int i=1;i<=m;i++) ql[i]=read()+1,qr[i]=read()+1;
            deep[1]=1;for(re int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
            for(re int i=2;i<=cnt;i++) deep[A[i]]=deep[fa[A[i]]]+1;
            for(re int i=1;i<=cnt;i++) {
                int x=A[i];f[0][x]=fa[x];
                for(re int j=1;j<=lg[deep[x]];++j)
                    f[j][x]=f[j-1][f[j-1][x]];
            }
            int x,y;
            while(q--) {
                scanf("%s",S+1);x=read()+1,y=read()+1;
                int now=1,l=0;LL ans=0;
                for(re int i=1;i<=k;i++) {
                    if(son[now][S[i]-'a']) {
                        pos[i]=now=son[now][S[i]-'a'];
                        ml[i]=++l;continue;
                    }
                    while(now&&!son[now][S[i]-'a']) now=fa[now];
                    if(!now) pos[i]=now=1,ml[i]=l=0; 
                    else ml[i]=l=len[now]+1,pos[i]=now=son[now][S[i]-'a'];
                }
                for(re int i=x;i<=y;++i) {
                    if(ml[qr[i]]<qr[i]-ql[i]+1) continue;
                    now=pos[qr[i]];
                    for(re int j=lg[deep[now]];j>=0;--j)
                        if(len[f[j][now]]>=qr[i]-ql[i]+1) now=f[j][now];
                    ans+=sz[now];
                }
                printf("%lld\n",ans);
            }
        }
    }
    int main() {
        n=read(),m=read(),q=read(),k=read();
        scanf("%s",S+1);lst=cnt=1;
        for(re int i=1;i<=n;i++) ins(S[i]-'a');
        for(re int i=1;i<=cnt;i++) tax[len[i]]++;
        for(re int i=1;i<=n;i++) tax[i]+=tax[i-1];
        for(re int i=1;i<=cnt;i++) A[tax[len[i]]--]=i;
        for(re int i=cnt;i;--i) sz[fa[A[i]]]+=sz[A[i]];
        if(k<=std::sqrt(k*q)) sub1::solve();else sub2::solve();
        return 0;
    }

转载于:https://www.cnblogs.com/asuldb/p/11369349.html

[Link 1]: https://loj.ac/problem/6031/