[bzoj 4104] [Thu Summer Camp 2015]解密运算

给一个长度为n的字符串, 在末尾添加字典序小于其他字符的'.', (n+1)个循环右移按字典序从小到大排列, 取出每个串的最后一个字符, 按照顺序排成一个新的字符串. 现在给出这个新串, 求原串. (n, 字符集大小m ≤ 2*10^5)

.ABCAAA
A.ABCAA
AA.ABCA
AAA.ABC
ABCAAA.
BCAAA.A
CAAA.AB

ABCAAA -> AAAC.AB

读了一遍题面, 似曾相识......一翻PPT, 果然九老师在冬令营上讲过, 但是当时没听懂......它的学名叫 Burrows-Wheeler transform. 先做一遍这个变换, 再跑游程编码, 会使压缩的效果更好.

自己摸索一下.

设排序后第i行第j列的字符为A[i][j] (从1开始标号).

新串是原串所有字符的一个排列, 因此, sort一遍, 得到了第一列.

._____A
A_____A
A_____A
A_____C
A_____.
B_____A
C_____B

然后, 我们获知, 原串中有子串 A[i][n+1] + A[i][1]. 对于样例, 它们是:

A.
AA
AA
CA
.A
AB
BC

出现一点小问题. 第一列有4个A, .AAB分别对应哪个A呢?

不过, 至此, 对于所有字符各不相同的情况, 我们已经得到一个的算法.

把(n+1)个长度为2的子串sort一遍:

.A
A.
AA
AA
AB
BC
CA

现在就知道对应关系啦!

.A____A
A.____A
AA____A
AA____C
AB____.
BC____A
CA____B

1,2,3,6行生成的子串的首字母都是A, 但它们的第二个字符满足A[1][1]≤A[2][1]≤A[3][1]≤A[6][1], 因此排序后也是1,2,3,6.

我们归纳出: 最后一列的第k个c = 第一列的第k个c.

所以, 把它们合并起来:

._____A_____A_____A_____C_____B_____A_____.

x_____y说的是, 从y循环向左走n位得到x - 也就是循环向右走一位. 于是, 我们需要快速得到: 1. 排名为i (以字符为第一关键字, 位置为第二关键字) 的字母在最后一列的第几行. 2. 第i行第一列的字母是什么?

const int N = 2e5;

pair<int, int> p[N];

int main()
{
	int n, m, x = 0;
	scanf("%d%d", &n, &m);
	rep (i, 0, n+1) {
		int s;
		scanf("%d", &s);
		p[i] = make_pair(s, i);
	}
	sort(p, p+n+1);
	rep (i, 0, n) {
		x = p[x].second;
		printf("%d ", p[x].first);
	}
	puts("");
	return 0;
}