题目概述

Suffix Automaton

解题报告

被时限骗了，以为做法是两个 $\log$（空间爆炸），其实只要离线就可以一个 $\log$ 。

求出后缀数组后，第 $i$ 个后缀多出来的就是 $[SA_i,SA_i+H_i\sim n]$ 共 $n-(SA_i+H_i)+1$ 个子串。对应的长度区间是 $[H_i+1,n-SA_i+1]$ 。

如果用主席树就可以实现动态查找第 $K$ 小，但是这样是两个 $\log$ ，而且空间复杂度爆炸了。

由于第 $i$ 个点出现在 $[H_i+1,n-SA_i+1]$ 长度区间中，我们可以在 $H_i+1$ 插入 $i$ ，在 $n-SA_i+2$ 删除 $i$ ，用扫描线+线段树维护每个长度对应的后缀位置。因此考虑离线，将询问从小到大排序后从小到大考虑长度。

设当前长度为 $i$ ，$cnt$ 表示 $[1,i-1]$ 长度子串个数，$sum$ 表示长度为 $i$ 子串个数，那么如果 $cnt<K\le cnt+sum$ 就说明第 $K$ 小子串的长度为 $i$ ，然后在线段树里二分第 $K-cnt$ 小就可以得知对应位置。

由于要求出答案子串第一次出现的位置，还需要在后缀数组上二分一下，然后求出符合区间中最靠前的位置。

示例程序

#include<cstdio>
#include<cctype>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
typedef long long LL;
const int maxn=1000000,maxt=maxn<<2,LOG=20;

int te,n;char s[maxn+5];
int Q,ans[maxn+5][2];pair<LL,int> q[maxn+5];
int SA[maxn+5],rk[maxn+5],t[(maxn<<1)+5],ha[maxn+5];
int H[maxn+5],RMQ[maxn+5][LOG+1],MIN[maxn+5][LOG+1],lg[maxn+5];
int m;pair<int, pair<int,int> > a[(maxn<<1)+5];
int sum[maxt+5];

#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
int reads(char *s){
    int len=0;char ch=readc();
    while (!islower(ch)) ch=readc();
    while (islower(ch)) s[++len]=ch,ch=readc();
    s[len+1]=0;return len;
}
template<typename T> void writei(T x){
    static int len=0,buf[100];
    if (x<0) putchar('-'),x=-x;
    do buf[len++]=x%10,x/=10; while (x);
    while (len) putchar(buf[--len]+48);
}
void Sort(int n,int m){
    for (int i=0;i<=m;i++) ha[i]=0;for (int i=1;i<=n;i++) ha[rk[i]]++;
    for (int i=1;i<=m;i++) ha[i]+=ha[i-1];for (int i=n;i;i--) SA[ha[rk[t[i]]]--]=t[i];
}
#define min(x,y) ((x)<(y)?(x):(y))
void Make(int n,int m=255){
    for (int i=1;i<=n;i++) rk[i]=s[i],t[i]=i,t[i+n]=0;Sort(n,m);
    for (int k=1,p=0;p<n;m=p,k<<=1){
        p=0;for (int i=n-k+1;i<=n;i++) t[++p]=i;
        for (int i=1;i<=n;i++) if (SA[i]>k) t[++p]=SA[i]-k;
        Sort(n,m);for (int i=1;i<=n;i++) t[i]=rk[i];rk[SA[1]]=p=1;
        for (int i=2;i<=n;i++) rk[SA[i]]=(p+=t[SA[i-1]]!=t[SA[i]] || t[SA[i-1]+k]!=t[SA[i]+k]);
    }
    for (int i=1,k=0;i<=n;i++){
        if (k) k--;
        while (s[i+k]==s[SA[rk[i]-1]+k]) k++;
        H[rk[i]]=k;
    }
    H[1]=0;
    for (int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
    for (int i=1;i<=n;i++) RMQ[i][0]=H[i],MIN[i][0]=SA[i];
    for (int j=1;(1<<j)<=n;j++)
        for (int i=1;i+(1<<j)-1<=n;i++)
            RMQ[i][j]=min(RMQ[i][j-1],RMQ[i+(1<<j-1)][j-1]),
            MIN[i][j]=min(MIN[i][j-1],MIN[i+(1<<j-1)][j-1]);
}
int LCP(int L,int R){
    L++;int k=lg[R-L+1];
    return min(RMQ[L][k],RMQ[R-(1<<k)+1][k]);
}
int Min(int L,int R){
    int k=lg[R-L+1];
    return min(MIN[L][k],MIN[R-(1<<k)+1][k]);
}
void Insert(int pos,int k,int l=1,int r=n,int p=1){
    sum[p]+=k;if (l==r) return;
    int mid=l+(r-l>>1);
    pos<=mid?Insert(pos,k,l,mid,p<<1):Insert(pos,k,mid+1,r,p<<1|1);
}
int Find(int k,int l=1,int r=n,int p=1){
    if (l==r) return l;
    int mid=l+(r-l>>1);
    return k<=sum[p<<1]?Find(k,l,mid,p<<1):Find(k-sum[p<<1],mid+1,r,p<<1|1);
}
int main(){
    n=reads(s);Make(n);
    for (int i=1;i<=n;i++)
        if (H[i]<n-SA[i]+1) a[++m]=mp(H[i]+1,mp(i,1)),a[++m]=mp(n-SA[i]+2,mp(i,-1));
    sort(a+1,a+1+m);
    readi(Q);for (int i=1;i<=Q;i++) readi(q[i].fr),q[i].sc=i;
    sort(q+1,q+1+Q);
    LL cnt=0;
    for (int i=1,j=1,k=1;i<=n && k<=Q;i++){
        while (j<=m && a[j].fr==i) Insert(a[j].sc.fr,a[j].sc.sc),j++;
        while (k<=Q && q[k].fr<=cnt+sum[1]){
            int p=Find(q[k].fr-cnt);
            int L=1,R=p-1;
            for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1))
                LCP(mid,p)>=i?R=mid-1:L=mid+1;
            int ql=L;
            L=p+1;R=n;
            for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1))
                LCP(p,mid)>=i?L=mid+1:R=mid-1;
            int qr=R;
            ans[q[k].sc][0]=Min(ql,qr);ans[q[k].sc][1]=ans[q[k].sc][0]+i-1;
            k++;
        }
        cnt+=sum[1];
    }
    for (int i=1;i<=Q;i++)
        if (ans[i][0]) writei(ans[i][0]),putchar(' '),writei(ans[i][1]),puts("");
        else puts("-1 -1");
    return 0;
}