题解：P15146 [SWERC 2025] LFS

highkj · 2026-04-25 09:19:58 · 题解

前言

做复杂了，属于是数据结构学傻了。

思路

首先我们能很容易求出最多的次数，因为长度为 1 的出现次数一定最大，所以我们只需要求每一个字符在这段区间中出现的次数就能得到答案，然后我们考虑如何求最长的公共前缀，其实这个也很简单，只需要我们把询问放到那个字符上然后考虑从后往前扫描线，我们只需要维护 l\to l-1 之后对于每一个 r 的最长公共前缀长度即可，这个我们可以先求出第 l,l-1 个的最长公共前缀然后我们发现对于每一个 r 就是将答案设为 \min(lst_i,val) 其中 lst_i 为 l 的时候 i 的答案然后 val 是最长公共前缀，这个用线段树不难维护，然后对于查询我们发现可能最后一段的长度没这么长所以再和最后一段能放下的长度取一个 \min 即可，时间复杂度劣爆了 O(n\log^2{n})，喜提最劣解。

代码

#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define rep(i,x,y) for(register int i=x;i<=y;i++)
#define rep1(i,x,y) for(register int i=x;i>=y;--i)
#define int long long
#define fire signed
#define il inline
template<class T> il void print(T x) {
    if(x<0) printf("-"),x=-x;
    if (x > 9) print(x / 10);
    putchar(x % 10 + '0');
}
template<class T> il void in(T &x) {
    x = 0; char ch = getchar();
    int f = 1;
    while (ch < '0' || ch > '9') {if(ch=='-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); }
    x *= f;
}
const int N=5e5+10;
int T=1;
int n,q;
string s;
const int mod=1e9+7,ba=131;
int ha[N],jc[N];
int has(int l,int r) {
    return ((ha[r]-ha[l-1]*jc[r-l+1]%mod)%mod+mod)%mod;
}
int cnt[N][30],lst[N][30];
vector<array<int,3>>vv[30];
vector<int>ve[30];
int ans[N],mp[N];
vector<array<int,2>>v1[N];
struct node{
    int l,r;
    int mn,tag;
}tr[N<<2];
int nxt[N][30];
void up(int x) {
    tr[x].mn=min(tr[x<<1].mn,tr[x<<1|1].mn);
}
void work(int x,int k) {
    tr[x].tag=k;
    tr[x].mn=k;
}
void down(int x) {
    if(tr[x].tag) {
        work(x<<1,tr[x].tag);
        work(x<<1|1,tr[x].tag);
        tr[x].tag=0;
    }
}
void build(int u,int l,int r) {
    tr[u]={l,r};
    if(l==r) {
        return;
    }
    int mid=l+r>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
}
void modify(int u,int l,int r,int k) {
    if(tr[u].l==tr[u].r) {
        tr[u].mn=k;
        tr[u].tag=k;
        return ;
    }
    down(u);
    int mid=tr[u].l+tr[u].r>>1;
    if(mid>=l) modify(u<<1,l,r,k);
    if(mid<r) modify(u<<1|1,l,r,k);
    up(u);
}
int Ans(int u,int l,int r) {
    if(tr[u].l>=l&&tr[u].r<=r) return tr[u].mn;
    int mid=tr[u].l+tr[u].r>>1;
    down(u);
    int res=1e18;
    if(mid>=l) res=Ans(u<<1,l,r);
    if(mid<r) res=min(res,Ans(u<<1|1,l,r));
    return res;
}
void solve() {
    in(n),in(q);
    cin>>s;
    s=" "+s;
    jc[0]=1;
    rep(i,1,n) jc[i]=jc[i-1]*ba%mod;
    rep(i,1,n) ha[i]=(ha[i-1]*ba%mod+s[i]-'a')%mod;
    rep(i,1,n) {
        rep(j,0,25) cnt[i][j]=cnt[i-1][j],lst[i][j]=lst[i-1][j];
        cnt[i][s[i]-'a']++;
        mp[i]=mp[lst[i][s[i]-'a']]+1;
        lst[i][s[i]-'a']=i;
        ve[s[i]-'a'].pb(i);
    }
    rep1(i,n,1) {
        rep(j,0,25) nxt[i][j]=nxt[i+1][j];
        nxt[i][s[i]-'a']=i;
    }
    rep(i,0,25) ve[i].pb(n+1);
    rep(io,1,q) {
        int l,r;
        in(l),in(r);
        vector<int>vk;
        int ct=false;
        rep(j,0,25) {
            int mx=cnt[r][j]-cnt[l-1][j];
            if(ct<mx) {
                ct=mx;
                vk.clear();
                vk.pb(j);
            }else if(ct==mx) {
                vk.pb(j);
            }
        }
        for(auto to:vk) {
            vv[to].pb({io,r,nxt[l][to]});
        }
    }
    rep(i,0,25) {
        int len=ve[i].size();
        len--;
        if(0>len) continue;
        build(1,0,len);
        for(auto to:vv[i]) {
            v1[mp[to[2]]-1].pb({to[0],to[1]});
        }
        rep1(j,len-1,0) {
            modify(1,j,j,ve[i][j+1]-ve[i][j]);
            if(j+1<=len-1) {
                int dis=false;
                int l=1,r=min(ve[i][j+1]-ve[i][j],ve[i][j+2]-ve[i][j+1]);
                int res=0;
                while(l<=r) {
                    int mid=l+r>>1;
                    if(has(ve[i][j],ve[i][j]+mid-1)==has(ve[i][j+1],ve[i][j+1]+mid-1)) l=mid+1,res=mid;
                    else r=mid-1;
                }
                l=j+1,r=len;
                int mx=0;
                while(l<=r) {
                    int mid=l+r>>1;
                    if(Ans(1,j+1,mid)>res) l=mid+1,mx=mid;
                    else r=mid-1;
                }
                if(mx>=j+1) {
                    modify(1,j+1,mx,res);
                }
            }
            for(auto to:v1[j]) {
                int mx=to[1]-lst[to[1]][i]+1;
                mx=min(mx,Ans(1,mp[lst[to[1]][i]]-1,mp[lst[to[1]][i]]-1));
                ans[to[0]]=max(ans[to[0]],mx);
            }
            v1[j].clear();
        }
    }
    rep(i,1,q) printf("%lld\n",ans[i]);
}
fire main() {
    while(T--) {
        solve();
    }
    return false;
}