跳至主要內容

[Easy] P5108 仰望半月的夜空

xiezheyuan2025/2/8做题笔记后缀自动机线段树约 865 字大约 4 分钟

简要题意

给定一个长度为 nn 的序列 aa，你需要对于每一个 L∈[1,n]L\in [1,n]，求所有长度为 LL 的区间中，字典序最小的区间的左端点（若有多个相同的区间，输出最小左端点）。

1≤n≤3×105,1≤ai≤1071\leq n\leq 3\times 10^5,1\leq a_i\leq 10^7。

思路

挺简单的 SAM 题，自己独立都可以想出来。

首先看到题目，对于一个字符串搞点抽象东西，SAM 或者 SA 没得跑了，但是我不是很会 SA，所以选择 SAM。然后问题就是如何在 SAM 上刻画字典序信息？在 trans 边上搞就没有前途，所以考虑 parent tree。

由于 parent tree 的本质其实是一个二度点压缩的 trie，所以可以干很多 trie 能干的操作。而 trie 维护字典序再容易不过了，对 trie 跑 dfs，每次访问钦定出边顺序即可。这个想法可以自然地迁移到 parent tree 上。

具体地，我们建立反串的 SAM，记录每个点的 LiL_i 表示每个节点（endpos 等价类）所代表的在原串的最小左端点，然后在 parent tree 上 dfs，将所有出边按照下一个字符排序，从大到小访问。访问到一个节点，就维护一个数据结构，支持区间赋值单点询问，每次将这个 endpos 等价类覆盖的长度区间推平为 LiL_i，最后查询答案。这个数据结构线段树就可以维护。

时间复杂度 O(nlog⁡n)O(n\log n)。

代码

#include <bits/stdc++.h>
#define ls (i << 1)
#define rs (i << 1 | 1)
using namespace std;

template<int N>
struct SuffixAutomaton {
    int link[N << 1], len[N << 1], cur, tot;
    int cnt, lst[N << 1], per[N <<1];
    vector<int> ptr[N << 1];
    map<int, int> trans[N << 1];

    SuffixAutomaton(){ link[0] = -1; }

    void extend(int c){
        int x = cur; cur = ++tot;
        len[cur] = len[x] + 1;
        lst[cur] = ++cnt, per[cnt] = cur;
        for(;(~x)&&(!trans[x][c]);x=link[x]) trans[x][c] = cur;
        if(!(~x)) return link[cur] = 0, void();
        int y = trans[x][c];
        if(len[y] == len[x] + 1) return link[cur] = y, void();
        int u = ++tot, d = y;
        link[u] = link[y], link[d] = link[cur] = u, len[u] = len[x] + 1;
        for(auto i : trans[d]) trans[u][i.first] = i.second;
        for(;(~x)&&(trans[x][c]==y);x=link[x]) trans[x][c] = u;
    }

    void build(){
        for(int i=1;i<=tot;i++) ptr[link[i]].push_back(i);
    }
};

const int N = 3e5 + 5;
int n, a[N];
SuffixAutomaton<N> sam;

int lft[N << 1], tag[N << 2];

void pushdown(int i){
    if(!tag[i]) return;
    tag[ls] = tag[rs] = tag[i], tag[i] = 0;
}

void update(int ql, int qr, int v, int i, int l, int r){
    if(ql <= l && r <= qr) return tag[i] = v, void();
    pushdown(i);
    int mid = (l + r) >> 1;
    if(ql <= mid) update(ql, qr, v, ls, l, mid);
    if(mid < qr) update(ql, qr, v, rs, mid + 1, r);
}

int query(int p, int i, int l, int r){
    if(l == r) return tag[i];
    pushdown(i);
    int mid = (l + r) >> 1;
    if(p <= mid) return query(p, ls, l, mid);
    else return query(p, rs, mid + 1, r);
}

void dfs(int u){
    sort(sam.ptr[u].begin(), sam.ptr[u].end(), [u](int x, int y){
        return a[lft[x] + sam.len[u]] > a[lft[y] + sam.len[u]];
    });
    if(u) update(sam.len[sam.link[u]] + 1, sam.len[u], lft[u], 1, 1, n);
    for(int v : sam.ptr[u]) dfs(v);
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int sigma; cin >> sigma >> n;
    if(sigma == 26){
        string s; cin >> s;
        for(int i=0;i<s.size();i++) a[i + 1] = s[i] - 'a';
    }
    else{
        for(int i=1;i<=n;i++) cin >> a[i];
    }
    for(int i=n;i;i--) sam.extend(a[i]);
    sam.build();
    for(int i=1;i<=n;i++){
        for(int u=sam.per[n-i+1];~u&&!lft[u];u=sam.link[u]) lft[u] = i;
    }
    dfs(0);
    for(int i=1;i<=n;i++) cout << query(i, 1, 1, n) << ' ';
    cout << '\n';
    return 0;
}

// Written by xiezheyuan