ABC272F Two Strings

题意：给定两个长度为 $n$ 的字符串 $S, T$，定义 $f(S, i)$ 表示将前 $i$ 个字符放在最后得到的字符串，问有多少个 $(i, j)(0\leq i, j <n)$ 满足 $f(S, i)\leq f(T, j)$。$n\leq 2\times 10 ^ 5$，$S, T$ 仅由小写英文字符构成。

场上没做出来，靠 G 的随机化才上了分……

我们尝试把 $S, T$ 拼在一起，然后把 $f(S, i)\leq f(T, j)$ 设置为整个字符串内部的某些后缀的大小关系。经过构造可以这样：

$$S + S + \texttt a ^ n + T + T + \texttt z ^ n$$

首先两倍是很显然的，因为我们需要把前 $i$ 个拼到最后面，复制一遍显然是比较好的选择。如果 $f(S, i) < f(T, j)$，那么在新字符串中，他们对应的后缀一定满足小于关系。如果 $f(S, i) = f(T, j)$ 的话，容易发现他们一定会跳过本身的 $S, T$，而变成 $\tt a, z$ 的比较了。那么也就是说新的字符串，我们只需要比较新的字符串中 $S, T$ 区间的大小关系。

这个怎么做呢？其实我场上想到这了，但是没想到这是一个 SA 板子 /kk。直接做就好了，复杂度 $O(n\log n)$ 或者 $O(n)$。

int main()
{
	std::cin >> n;
	scanf("%s%s", a + 1, b + 1);
	int m = 2 * n;
	for (int i = 1; i <= n; ++ i) s[i] = s[i + n] = a[i];
	for (int i = 1; i <= n; ++ i) s[++ m] = 'a';
	for (int i = 1; i <= n; ++ i) s[i + m] = s[i + n + m] = b[i];
	m += 2 * n;
	for (int i = 1; i <= n; ++ i) s[++ m] = 'z';
	get_sa(s);
	LL res = 0;
	for (int i = 1, cnt = 0; i <= m; ++ i)
		if (sa[i] <= n) cnt ++;
		else if (sa[i] > 3 * n && sa[i] <= 4 * n) res += cnt;
	std::cout << res << '\n';
	return 0;
}