字符串 NOI2023

WZH2026-09-192026-09-19

[NOI2023] 字符串

题目链接： [NOI2023] 字符串。

题目描述：

小 Y 了解到关于字符串的如下定义:

给定一个长度为 $n$ 的字符串 $s[1: n]$ ，我们定义其子串 $s[l: r]$ （ $1 \leq l \leq r \leq n$ ）为选择 $s[l], s[l+1], \dots, s[r]$ , 将其顺次拼接得到的新字符串。

给定一个长度为 $n$ 的字符串 $s[1: n]$ ，我们定义其翻转后的结果 $R(s)$ 为将 $s[n], s[n-1], \dots, s[1]$ 顺次拼接，也就是将字符串反序拼接得到的字符串。

给定两个长度均为 $n$ 的字符串 $a[1: n], b[1: n]$ ，我们定义 $a$ 的字典序小于 $b$ 当且仅当存在 $1 \leq i \leq n$ ，使得对于任意 $1 \leq j < i$ ， $a[j] = b[j]$ ，且 $a[i] < b[i]$ 。

在了解了上述定义后，小 Y 想到了这样的问题:

给定一个长度为 $n$ 的字符串 $s[1: n]$ 。有 $q$ 次询问，每次询问给定两个参数 $i, r$ 。你需要求出有多少 $l$ ，满足如下条件:

$1 \leq l \leq r$ 。

$s[i: i+l-1]$ 字典序小于 $R(s[i+l: i+2l-1])$ 。

小 Y 想求助你帮忙解决这一问题。

$n,q\le 10^5$ 。

暴力可以做到 $O(qn^2)$ ，使用 SA 或哈希优化后可以做到 $O(qn)$ 或 $O(qn\log n)$ ，能拿到 $36\%$ 的分数。

此时我们发现我们没有什么好办法可以直接刻画限制，于是考虑：

加紧限制，然后统计漏掉的。
放松限制，然后扣掉不合法的。

在这里定义 $S_i$ 表示从 $i$ 开始的后缀， $P_i$ 表示从 $i$ 开始的前缀。

不妨把 $s[i:i+l-1]<R(s[i+l:i+2l-1])$ 改为 $S_i<P_{i+2l-1}$ ，这样做容易发现是放松了限制，于是我们要减去不合法的。

Part I. 放松的限制

考虑将 $s$ 和 $s^R$ 拼接，这样就可以把 $P$ 转化为一个后缀。这里为了好处理细节，将 $s+c+s^R+d$ 进行拼接，其中 $c,d$ 为两个不同的字符。

然后构建 SA ，此时限制直接变为：

$rk_i<rk_j$ 。
$j\bmod 2\ne i\bmod 2$ 。
$i+1\le j\le i+2r-1$ 。

这是一个经典的二维数点问题，用奇数偶数两个 BIT 维护即可。

namespace SA{
    int sa[N],rk[N],t[N],cnt[N];
    void init(){
        memset(t,0,sizeof(t));
        memset(rk,0,sizeof(rk));
        memset(sa,0,sizeof(sa));
    }
    void sortsa(int n,int m,int w){
        for(int i=0;i<=m;i++)cnt[i]=0;
        for(int i=1;i<=n;i++)cnt[rk[t[i]]]++;
        for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
        for(int i=n;i;i--)sa[cnt[rk[t[i]]]--]=t[i];
        for(int i=1;i<=n;i++)t[i]=rk[i];
        for(int i=1,j=0;i<=n;i++)
            rk[sa[i]]=(t[sa[i]]==t[sa[i-1]]&&t[sa[i]+w]==t[sa[i-1]+w])?j:++j;
    }
    void build(char *c,int n){
        for(int i=1;i<=n;i++)rk[i]=c[i];
        for(int i=1;i<=n;i++)t[i]=i;
        sortsa(n,127,0);
        for(int w=1;w<n;w<<=1){
            for(int i=n-w+1,j=0;i<=n;i++)t[++j]=i;
            for(int i=1,j=w;i<=n;i++)if(sa[i]>w)t[++j]=sa[i]-w;
            sortsa(n,n,w);
        }
    }
}
struct BIT{
    int c[N];
    void clear(){
        for(int i=1;i<N;i++)
            c[i]=0;
    }
    void add(int x,int y){
        for(int i=x;i<N;i+=(i&-i))
            c[i]+=y;
    }
    int query(int x){
        int cnt=0;
        for(int i=x;i>=1;i-=(i&-i))
            cnt+=c[i];
        return cnt;
    }
    int query(int l,int r){return query(r)-(l==1?0:query(l-1));}
};
namespace Part1{
    struct node{int l,r,id;};
    vector<node>q[N];
    BIT o0,o1;//o0 is mod 2=0 number, o1 is mod 2=1 number.
    void add(int i,int r,int id){
        q[SA::rk[i]].push_back({i+1,i+2*r-1,id});
    }
    void solve(char *c){
        o0.clear(),o1.clear();
        for(int i=tn;i>=1;i--){
            int t=SA::sa[i];
            if(t<=n){
                for(node u:q[i]){
                    if(u.l&1)ans[u.id]+=o1.query(u.l,u.r);
                    else ans[u.id]+=o0.query(u.l,u.r);
                }
            }
            else if(t>n+1&&t<tn){
                t=tn-t;
                if(t&1)o1.add(t,1);
                else o0.add(t,1);
            }
        }
        for(int i=1;i<=tn;i++)q[i].clear();
    }
}

Part II. 不合法情况

观察一下，我们发现，如果 $S_i<P_{i+2l-1}$ 不满足，必然意味着 $s[i:i+l-1]=R(s[i+l:i+2l-1])$ ，即， $s[i:i+2l-1]$ 是一个回文串！

在这种情况下，考虑一个回文中心 $i,i+1$ ，设她的最大回文半径为 $R_i$ ，考虑 $0\le l \le R_i$ ，则 $S_{i-R_1}\ge P_{i+R_i-1}\Leftrightarrow S_{i+R_i}\ge P_{i-R_i-1}$ 。

又因为回文串的最大半径为 $R_i$ ，也就是说， $S_{i+R_i}$ 和 $P_{i-R_i-1}$ 的前几位必然一样，直到 $R_i$ 为之后才能开始比较。又因为 $R_i$ 是最大的，所以必然有 $s_{i+R_i}\ne s_{i-R_i-1}$ 。所以，只要满足 $s_{i+R_i}\ne s_{i-R_i-1}$ ，就必然有任意的 $0\le l\le R_i$ 都满足 $S_{i-R_i}\ge P_{i+1+R_i}$ 。

现在的问题可以认为是一个：

斜线加。
线段和。

经典，只需要将坐标变换一下后就可以当作二维数点来做

namespace Part2{
    BIT tr;
    struct node{int r,id;};
    vector<node>v[N],q[N];
    char s[N];
    int p[N];
    void add(int i,int r,int id){
        q[i].push_back({i+r,id});
    }
    void solve(char *C){
        int m=0;
        s[m++]=',';
        for(int i=1;i<=n;i++){
            s[m++]='?';
            s[m++]=C[i];
        }
        s[m++]='?';s[m++]='.';
        int c=0,r=0;
        for(int i=1;i<m;i++){
            if(i>=r)p[i]=1;
            else p[i]=min(r-i,p[2*c-i]);
            while(s[i-p[i]]==s[i+p[i]])p[i]++;
            if(i+p[i]>r)r=i+p[i],c=i;
        }
        for(int i=2;i<=n;i++){
            r=p[i*2-1]>>1;
            if(!r||C[i+r]>=C[i-r-1])continue;
            v[i-r].push_back({i,1});
            v[i].push_back({i,-1});
        }
        tr.clear();
        for(int i=1;i<=n;i++){
            for(node u:v[i])tr.add(u.r,u.id);
            for(node u:q[i])ans[u.id]-=tr.query(u.r);
            v[i].clear(),q[i].clear();
        }
    }
}

Code

#include <bits/stdc++.h>
using namespace std;
const int N=410010;
int T,cid,n,m,ans[N],tn;
char c[N],tmpc[N];
namespace SA{
    int sa[N],rk[N],t[N],cnt[N];
    void init(){
        memset(t,0,sizeof(t));
        memset(rk,0,sizeof(rk));
        memset(sa,0,sizeof(sa));
    }
    void sortsa(int n,int m,int w){
        for(int i=0;i<=m;i++)cnt[i]=0;
        for(int i=1;i<=n;i++)cnt[rk[t[i]]]++;
        for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
        for(int i=n;i;i--)sa[cnt[rk[t[i]]]--]=t[i];
        for(int i=1;i<=n;i++)t[i]=rk[i];
        for(int i=1,j=0;i<=n;i++)
            rk[sa[i]]=(t[sa[i]]==t[sa[i-1]]&&t[sa[i]+w]==t[sa[i-1]+w])?j:++j;
    }
    void build(char *c,int n){
        for(int i=1;i<=n;i++)rk[i]=c[i];
        for(int i=1;i<=n;i++)t[i]=i;
        sortsa(n,127,0);
        for(int w=1;w<n;w<<=1){
            for(int i=n-w+1,j=0;i<=n;i++)t[++j]=i;
            for(int i=1,j=w;i<=n;i++)if(sa[i]>w)t[++j]=sa[i]-w;
            sortsa(n,n,w);
        }
    }
}
struct BIT{
    int c[N];
    void clear(){
        for(int i=1;i<N;i++)
            c[i]=0;
    }
    void add(int x,int y){
        for(int i=x;i<N;i+=(i&-i))
            c[i]+=y;
    }
    int query(int x){
        int cnt=0;
        for(int i=x;i>=1;i-=(i&-i))
            cnt+=c[i];
        return cnt;
    }
    int query(int l,int r){return query(r)-(l==1?0:query(l-1));}
};
namespace Part1{
    struct node{int l,r,id;};
    vector<node>q[N];
    BIT o0,o1;//o0 is mod 2=0 number, o1 is mod 2=1 number.
    void add(int i,int r,int id){
        q[SA::rk[i]].push_back({i+1,i+2*r-1,id});
    }
    void solve(char *c){
        o0.clear(),o1.clear();
        for(int i=tn;i>=1;i--){
            int t=SA::sa[i];
            if(t<=n){
                for(node u:q[i]){
                    if(u.l&1)ans[u.id]+=o1.query(u.l,u.r);
                    else ans[u.id]+=o0.query(u.l,u.r);
                }
            }
            else if(t>n+1&&t<tn){
                t=tn-t;
                if(t&1)o1.add(t,1);
                else o0.add(t,1);
            }
        }
        for(int i=1;i<=tn;i++)q[i].clear();
    }
}
namespace Part2{
    BIT tr;
    struct node{int r,id;};
    vector<node>v[N],q[N];
    char s[N];
    int p[N];
    void add(int i,int r,int id){
        q[i].push_back({i+r,id});
    }
    void solve(char *C){
        int m=0;
        s[m++]=',';
        for(int i=1;i<=n;i++){
            s[m++]='?';
            s[m++]=C[i];
        }
        s[m++]='?';s[m++]='.';
        int c=0,r=0;
        for(int i=1;i<m;i++){
            if(i>=r)p[i]=1;
            else p[i]=min(r-i,p[2*c-i]);
            while(s[i-p[i]]==s[i+p[i]])p[i]++;
            if(i+p[i]>r)r=i+p[i],c=i;
        }
        for(int i=2;i<=n;i++){
            r=p[i*2-1]>>1;
            if(!r||C[i+r]>=C[i-r-1])continue;
            v[i-r].push_back({i,1});
            v[i].push_back({i,-1});
        }
        tr.clear();
        for(int i=1;i<=n;i++){
            for(node u:v[i])tr.add(u.r,u.id);
            for(node u:q[i])ans[u.id]-=tr.query(u.r);
            v[i].clear(),q[i].clear();
        }
    }
}
void WZH(){
    SA::init();
    scanf("%d%d%s",&n,&m,c+1);
    tn=0;
    for(int i=1;i<=n;i++)tmpc[++tn]=c[i];
    tmpc[++tn]=50;
    for(int i=n;i;i--)tmpc[++tn]=c[i];
    tmpc[++tn]=40;
    SA::build(tmpc,tn);
    for(int i=1;i<=m;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        //Add Something.
        Part1::add(l,r,i);
        Part2::add(l,r,i);
    }
    //do something.
    Part1::solve(tmpc);
    Part2::solve(c);
    for(int i=1;i<=m;i++)printf("%d\n",ans[i]),ans[i]=0;
}
int main(){
    // freopen("string2.in","r",stdin);
    // freopen("string.out","w",stdout);
    scanf("%d%d",&cid,&T);
    while(T--)WZH();
    return 0;
}