ABC280ex 题解

· · 题解

题目描述

题目链接：ABC280Ex。

给定 n 个字符串，q 次询问，每次询问第 k 小的子串。n,q,\sum |s_i| \le 10^5。

题解

官方题解好复杂！官方题解怎么是离线！怎么没有洛谷题解！

提供一种简单的在线后缀数组做法。

以下的排名指的都是一个串在所有子串里的排名。

一般来说，求第 k 小难于求排名，我们考虑如果给定一个子串，求它的排名怎么做。

先建出 SA，排好序，考虑下面的例子，我们要查后缀 s = \texttt{suffixaaaaa} 中子串 t = \texttt{suf} 的排名：

\begin{aligned}&\texttt{\color{red}{sam}\color{black}}\\&\texttt{\color{blue}{suf}\color{black}fix}\\&\texttt{\color{blue}{suf}\color{black}fixaaaaa}\\&\texttt{\color{blue}{suf}\color{black}fixarray}\\&\texttt{\color{red}{su}\color{black}uffix}\\&\color{black}\texttt{zpxpxp}\end{aligned}

可以看到，后缀被分为三种不同类型：

我们直接二分出 \operatorname{LCP} \ge |t| 的排名区间 [l,r]，第一部分贡献前缀和，第二部分贡献为 (|t| - 1)(r-l+1)，第三部分贡献是 \sum \limits_{i=r+1}^n \min \limits_{j=r+1}^i\{h_{j}\}，可以单调栈预处理，\mathcal O(1) 查询。至此，我们在 \mathcal O(\log n) 的时间复杂度内求出了一个子串的排名。

一般来说我们会求排名以后就可以多一只 \log 二分求第 k 小，但是我们还有一个问题：二分什么。

我们来证明一个结论：

排名为 k 的子串一定是排名小于 k 里的后缀里排名最大的后缀，或者是排名大于等于 k 的后缀里排名最小的后缀的一个前缀。

第一部分是显然的：令这个串是 s_1，任何排名小于等于 s_1 的后缀的任何前缀字典序都小于等于 s_1，那么它们的排名也一定小于 k。

第二部分证明也很简单，不妨设这个后缀是 s_1，任意一个排名大于 k 的非 s_1 的后缀为 s_2，我们可以证明第 k 小的子串 ans 如果是 s_2 的前缀，一定也是 s_1 的前缀。

预处理出每一个后缀在所有子串里的排名，显然这个值随着 SA 里的 rk 数组递增。每次询问时，二分出 k 的前驱后继，在 k 的后继里二分得到小于等于 k 的最大子串，与前驱比较后取 \max 输出即可。

时间复杂度 \mathcal O(n \log n + q \log^2 n)。

用了 atcoder 的 SA。

/**
 *    author: sunkuangzheng
 *    created: 12.02.2024 14:33:15
**/
#include<bits/stdc++.h>
#ifdef DEBUG_LOCAL
#include <mydebug/debug.h>
#endif
#include <atcoder/string>
using ll = long long;
const int N = 5e5+5;
using namespace std;
using namespace atcoder;
int T,n,m,le[N],al[N],sa[N],rk[N],q,h[N],st[22][N],pos[N],st2[N],tp,sta[N],bl[N];string t[N],s;
ll rk2[N],sm[N],k,sm2[N];
void los(){
    cin >> n;
    for(int i = 1;i <= n;i ++){
        cin >> t[i],al[i] = s.size() + 1,le[i] = t[i].size(),s += t[i] + '#';
        for(int j = al[i];j < s.size();j ++) pos[j] = t[i].size() - (j - al[i]),sta[j] = (j - al[i] + 1),bl[j] = i;
    }vector<int> _sa = suffix_array(s);m = s.size(),s = " " + s;
    for(int i = 1;i <= m;i ++) sa[i] = _sa[i - 1] + 1,rk[sa[i]] = i;
    for(int i = 1,k = 0;i <= m;h[rk[i ++]] = k) 
        for(k --,k = max(0,k);s[i + k] != '#' && s[i + k] == s[sa[rk[i] - 1] + k];k ++);
    for(int i = 1;i <= m;i ++) st[0][i] = h[i];
    for(int j = 1;j <= __lg(m);j ++) for(int i = 1;i + (1 << j) - 1 <= m;i ++)
        st[j][i] = min(st[j-1][i],st[j-1][i+(1<<j-1)]);
    auto lcp = [&](int l,int r){
        if(l == r) return m;
        int k = __lg(r - l);
        return min(st[k][l+1],st[k][r-(1<<k)+1]);
    };st2[++tp] = m + 1;
    for(int i = m;i >= 1;i --){
        while(tp && h[st2[tp]] > h[i]) tp --;
        sm2[i] = 1ll * h[i] * (st2[tp] - i) + sm2[st2[tp]],st2[++tp] = i;
    }auto get = [&](int k,int len){
        int l,r,ql,qr;
        for(l = 1,r = k;l <= r;){
            int mid = (l + r) / 2;
            if(lcp(mid,k) >= len) r = mid - 1; else l = mid + 1;
        }ql = r + 1;
        for(l = k,r = m;l <= r;){
            int mid = (l + r) / 2;
            if(lcp(k,mid) >= len) l = mid + 1; else r = mid - 1;
        }qr = l - 1;
        return 1ll * (qr - ql + 1) * (len - 1) + sm[ql - 1] + sm2[qr + 1];
    };for(int i = 1;i <= m;i ++) sm[i] = sm[i - 1] + pos[sa[i]],rk2[i] = (!sm[i] ? -1 : get(i,pos[sa[i]]) + 1);
    for(cin >> q;q --;){
        cin >> k;
        int p = lower_bound(rk2+1,rk2+m+1,k) - rk2,len = pos[sa[p]],l = 1,r = len,res = -1;
        while(l <= r){
            int mid = (l + r) / 2;
            if(get(p,mid) + 1 <= k) l = mid + 1,res = mid; else r = mid - 1;
        }if(res != -1 && get(p,res) >= get(p-1,pos[sa[p-1]])) cout << bl[sa[p]] << " " << sta[sa[p]] << " " << sta[sa[p]] + res - 1 << "\n";
        else p --,cout << bl[sa[p]] << " " << sta[sa[p]] << " " << sta[sa[p]] + pos[sa[p]] - 1 << "\n";
    }
}int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    for(T = 1;T --;) los();
}