洛谷 5108 仰望半月的夜空

首先，对于 YS(L)，字典序最小，只需要在后缀数组 sa 中找到最小的 i 满足 n−sai+1≥L。
然而又要求左端点最小。

注意到由于后缀数组是按照字典序排序的，所以如果某些后缀的前 L 个字符相等，也就是 LCP 的长度不小于 L，则它们在后缀数组中一定是连续的。
又因为 i 是最小的，所以别的这些前 L 个字符相等的后缀一定在 i 之后。
考虑到 height 数组的性质：两个后缀的 LCP 长度相当于其在后缀数组的排名间的 RMQ。
则由于 RMQ 具有单调性，可以二分来找这个区间的右端点。

找到之后，只需要对后缀数组上这一段在原串中的下标求个最小值就行了。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 3e5;
const int M = 1e7 + 1;
const int LG = 19;
int sig,n,a[N + 5];
int lg2[N + 5];
int sa[N + 5],rk[N + 5],tpr[N + 5],c[M + 5],height[N + 5];
int st[2][LG + 5][N + 5];
void build_SA()
{
    static int m = sig;
    memset(c,0,sizeof c);
    for(register int i = 1;i <= n;++i)
        ++c[rk[i] = a[i]];
    for(register int i = 1;i <= m;++i)
        c[i] += c[i - 1];
    for(register int i = n;i;--i)
        sa[c[rk[i]]--] = i;
    for(register int w = 1,p = 0;p < n;w <<= 1,m = p)
    {
        p = 0;
        for(register int i = 1;i <= w;++i)
            tpr[++p] = n - w + i;
        for(register int i = 1;i <= n;++i)
            if(sa[i] > w)
                tpr[++p] = sa[i] - w;
        memset(c,0,sizeof c);
        for(register int i = 1;i <= n;++i)
            ++c[rk[i]];
        for(register int i = 1;i <= m;++i)
            c[i] += c[i - 1];
        for(register int i = n;i;--i)
            sa[c[rk[tpr[i]]]--] = tpr[i];
        swap(rk,tpr),rk[sa[1]] = p = 1;
        for(register int i = 2;i <= n;++i)
            rk[sa[i]] = tpr[sa[i]] == tpr[sa[i - 1]] && tpr[sa[i] + w] == tpr[sa[i - 1] + w] ? p : ++p;
    }
    for(register int i = 1,k = 0;i <= n;++i)
    {
        k -= (bool)k;
        for(;a[i + k] == a[sa[rk[i] - 1] + k];++k);
        height[rk[i]] = k;
    }
}
int query(int op,int l,int r)
{
    int lg = lg2[r - l + 1];
    return min(st[op][lg][l],st[op][lg][r - (1 << lg) + 1]);
}
int main()
{
    scanf("%d%d",&sig,&n),++sig;
    if(sig == 27)
    {
        char ch;
        for(register int i = 1;i <= n;++i)
            scanf(" %c",&ch),a[i] = ch - 'a' + 1;
    }
    else
        for(register int i = 1;i <= n;++i)
            scanf("%d",a + i),++a[i];
    build_SA();
    for(register int i = 1;i <= n;++i)
        st[0][0][i] = height[i],st[1][0][i] = sa[i];
    for(register int i = 2;i <= n;++i)
        lg2[i] = lg2[i >> 1] + 1;
    for(register int i = 1;i <= LG;++i)
        for(register int j = 1;j + (1 << i) - 1 <= n;++j)
            st[0][i][j] = min(st[0][i - 1][j],st[0][i - 1][j + (1 << i - 1)]),
            st[1][i][j] = min(st[1][i - 1][j],st[1][i - 1][j + (1 << i - 1)]);
    for(register int L = 1,i = 1,l,r,mid,pos;L <= n;++L)
    {
        for(;n - sa[i] + 1 < L;++i);
        l = i + 1,r = n,pos = i;
        while(l <= r)
            mid = l + r >> 1,query(0,i + 1,mid) >= L ? (l = mid + 1,pos = mid) : (r = mid - 1);
        printf("%d%c",query(1,i,pos)," \n"[L == n]);
    }
}