相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4278
解题报告
考虑归并排序
唯一麻烦的地方就是两个字符相同时选哪个
我们可以比较后缀的字典序来解决这个问题
具体实现上,我们可以使用SA
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 800009; const int SGZ = 1001; int n, m, s[N]; class Suffix_Array{ int *rk, *tmp, sa[N], bot[N], arr1[N], arr2[N], que[N]; public: inline void build(int *s, int nn) { rk = arr1; tmp = arr2; int sgz = SGZ; for (int i = 1; i <= nn; i++) bot[s[i]]++; for (int i = 1; i <= sgz; i++) bot[i] += bot[i - 1]; for (int i = 1; i <= nn; i++) que[bot[s[i]]--] = i; rk[que[1]] = sgz = 1; for (int i = 2; i <= nn; i++) rk[que[i]] = (sgz += s[que[i]] != s[que[i - 1]]); for (int l = 1; l < nn && sgz < nn; l <<= 1) { int tt = 0; for (int i = nn - l + 1; i <= nn; i++) tmp[++tt] = i; for (int i = 1; i <= nn; i++) if (que[i] > l) tmp[++tt] = que[i] - l; for (int i = 0; i <= sgz; i++) bot[i] = 0; for (int i = 1; i <= nn; i++) bot[rk[i]]++; for (int i = 1; i <= sgz; i++) bot[i] += bot[i - 1]; for (int i = nn; i; i--) que[bot[rk[tmp[i]]]--] = tmp[i]; swap(rk, tmp); rk[que[1]] = sgz = 1; for (int i = 2; i <= nn; i++) { rk[que[i]] = (sgz += tmp[que[i]] != tmp[que[i - 1]] || tmp[que[i] + l] != tmp[que[i - 1] + l]); } } } inline int rank(int p) { return rk[p]; } }sa; inline int read() { char c = getchar(); int ret = 0, f = 1; for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar()); for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar()); return ret * f; } int main() { n = read(); for (int i = 1; i <= n; i++) { s[i] = read(); } s[n + 1] = 1001; m = read(); for (int i = 1; i <= m; i++) { s[i + n + 1] = read(); } sa.build(s, n + m + 1); for (int i = 1, j = 1, k = 1; k <= n + m; k++) { if (i <= n && j <= m) { if (s[i] < s[j + n + 1] || (s[i] == s[j + n + 1] && sa.rank(i) < sa.rank(j + n + 1))) { printf("%d ", s[i++]); } else { printf("%d ", s[n + 1 + j++]); } } else if (i <= n) { printf("%d ", s[i++]); } else { printf("%d ", s[n + 1 + j++]); } } return 0; }