题解：P12490 [集训队互测 2024] 字符串

鲤鱼江 · 2025-10-24 10:50:25 · 题解

典题，从 Runs 模板拷过来的代码上加点东西就行了。

设 rk_i 表示以 i 开头的后缀在所有后缀中的排名，就是 SA 里面的定义。

一个 l 合法的充要条件是 rk_i<rk_{i+l}\wedge s[i:i+l-1]\neq s[i+l:i+2l-1]。

考虑求出满足 l\le r\wedge rk_i<rk_{i+l} 的 l 的个数 s。

如果再求出满足 l\le r\wedge rk_i<rk_{i+l}\wedge s[i:i+l-1]= s[i+l:i+2l-1] 的 l 的个数 c。

那么最终答案就是 s-c。

按照字典序从大到小加入后缀可以简单地求出 s，使用树状数组单点加区间求和即可。

思考 c 怎么求，s[i:i+l-1]= s[i+l:i+2l-1] 这个条件很难不想到平方串，从平方串的角度入手。

设 (l,r,p) 表示 \forall i\in[l,r-p],S_i=S_{i+p}。

如果没有 rk_i<rk_{i+p} 的限制条件是非常容易的，离线扫描线，直接将区间 [l,r-2p+1] 加一，然后把 r=p 的查询给全部搞了。

思考 rk_i<rk_{i+p} 怎么处理，不难发现我们直接比较 S_{r+1} 和 S_{r-p+1} 的字典序大小就知道是否贡献了，显然 S_{r+1}\neq S_{r-p+1}。

时间复杂度 O(n\log^2 n) 吧，挺小常数的还。

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

namespace Fread {
    const int SIZE=1<<21;char buf[SIZE],*S,*T;
    inline char getchar() {if(S==T){T=(S=buf)+fread(buf,1,SIZE,stdin);if(S==T)return '\n';}return *S++;}
}
namespace Fwrite {
    const int SIZE=1<<21;
    char buf[SIZE],*S=buf,*T=buf+SIZE;
    inline void flush(){fwrite(buf,1,S-buf,stdout);S=buf;}
    inline void putchar(char c){*S++=c;if(S==T)flush();}
    struct POPOSSIBLE{~POPOSSIBLE(){flush();}}ztr;
}
#define getchar Fread :: getchar
#define putchar Fwrite :: putchar
namespace Fastio{
    struct Reader{
        template<typename T>
        Reader& operator >> (T& x) {
            char c=getchar();T f=1;
            while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}x=0;
            while(c>='0'&&c<='9'){x=x*10+(c-'0');c=getchar();}x*=f;
            return *this;
        }
        Reader& operator >>(string &s){
            char c=getchar();s.clear();
            while(c==' '||c=='\n')c=getchar();
            while(c!=' '&&c!='\n'&&c!='\r'){s+=c;c=getchar();}
            return *this;
        }
        Reader(){}
    }cin;
    struct Writer{
        template<typename T>
        Writer& operator << (T x) {
            if(x==0){putchar('0');return *this;}
            if(x<0){putchar('-');x=-x;}
            static int sta[45];int top=0;
            while(x){sta[++top]=x%10;x/=10;}
            while(top){putchar(sta[top]+'0');--top;}
            return *this;
        }
        Writer& operator << (char c) {putchar(c);return *this;}
        Writer(){}
    }cout;
}
#define fi first 
#define sec second
typedef pair<int,int> pii;
#define cin Fastio :: cin
#define cout Fastio :: cout

bool st;
const int N=1e6+10;
string s;int n,m,tot,flag[N];
int x[N],y[N],c[N],cas,ans[N];

struct SA{
    int sa[N],rk[N],h[N],f[20][N];
    inline void Suffix_Sort(){
        int m=130;
        for(int i=1;i<=n;++i) ++c[x[i]=s[i]];
        for(int i=1;i<=m;++i) c[i]+=c[i-1];
        for(int i=n;i;--i) sa[c[x[i]]--]=i;
        for(int i=0;i<=m;++i) c[i]=0;
        for(int k=1;k<=n;k<<=1){
            int ct=0;
            for(int i=n-k+1;i<=n;++i) y[++ct]=i;
            for(int i=1;i<=n;++i) if(sa[i]>k) y[++ct]=sa[i]-k;
            for(int i=1;i<=n;++i) ++c[x[i]];
            for(int i=1;i<=m;++i) c[i]+=c[i-1];
            for(int i=n;i;--i) sa[c[x[y[i]]]--]=y[i],y[i]=0;
            for(int i=0;i<=m;++i) c[i]=0;
            swap(x,y);x[sa[1]]=ct=1;
            for(int i=2;i<=n;++i) x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?ct:++ct;
            if(ct==n) break;
            m=ct;
        }
        for(int i=1;i<=n;++i) rk[sa[i]]=i;
    }
    inline void getheight(){
        int k=0;
        for(int i=1;i<=n;++i){
            if(k) --k;
            if(rk[i]==1) continue;
            int j=sa[rk[i]-1];
            while(j+k<=n&&s[i+k]==s[j+k]) ++k;
            h[rk[i]]=k;
        }
    }
    inline void init(){
        for(int i=1;i<=n;++i) f[0][i]=h[i];
        for(int i=1;i<=__lg(n);++i) for(int j=1;j+(1<<i)-1<=n;++j) f[i][j]=min(f[i-1][j],f[i-1][j+(1<<(i-1))]);
    }
    inline int ask(int i,int j){
        i=rk[i];j=rk[j];if(i>j) swap(i,j);
        ++i;int g=__lg(j-i+1);
        return min(f[g][i],f[g][j-(1<<g)+1]);
    }
}lcp,lcs;
bool ed;
struct TreeArray{
    int tr[N];inline int lowbit(int x){return x&(-x);}
    inline void add(int i,int x){for(;i<=n;i+=lowbit(i)) tr[i]+=x;}
    inline int ask(int i){int res=0;for(;i;i-=lowbit(i)) res+=tr[i];return res;}
}tmp,t;

inline int LCP(int x,int y){return lcp.ask(x,y);}
inline int LCS(int x,int y){return lcs.ask(n-y+1,n-x+1);}
int sa[N],id[N];
vector < pii > v[N],g[N];

int main(){
    cin>>cas>>n>>m>>s;s=' '+s;
    lcp.Suffix_Sort();lcp.getheight();lcp.init();reverse(s.begin()+1,s.end());
    lcs.Suffix_Sort();lcs.getheight();lcs.init();reverse(s.begin()+1,s.end());
    for(int i=1,p,r;i<=m;++i){
        cin>>p>>r;
        v[p].emplace_back(r,i);
        g[r].emplace_back(p,i);
    }
    for(int i=1;i<=n;++i) sa[i]=lcp.sa[i];
    for(int i=n;i;--i){
        for(auto x:v[sa[i]]) ans[x.sec]+=tmp.ask(sa[i]+x.fi)-tmp.ask(sa[i]);
        tmp.add(sa[i],1);
    }
    for(int k=1;k<=n;++k){
        for(int i=k;i+k<=n;i+=k){
            int j=i+k;
            int L=i-LCS(i,j)+1;
            int R=j+LCP(i,j)-1;
            if((R-j+1)+(i-L+1)<k) continue;
            if(flag[L]==k||R-L+1<2*k) continue;
            if(R==n||s[R-k+1]>s[R+1]) continue;
            t.add(L,1);t.add(R-2*k+2,-1);
            flag[L]=k;
        }
        for(auto x:g[k]) ans[x.sec]-=t.ask(x.fi);
    }
    for(int i=1;i<=m;++i) cout<<ans[i]<<'\n';
    return 0;
}