[USACO07DEC]Best Cow Line G

题目背景

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

题目描述

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

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

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

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

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

输入格式

第一行一个整数 NNN。

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

输出格式

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

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

样例 #1

样例输入 #1

6
A
C
D
B
C
B

样例输出 #1

ABCBCD

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], 说明从尾选一个字符

#include 
using namespace std;
const int N = 2e6 + 10;char s[N];
char ans[N];
int len;
int n, m;	//n是后缀个数， m是桶的个数
int x[N];	//桶数组
int y[N];	//辅助数组
int c[N];	//计数数组
int sa[N];	//sa[k] 表示排名为k的数组后缀编号
int rk[N];	//rk[k] 表示后缀字符串k 的排名
int height[N];	// heght[k] = lcp(sa[i], sa[i - 1])void get_sa()
{int i, k;// 按第一个字母排序for(i = 1; i <= n; ++i)	// 按第一个字母编桶号， 并累计c[(x[i] = s[i])]++;for(i = 1; i <= m; ++i)	c[i] += c[i - 1];for(i = n; i; --i)		//后缀i的排序是i 所在桶号的剩余累计值sa[c[x[i]]--] = i;for(k = 1; k <= n; k <<= 1)	// logn 轮{// 按第二关键字排序memset(c, 0, sizeof c);for(i = 1; i <= n; ++i)	y[i] = sa[i];for(i = 1; i <= n; ++i)	c[x[y[i] + k]]++;for(i = 1; i <= m; ++i) c[i] += c[i - 1];for(i = n; i; i--) sa[c[x[y[i] + k]]--] = y[i];//按第一关键字排序memset(c, 0, sizeof c);for(i = 1; i <= n; ++i)	y[i] = sa[i];for(i = 1; i <= n; ++i)	c[x[y[i]]]++;for(i = 1; i <= m; ++i)	c[i] += c[i - 1];for(i = n; i; --i)	sa[c[x[y[i]]]--] = y[i];//把后缀放入桶数组for(i = 1; i <= n; ++i)	y[i] = x[i];for(m = 0, i = 1; i <= n; ++i){if(y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k])x[sa[i]] = m;elsex[sa[i]] = ++m;	// 相邻后缀的关键字不相等则放入新桶}if(m == n)	break;}
}// 定理 height[rk[i]] >= height[rk[i - 1]] - 1;
void get_height()
{for(int i = 1; i <= n; ++i)rk[sa[i]] = i;for(int i = 1, k = 0; i <= n; ++i)	//枚举后缀i{if(rk[i] == 1)	continue;		//第一名height 为0if(k) k--;						//上一个后缀的height 值减 1int j = sa[rk[i] - 1];			//找出后缀i的前邻后缀 jwhile(i + k <= n && j + k <= n && s[i + k] == s[j + k])k++;height[rk[i]] = k;}
}int main()
{scanf("%d", &n);char ch[10];for(int i = 1; i <= n; ++i){scanf("%s", ch);s[i] = ch[0];}for(int i = 1; i <= n; ++i)s[2 * n + 1 - i] = s[i];n *= 2;m = 90;get_sa();for(int i = 1; i <= n; ++i)rk[sa[i]] = i;int i = 1, j = 1, step = n / 2;for(int k = 1; k <= step; ++k){if(rk[i] < rk[step + j]){ans[++len] = s[i];//	printf("%c", s[i]);	++i;}else{ans[++len] = s[step + j];//	printf("%c", s[step + j]);	++j;}}for(int i = 1; i <= len; ++i){printf("%c", ans[i]);if(i % 80 == 0)printf("\n");}
//	printf("\n");return 0;
}