题解：P5184 [COCI2009-2010#2] PASIJANS

JimmyLee · 2024-09-24 15:52:10 · 题解

分析

考虑贪心，每次尽量选最小的字符。

显然是每次选字典序最小的弹栈。

我们要比较的是每个栈的字典序，但是朴素比较是 O(L) 的，考虑将它优化到 O(1)。

这个时候我们可以先离散化然后套路地将所有串拼一起跑 SA。

记得在每个串之间加分割符。

这样每次比较字典序就变成了 O(1)。

时间复杂度 O((\sum L)\log (\sum L))。

Code

#include<bits/stdc++.h>
using namespace std;
#define maxn 1001006

int sa[maxn], x[maxn], y[maxn], c[maxn];

void radix_sort(int n, int m)
{
    for(int i=1;i<=m;i++) c[i]=0;
    for(int i=1;i<=n;i++) c[x[i]]++;
    for(int i=1;i<=m;i++) c[i]+=c[i-1];
    for(int i=n;i;i--) sa[c[x[y[i]]]--]=y[i];
}

void suffix_sort(int *s, int n)
{
    int m=1e6+1;
    for(int i=1;i<=n;i++) x[i]=s[i], y[i]=i;
    radix_sort(n, m);
    for(int k=1;k<=n;k<<=1)
    {
        int cnt=0;
        for(int i=n-k+1;i<=n;i++) y[++cnt]=i;
        for(int i=1;i<=n;i++) if(sa[i]>k) y[++cnt]=sa[i]-k;
        radix_sort(n, m);
        swap(x, y);
        x[sa[1]]=cnt=1;
        for(int i=2;i<=n;i++)
            x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?cnt:++cnt;
        if((m=cnt)==n) return;
    }
}

int cont[maxn];
vector<int> wa;
int pos[1003], len[1003], stp[1003];
int rk[maxn];
struct cmp
{
    bool operator()(int a, int b) {return rk[pos[a]]>rk[pos[b]];}
};

priority_queue<int, vector<int>, cmp> pq;

int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        pos[i]=stp[i]=*cont+1;
        cin>>len[i];
        for(int j=1;j<=len[i];j++)
        {
            cin>>cont[++*cont];
            wa.emplace_back(cont[*cont]);
        }
        cont[++*cont]=2e9;
    }
    sort(wa.begin(), wa.end());
    auto end_it=unique(wa.begin(), wa.end());
    for(int i=1;i<=*cont;i++)
        cont[i]=lower_bound(wa.begin(), end_it, cont[i])-wa.begin()+1;
    suffix_sort(cont, *cont);
    for(int i=1;i<=*cont;i++)
        rk[sa[i]]=i;
    for(int i=1;i<=n;i++) pq.emplace(i);
    while(!pq.empty())
    {
        int v=pq.top();
        pq.pop();
        cout<<wa[cont[pos[v]]-1]<<' ';
        pos[v]++;
        if(pos[v]!=stp[v]+len[v]) pq.emplace(v);
    }
}