CF1043G Speckled Band 题解

· · 题解

题目分析

我们阅读题目后能够很容易的得出答案有解时最大为 4。因为答案种类数较少时我们可以考虑直接分类讨论。

  1. 答案为 -1

那么区间内的字母都只出现一次，所以我们开个字母出现次数的前缀和判断即可。

时间复杂度 O(\Sigma)。

  1. 答案为 1

因为只能出现一种子串，例如 \textrm{AAA}。所以我们判断一下这个区间是否有循环节即可，根据循环节的定义我们只需判断区间长度的因子是否为循环节即可。可以使用 Hash，也可以用 SA。

查询时间复杂度为因子个数，SA 预处理时间复杂度 O(n\log{n})，暴力预处理因子时间复杂度 O(n \sqrt{n})。

  1. 答案为 2

答案为 2 只有三种情况 \textrm{AAB}，\textrm{BAA}，\textrm{ABA}。前两种我们只需像优秀的拆分一样统计一下 pre[i] 和 suf[i] 分别表示以 i 开头的最短 \textrm{AA} 长度，以 i 结尾的最短 \textrm{AA} 长度。然后枚举关键点统计即可，随便用什么数据结构维护一下就行。

查询时间复杂度 O(1)，根据调和级数得出预处理时间复杂度 O(n\ln{n})。

再考虑第三种情况，其实就是判断子串是否有 border。最长 border 比较难求，但是最短 border 就比较简单了。

引理：若串 S 的最小 border 长度超过 \sqrt{|S|} 则该 border 在串中的出现次数不超过 \sqrt{|S|} 次。

所以我们可以考虑平衡规划，对于判断长度小于 \sqrt{|S|} 的 border，我们直接枚举长度用 SA 或 Hash 判断即可。对于判断长度大于 \sqrt{|S|} 的 border 我们可以枚举在后缀排名中与 rnk[l] 相邻的 \sqrt{|S|} 个后缀判断 border。

我们还要注意一个点，若有一个长度大于 \frac{|S|}{2} 的 border，那么相交处还会存在一个更小的 border。所以我们求出的 border 长度小于 \frac{|S|}{2} 的 border 才是合法的。

查询时间复杂度 O(\sqrt{n})。

  1. 答案为 3

答案为 3 也只有三种情况 \textrm{ABAC}，\textrm{BACA}，\textrm{BAAC}。

前两种只需判断 s[l] 和 s[r] 在 s[l+1\sim r-1] 中是否出现过即可。用前面需处理的前缀和判断。

第三种情况，我们可以用前面已知的 pre 帮助判断，我们就是判断是否存在一个 i 满足 \forall i \in \{l+1,\cdots,r-1\} 且 i+pre[i]<r。这个式子可以贪心，i+pre[i] 越小越优秀，我们预处理 ST 表即可查询。

查询时间复杂度 O(1)，预处理时间复杂度 O(n\log{n})。

  1. 答案为 4

以上都不是直接输出 4 即可。

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2e5+10;
const int inf=LONG_LONG_MAX;
int n,q,m,p,flg;
char s[maxn];
int cnt[maxn][200];
vector<int>g[maxn];
struct SA{
    int s[maxn];
    int m,p;
    int x[maxn],y[maxn],last[maxn],dbf[maxn],t[maxn];
    int sa[maxn],rnk[maxn],height[maxn],st[maxn][30];
    int cmp(int x,int y,int k){
        return last[x]==last[y]&&last[x+k]==last[y+k];
    }
    void init(){
        m=200;
        p=0;
        memset(t,0,sizeof(t));
        memset(height,0,sizeof(height)); 
        memset(x,0,sizeof(x));
        for(int i=1;i<=n;i++)t[x[i]=s[i]]++;
        for(int i=1;i<=m;i++)t[i]+=t[i-1];
        for(int i=n;i>=1;i--)dbf[t[x[i]]--]=i;
        for(int k=1;k<=n;k<<=1,m=p){
            p=0;
            for(int i=n-k+1;i<=n;i++)y[++p]=i;
            for(int i=1;i<=n;i++){
                if(dbf[i]>k)y[++p]=dbf[i]-k;
            }
            memset(t,0,sizeof(t));
            for(int i=1;i<=n;i++)t[x[y[i]]]++;
            for(int i=1;i<=m;i++)t[i]+=t[i-1];
            for(int i=n;i>=1;i--)dbf[t[x[y[i]]]--]=y[i];
            memcpy(last,x,sizeof(x));
            p=0;
            for(int i=1;i<=n;i++){
                x[dbf[i]]=cmp(dbf[i],dbf[i-1],k)?p:++p;
            }
            if(p==n)break;
        }
        for(int i=1;i<=n;i++){
            sa[i]=dbf[i];
            rnk[i]=x[i];
        }
        p=0;
        for(int i=1;i<=n;i++){
            if(p)p--;
            int j=sa[rnk[i]-1];
            while(i+p<=n&&j+p<=n&&s[i+p]==s[j+p])p++;
            height[rnk[i]]=p;
            st[rnk[i]][0]=height[rnk[i]];
        }
        for(int j=1;j<=25;j++){
            for(int i=1;i+(1<<j)-1<=n;i++){
                st[i][j]=min(st[i][j-1],st[i+(1<<j-1)][j-1]);
            }
        }
    }
    int get(int l,int r){
        l=rnk[l],r=rnk[r];
        if(l>r)swap(l,r);
        if(l==r)return n-sa[l]+1;
        l++;
        int k=__lg(r-l+1);
        return min(st[l][k],st[r-(1<<k)+1][k]); 
    }
}A,B;
struct DSU{
    int fa[maxn],val[maxn];
    void init(){
        for(int i=1;i<=n+1;i++){
            fa[i]=i;
            val[i]=0x3f3f3f3f;
        }
    }
    int find(int x){
        if(x==fa[x])return x;
        return fa[x]=find(fa[x]);
    }
    void update(int l,int r,int k){
        if(l>r)return ;
        int p=find(l);
        while(p<=r){
            val[p]=k;
            fa[p]=p+1;
            p=find(p);
        }
    }
}pre,suf;
int st[maxn][25];
void init(){
    for(int i=1;i<=n;i++){
        A.s[i]=s[i];
        B.s[i]=s[n-i+1];
    }
    A.init();
    B.init();
    pre.init();
    suf.init();
    for(int i=1;i<=n;i++){
        cnt[i][s[i]]++;
    }
    for(int i=1;i<=n;i++){
        for(int j='a';j<='z';j++){
            cnt[i][j]+=cnt[i-1][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j*j<=i;j++){
            if(i%j==0){
                if(j!=i)g[i].push_back(j);
                if(i/j!=i&&i/j!=j)g[i].push_back(i/j);
            }
        }
    }
    for(int len=1;len*2<=n;len++){
        for(int i=len,j=len*2;j<=n;i+=len,j+=len){
            int lcp=A.get(i,j);
            int lcs=B.get(n-i+1,n-j+1);
            int l=i-lcs+1,r=j+lcp-1;
            pre.update(l,r-2*len+1,2*len);
            suf.update(l+2*len-1,r,2*len);
        }
    }
    for(int i=1;i<=n;i++)st[i][0]=i+pre.val[i]-1;
    for(int j=1;j<=20;j++){
        for(int i=1;i+(1<<j)-1<=n;i++){
            st[i][j]=min(st[i][j-1],st[i+(1<<j-1)][j-1]);
        }
    }
}
int solve1(int l,int r){
    flg=1;
    for(int i='a';i<='z';i++){
        if(cnt[r][i]-cnt[l-1][i]>1)flg=0;
    }
    return flg;
}
int solve2(int l,int r){
    flg=0;
    for(int i=0;i<g[r-l+1].size();i++){
        if(A.get(l,l+g[r-l+1][i])>=r-l+1-g[r-l+1][i]){
            flg=1;
            break;
        }
    }
    return flg;
}
int solve3(int l,int r){
    if(pre.val[l]<=r-l+1||suf.val[r]<=r-l+1){
        return 1;
    }
    int sq=sqrt(n);
    for(int i=1;i<=sq&&i<r-l+1;i++){
        if(A.get(l,r-i+1)>=i&&2*i<=r-l+1)return 1;
    }
    int res=0x3f3f3f3f;
    for(int i=max(1ll,A.rnk[l]-sq+1);i<=min(n,A.rnk[l]+sq-1);i++){
        int p=A.sa[i];
        if(p>l&&p<=r&&A.get(l,p)>=r-p+1)res=min(res,r-p+1);
    }
    if(res*2<=r-l+1)return 1;
    return 0;
}
int get(int l,int r){
    if(l>r)return 0x3f3f3f3f;
    int k=__lg(r-l+1);
    return min(st[l][k],st[r-(1<<k)+1][k]);
}
int solve4(int l,int r){
    if((cnt[r-1][s[l]]-cnt[l][s[l]])||(cnt[r-1][s[r]]-cnt[l][s[r]]))return 1;
    if(get(l+1,r-1)<r)return 1;
    return 0;
}
signed main(){
    scanf("%lld",&n);
    scanf("%s",s+1);
    init();
    scanf("%lld",&q);
    while(q--){
        int l,r;
        scanf("%lld%lld",&l,&r);
        if(solve1(l,r))puts("-1");
        else if(solve2(l,r))puts("1");
        else if(solve3(l,r))puts("2");
        else if(solve4(l,r))puts("3");
        else puts("4");
    }

    return 0;
}