[后缀数组 贪心] BZOJ 4278 [ONTAK2015]Tasowanie

两个指针 显然小的那个先放 如果一样 比后一个 再一样 再后 然后就转化成比较后缀的字典序了

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;

inline char nc(){
  static char buf[100000],*p1=buf,*p2=buf;
  return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &x){
  char c=nc(),b=1;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}

const int N=400005;

int n1,n2;
int n,a[N];

int t1[N],t2[N],c[N],sa[N];
int rank[N];

inline void SA(int *a,int m){
  int *x=t1,*y=t2;
  for (int i=1;i<=m;i++) c[i]=0;
  for (int i=1;i<=n;i++) c[x[i]=a[i]]++;
  for (int i=1;i<=m;i++) c[i]+=c[i-1];
  for (int i=n;i;i--) sa[c[x[i]]--]=i;
  for (int k=1;k<=n;k<<=1){
    int p=0;
    for (int i=n-k+1;i<=n;i++) y[++p]=i;
    for (int i=1;i<=n;i++) if (sa[i]>k) y[++p]=sa[i]-k;
    for (int i=1;i<=m;i++) c[i]=0;
    for (int i=1;i<=n;i++) c[x[y[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];
    swap(x,y);
    x[sa[1]]=1; p=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])?p:++p;
    if (p>=n) break;
    m=p;
  }
}

int main(){
  freopen("t.in","r",stdin);
  freopen("t.out","w",stdout);
  read(n1); for (int i=1;i<=n1;i++) read(a[i]);
  a[n1+1]=1001;
  read(n2); for (int i=1;i<=n2;i++) read(a[i+n1+1]);
  n=n1+1+n2;
  SA(a,1001);
  for (int i=1;i<=n;i++) rank[sa[i]]=i;
  int p=1,q=1;
  while (p<=n1 || q<=n2) if (p>n1)
      printf("%d ",a[(q++)+n1+1]);
    else if (q>n2)
      printf("%d ",a[p++]);
    else if (rank[p]<rank[q+n1+1])
      printf("%d ",a[p++]);
    else
      printf("%d ",a[(q++)+n1+1]);
  return 0;
}