2

这是一道贪心题（一开始没想到 TAT ）
较简单的情况：目前所有栈的栈顶元素互不相同。显然，当前这步的最优解应该选择栈顶元素最小者，将其放入答案队列。 但是，如果两个栈的栈顶元素相同呢？
乍一看，随意选择一个均可，但是你会发现在样例 3（两个栈中的元素分别为 5 1 2 和 5 1 1）中， 如果第一步选择了一号栈的 5，那么最终结果会得出 5 1 2 5 1 1，而最优解应该是先选二号栈的 5，最终结果为 5 1 1 5 1 2。
假设有两个大小均为 2 的栈 a,b ，a中栈顶元素为 p，接下来是 q1；b 中栈顶元素同样为 p，接下来是 q2。 那么，先选哪个栈好呢？模拟一下，发现： 如果 q1=q2，则继续往后考虑。 若 q1<q2​，则先选栈 a 「肯定不会」「得不到」最优解。模拟 p<q1<q2， q1<p<q2，q1<q2<p。 若 q1>q2，则先选栈 b 肯定不会得不到最优解，自行模拟的东西与上面类似。 一言以蔽之： 每次选择字典序最小的栈，将其栈顶的元素放入答案队列。 把总共 NL 个后缀（N 个数组，每个数组有 L 个）搞个后缀数组出来就行了。然后跑一边后缀数组模板。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1050,inf=0x3f3f3f3f;
int n,L,cnt,s[maxn*maxn],fir[maxn],rank[maxn*maxn],tim,qaq[maxn*maxn],tot,tat[maxn*maxn];
struct node
{
 int pos,val;
 bool operator <(const node& rhs)const{return val>rhs.val;}
};
int sa[maxn*maxn],m,x[maxn*maxn],y[maxn*maxn],c[maxn*maxn];
inline void get_sa(int n)
{
 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 len=1;len<=n;len<<=1)
 {
  int num=0;
  for(int i=n-len+1;i<=n;i++) 
   y[++num]=i;
  for(int i=1;i<=n;i++)
   if(sa[i]>len) 
    y[++num]=sa[i]-len;
  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];
  swap(x,y);
  int tmp=1;x[sa[1]]=1;
  for(int i=2;i<=n;i++)
   x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+len]==y[sa[i-1]+len])?tmp:++tmp;
  if(tmp==n) 
   break;
  m=tmp;
 }
}
priority_queue<node> p;
int main(){
 scanf("%d",&n);
 qaq[tot=1]=inf;
 for(int i=1;i<=n;i++)
 {
  scanf("%d",&L);
  fir[i]=cnt+1;
  tim+=L;
  for(int j=1;j<=L;j++) 
   scanf("%d",&s[++cnt]),qaq[++tot]=s[cnt];
  s[++cnt]=inf;
 }
 sort(qaq+1,qaq+1+tot);
 m=unique(qaq+1,qaq+1+tot)-(qaq+1);
 for(int i=1;i<=cnt;i++)
  tat[i]=s[i],s[i]=lower_bound(qaq+1,qaq+1+m,s[i])-qaq;
 get_sa(cnt);
 for(int i=1;i<=cnt;i++) 
  rank[sa[i]]=i;
 for(int i=1;i<=n;i++) 
  p.push((node){fir[i],rank[fir[i]]});
 for(int i=1;i<=tim;i++)
 {
  node tmp=p.top();
  p.pop();
  printf("%d ",tat[tmp.pos]);
  if(s[tmp.pos+1]!=inf) 
   p.push((node){tmp.pos+1,rank[tmp.pos+1]});
 }
 return 0;
}