OceanEye's Blog

是时候表演真正的技术了!

@OceanEye10月前

08/8
11:12
OI

BZOJ4278

4278: [ONTAK2015]Tasowanie

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 434  Solved: 203
[Submit][Status][Discuss]

Description

给定两个数字串A和B,通过将A和B进行二路归并得到一个新的数字串T,请找到字典序最小的T。

Input

第一行包含一个正整数n(1<=n<=200000),表示A串的长度。
第二行包含n个正整数,其中第i个数表示A[i](1<=A[i]<=1000)。
第三行包含一个正整数m(1<=m<=200000),表示B串的长度。
第四行包含m个正整数,其中第i个数表示B[i](1<=B[i]<=1000)。

Output

输出一行,包含n+m个正整数,即字典序最小的T串。

Sample Input

6
1 2 3 1 2 4
7
1 2 2 1 3 4 3

Sample Output

1 1 2 2 1 2 3 1 2 3 4 3 4

HINT

Source

[Submit][Status][Discuss]
 

把两个串前后拼在一起 然后用SA处理出rank数组跑归并

中间插一个大大的分隔符就好

听说有姿势奇怪的贪心?【难道是某种神奇的哈希……】

现在不是很想理……

代码

 

BZOJ4278