显然我们每次贪心用堆维护最小的。
但是如果有相同的怎么选择呢？我们就要往后比较了。所以就是一个后缀排序的问题了。
但是要注意，字符串4 2是大于字符串4 2 3的。
所以我们在每个字符串后面增加一个极大值。
AC代码：
#pragma GCC optimize("-Ofast","-funroll-all-loops") #include<bits/stdc++.h> //#define int long long using namespace std; const int N=2e6+10; int n,s[N],num[N],cnt,m,sum[N]; vector<int> v; struct node{int pos,val,id;}; bool operator < (node a,node b){return a.val>b.val;} priority_queue<node> q; int y[N],x[N],c[N],sa[N],rk[N],h[N]; char *fs,*ft,buf[1<<20]; #define gc() (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<20,stdin),fs==ft))?0:*fs++; inline int read(){ int x=0,f=1; char ch=gc(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=gc();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=gc();} return x*f; } void get_SA(int n,int m){ for(int i=1;i<=n;i++) ++c[x[i]=s[i]]; for(int i=2;i<=m;i++) c[i]+=c[i-1]; for(int i=n;i>=1;i--) sa[c[x[i]]--]=i; for(int k=1,num;k<=n;k<<=1){ num=0; for(int i=n-k+1;i<=n;i++) y[++num]=i; for(int i=1;i<=n;i++) if(sa[i]>k) y[++num]=sa[i]-k; for(int i=1;i<=m;i++) c[i]=0; for(int i=1;i<=n;i++) ++c[x[i]]; for(int i=2;i<=m;i++) c[i]+=c[i-1]; for(int i=n;i>=1;i--) sa[c[x[y[i]]]--]=y[i],y[i]=0; swap(x,y),x[sa[1]]=1,num=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])?num:++num; if(num==n) break; m=num; } for(int i=1;i<=n;i++) rk[sa[i]]=i; } void write(int x){if(x>9) write(x/10);putchar(x%10+'0');} signed main(){ n=read(); v.push_back(1e9); for(int i=1;i<=n;i++){ num[i]=read(); sum[i]=sum[i-1]+num[i]+1; for(int j=1;j<=num[i];j++) s[++cnt]=read(),v.push_back(s[cnt]); s[++cnt]=1e9; } sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end()); m=v.size(); for(int i=1;i<=cnt;i++) s[i]=lower_bound(v.begin(),v.end(),s[i])-v.begin()+1; get_SA(cnt,m); for(int i=1;i<=n;i++) q.push({1,rk[sum[i-1]+1],i}); while(q.size()){ node u=q.top(); q.pop(); write(v[s[sum[u.id-1]+u.pos]-1]),putchar(' '); if(u.pos<num[u.id]) q.push({u.pos+1,rk[sum[u.id-1]+u.pos+1],u.id}); } return 0; }