P11823 [湖北省选模拟 2025] 最后的台词 / lines 题解

eastcloud · 2025-02-28 08:14:41 · 题解

先考虑 k 固定怎么做，先把答案为 1 到 2 的情况简单特判掉，答案为 1 即为两个串相同，答案为 2 就是第一个串长度为 k 的后缀和第二个串长度为 k 的前缀相同。而对于剩下的情况，我们发现除了第一个和最后一个串，其他每个串的作用相当于把我们要匹配的串换成另一个串，直到这个串被换成结尾串的前缀。

设一个串 u 的 endpos 集合为 S_u， u 为初始串的长度为 k 的后缀，v 为结尾串长度为 k 的前缀，于是问题变成初始令 p \gets \min_{d \in S_u} d ，其中，每次我们可以找到一个 q>p，令 T 为 q 所在的串，则我们要做的就是 p \gets \min_{d \in T} d，问最少多少次操作 p\le \max_{d\in S_v} d。

对于固定的 k，每个 p 对应的 q 是唯一的，可以直接连边然后倍增往上跳，而 k 不固定时可以考虑从大到小扫描 k，每次一个点的父亲要更改时对应着前缀树上两个节点合并，我们相当于把一个前缀树上节点的所有儿子的 endpos 集合的父亲对其最小值取 min，由于父亲编号是单调的，维护出连续段后可以操作就是区间覆盖。

于是问题又变成区间覆盖父亲，区间查某个点一直往上跳要跳几步才小于某个给定值，这个可以 LCT 维护，每次区间覆盖只修改连续段最左边点的父亲，其他的可以以 0 的边权连左边节点，每次 access 然后平衡树上二分即可，时间复杂度 O(n \log n)。

如果你不想写 LCT，可以考虑分块，区间覆盖小块暴力，大块打 tag，你需要对没打过 tag 的块预处理每个点第一次跳出块的位置和贡献，查询直接贪心跳即可，由于数据很水也可以通过。

提供个分块代码，写的时候没动脑子，实现比较呃呃，不太建议参考。

#include<bits/stdc++.h>

#define vi vector<int>
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pi pair<int,int>
#define ll long long
#define IL inline
#define For(i,j,k) for(int i=(j);i<=(k);i++)
#define Fol(i,j,k) for(int i=(j);i>=(k);i--)
#define fi first
#define se second

using namespace std;

#define N 2000005
#define inf 0x3f3f3f3f

int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0' || ch>'9')f=(ch=='-'?-1:f),ch=getchar();
    while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x*f;
}
void write(ll x){
    if(x<0)putchar('-'),x=-x;
    if(x/10)write(x/10);
    putchar(x%10+'0');
}

void debug(auto ...x){
    ((cerr<<x<<' '),...);
    cerr<<endl;
}

char s[N];
map<pi,int> t;
vector<array<int,3> > Q[N];
vector<pi> P[N];

namespace SAM{
    int nex[N][26],len[N],fa[N],mned[N],mxed[N],las,cnt,lasp[N];
    int f[21][N];
    basic_string<int> e[N];
    vi S[N];
    void extend(int it,int d){
        int cur=++cnt,p=las;len[cur]=len[p]+1;mxed[cur]=mned[cur]=d;las=cur;S[cur].pb(d);lasp[d]=cur;
        while(!nex[p][it])nex[p][it]=cur,p=fa[p];
        if(!p)return fa[cur]=1,void();
        int q=nex[p][it];
        if(len[q]==len[p]+1)return fa[cur]=q,void();
        int cl=++cnt;memcpy(nex[cl],nex[q],sizeof(nex[q]));len[cl]=len[p]+1;
        fa[cl]=fa[q];fa[q]=fa[cur]=cl;
        while(nex[p][it]==q)nex[p][it]=cl,p=fa[p];
    }
    void init(){
        For(i,1,cnt)if(fa[i])e[fa[i]]+=i,f[0][i]=fa[i];
        For(i,1,__lg(cnt))For(j,1,cnt)f[i][j]=f[i-1][f[i-1][j]];
        auto dfs=[&](auto &&self,int x)->void {
            if(!mxed[x])mxed[x]=0,mned[x]=0x3f3f3f3f;
            for(auto v:e[x]){
                self(self,v);mxed[x]=max(mxed[x],mxed[v]);
                mned[x]=min(mned[x],mned[v]);
            }
            P[len[x]].eb(mned[x],mxed[x]);
        };
        dfs(dfs,1);
    }
    pi jump(int x,int k){
        int now=lasp[x];
        if(len[now]>=k && len[fa[now]]<k)return mp(now,mned[now]);
        Fol(i,__lg(cnt),0)if(f[i][now] && len[f[i][now]]>=k)now=f[i][now];
        return mp(now,mned[now]);
    }
}

int f[N],ans[N];

int n;

struct Block{
    int a[N],tag[N],b[N],len[N];
    #define B 505
    void rebuild(int id){
        int l=id*B+1,r=min((id+1)*B,n);
        if(f[r]<l)return;
        For(i,l,r){
            if(a[i]<l)b[i]=a[i],len[i]=1;
            else if(a[i]==i)b[i]=i,len[i]=0;
            else b[i]=b[a[i]],len[i]=len[a[i]]+1;
        }
    }
    void upd(int l,int r){
        if(l>r)return;
        int Bl=(l-1)/B,Br=(r-1)/B;
        if(Bl==Br){
            if(tag[Bl]<l)return;
            Fol(i,r,l){
                a[i]=min(a[i],l);
                if(tag[Bl]!=inf && a[i]<l)return;
            }
            rebuild(Bl);return;
        }
        For(i,l,(Bl+1)*B)a[i]=min(a[i],l);
        For(i,Br*B+1,r)a[i]=min(a[i],l);
        if(tag[Bl]==inf)rebuild(Bl);
        if(tag[Br]==inf)rebuild(Br);
        For(i,Bl+1,Br-1)tag[i]=min(tag[i],l);
    }
    int ljump(int now,int goal){
        int res=0;
        while(now>goal){
            if(min(a[now],tag[(now-1)/B])==now)return -1;
            now=min(a[now],tag[(now-1)/B]);res++;
        }
        return res;
    }
    int bjump(int now,int goal){
        int res=0;
        while(now>goal){
            if(tag[(now-1)/B]!=inf)now=min(tag[(now-1)/B],a[now]),res++;
            else if(b[now]>=goal && b[now]!=now)res+=len[now],now=b[now];
            else{
                int ans=ljump(now,goal);
                if(ans==-1)return -1;
                return ans+res;
            }
        }
        return res;
    }
    #undef B
}Blo;

int main(){
    //freopen("lines5.in","r",stdin);
    //freopen("lines5.out","w",stdout);

    scanf("%s",s+1);n=strlen(s+1);SAM::las=SAM::cnt=1;
    int q=read();
    For(i,1,n)SAM::extend(s[i]-'a',i);SAM::init();
    For(i,1,q){
        int l1=read(),r1=read(),l2=read(),r2=read(),k=read();
        if(r1-l1==r2-l2 && SAM::jump(r1,r1-l1+1).fi==SAM::jump(r2,r1-l1+1).fi){ans[i]=1;continue;}
        Q[k].pb(array<int,3>{r1,l2+k-1,i});
    }
    For(i,0,n)f[i]=i,Blo.tag[i]=inf,Blo.a[i]=Blo.b[i]=i;
    Fol(k,n,1){
        for(auto [l,r]:P[k]){
            Blo.upd(l,r);
        }
        for(auto [now,goal,id]:Q[k]){
            pi A=SAM::jump(now,k),B=SAM::jump(goal,k);B.se=SAM::mxed[B.fi];
            if(A.fi==B.fi){ans[id]=2;continue;}
            now=A.se;goal=B.se;
            if(now<=goal){ans[id]=3;continue;}
            int res=Blo.bjump(now,goal);
            if(res==-1)ans[id]=-1;
            else ans[id]=res+3;
        }
    }
    For(i,1,q)write(ans[i]),putchar('\n');
    return 0;
}