[ONTAK2015]Tasowanie

题目大意：

给你两个长度分别为\(n(n\le2\times10^5)\)的序列\(A,B\)，将\(A,B\)进行二路归并，使得最后得到的序列字典序最小。求最后得到的序列。

思路：

后缀数组，每次贪心地取rank值对应最小的字符即可。

源代码：

#include<cstdio>

#include<cctype>

#include<climits>

#include<algorithm>

inline int getint() {

	register char ch;

	while(!isdigit(ch=getchar()));

	register int x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return x;

}

const int N=4e5+2;

int n,m,len,k,s[N],rank[N],sa[N],tmp[N];

inline bool cmp(const int &i,const int &j) {

	if(rank[i]!=rank[j]) return rank[i]<rank[j];

	const int ri=i+k<=len?rank[i+k]:-1;

	const int rj=j+k<=len?rank[j+k]:-1;

	return ri<rj;

}

inline void suffix_sort() {

	for(register int i=0;i<=len;i++) {

		sa[i]=i;

		rank[i]=s[i];

	}

	for(k=1;k<=len;k<<=1) {

		std::sort(&sa[0],&sa[len]+1,cmp);

		tmp[sa[0]]=0;

		for(register int i=1;i<=len;i++) {

			tmp[sa[i]]=tmp[sa[i-1]]+!!cmp(sa[i-1],sa[i]);

		}

		std::copy(&tmp[0],&tmp[len]+1,rank);

	}

}

int main() {

	n=getint();

	for(register int i=0;i<n;i++) s[i]=getint();

	s[n]=INT_MAX;

	m=getint();

	for(register int i=0;i<m;i++) s[n+i+1]=getint();

	s[n+m+1]=INT_MAX;

	len=n+m+2;

	suffix_sort();

	for(register int i=1,j=0,k=n+1;i<=n+m;i++) {

		int ans=0;

		if(j>=n) {

			ans=s[k++];

		} else if(k>=len-1) {

			ans=s[j++];

		} else {

			ans=rank[j]<rank[k]?s[j++]:s[k++];

		}

		printf("%d%c",ans," \n"[i==n+m]);

	}

	return 0;

}