洛谷 P2870 [USACO07DEC]Best Cow Line G（后缀数组）

[USACO07DEC]Best Cow Line G

题目背景

本题和 2007 年 11 月月赛银组同名题目 在题意上一致，唯一的差别是数据范围。

题目描述

Farmer John 打算带领 $N$（$1\le N\le 5\times 10^5$）头奶牛参加一年一度的”全美农场主大奖赛“。在这场比赛中，每个参赛者必须让他的奶牛排成一列，然后带领这些奶牛从裁判面前依此走过。

今年，竞赛委员会在接受报名时，采用了一种新的登记规则：取每头奶牛名字的首字母，按照它们在队伍中的次序排成一列。将所有队伍的名字按字典序升序排序，从而得到出场顺序。

FJ 由于事务繁忙，他希望能够尽早出场。因此他决定重排队列。

他的调整方式是这样的：每次，他从原队列的首端或尾端牵出一头奶牛，将她安排到新队列尾部。重复这一操作直到所有奶牛都插入新队列为止。

现在请你帮 FJ 算出按照上面这种方法能排出的字典序最小的队列。

输入格式

第一行一个整数 $N$。

接下来 $N$ 行每行一个大写字母，表示初始队列。

输出格式

输出一个长度为 $N$ 的字符串，表示可能的最小字典序队列。

每输出 $80$ 个字母需要一个换行。

样例 #1

样例输入 #1

6
A
C
D
B
C
B
1
2
3
4
5
6
7

样例输出 #1

ABCBCD
1

1、原字符串 ACDBCB， 反字符串 BCBDCA, 字符串长度为n
	拼接起来 ACDBCBBCBDCA， 字符串长度为 2n, 求拼接字符串的后缀数组
	sa, rk.
2、 得到数组 rk 后， 双指针 i， j 遍历数组 rk, 
	1 <= i <= n, n + 1 <= j <= 2n, 
	rk[i] < rk[j], 说明从头选一个字符，
	rk[i] > rk[j], 说明从尾选一个字符
1
2
3
4
5
6
7

#include 
using namespace std;
const int N = 2e6 + 10;

char s[N];
char ans[N];
int len;
int n, m;	//n是后缀个数， m是桶的个数
1
2
3
4
5
6
7
8