如标题所述，这是直接排序的 $O(N \log^2 N)$ 代码，可以AC：

#include <cstdio>
#include <string>
#include <cstring>
#include <numeric>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e6 + 5;
int n; string s;
int sa[N << 1], rk[N << 1];
// SA: the ith suffix
// RK: rank of suffix[i]

int main()
{
	cin >> s; n = s.length();
	iota(sa + 1, sa + n + 1, 1);
	for (int i = 1; i <= n; i++)
		rk[i] = s[i - 1];
	for (int l = 1; l < n; l <<= 1)
	{
		sort(sa + 1, sa + n + 1, [&](int x, int y){
			return rk[x] == rk[y] ? rk[x + l] < rk[y + l] : rk[x] < rk[y];
		});
		static int rkbu[N << 1];
		memcpy(rkbu, rk, sizeof(rk));
		for (int i = 1, idx = 0; i <= n; i++)
		{
			if (rkbu[sa[i]] != rkbu[sa[i - 1]]
			 || rkbu[sa[i] + l] !=rkbu[sa[i - 1] + l]
			) idx++;
			rk[sa[i]] = idx;
		}
	}
	for (int i = 1; i <= n; i++)
		printf("%d ", sa[i]);
	return 0;
}

而这是基数排序的 $O(N \log N)$ 代码，只能 $63$ 分，TLE $3$ 个，MLE $1$ 个：

#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <numeric>
#include <iostream>
#include <algorithm>
using namespace std;

typedef pair<int,int> PII;
const int N = 1e6 + 5;
int n; string s;
int sa[N << 1], rk[N << 1];
int rge;
// SA[i]: the ith suffix
// RK[i]: rank of suffix[i]

vector<PII> tlt[N], tlt2[N];
void sortsa(int l)
{
	for (int i = 1; i <= n; i++)
		tlt[rk[i + l]].push_back({i, rk[i]});
	for (int i = 0; i <= rge; i++)
	{
		for (PII t : tlt[i])
			tlt2[t.second].push_back(t);
		tlt[i].clear();
	}
	for (int i = 0, idx = 0; i <= rge; i++)
	{
		for (PII t : tlt2[i])
			sa[++idx] = t.first;
		tlt2[i].clear();
	}
	return;
}

int rkbu[N << 1];
void Disc(int l)
{
	memcpy(rkbu, rk, sizeof(rk));
	rge = 0;
	for (int i = 1; i <= n; i++)
	{
		if (rkbu[sa[i]] != rkbu[sa[i - 1]]
		 || rkbu[sa[i] + l] !=rkbu[sa[i - 1] + l]
		) rge++;
		rk[sa[i]] = rge;
	}
	return;
}

int main()
{
	cin >> s; n = s.length();
	iota(sa + 1, sa + n + 1, 1);
	for (int i = 1; i <= n; i++)
		rk[i] = s[i - 1];
	sort(sa + 1, sa + n + 1, [&](int x, int y){
		return rk[x] == rk[y] ? rk[x + 1] < rk[y + 1] : rk[x] < rk[y];
	});
	Disc(1);
	for (int l = 2; l < n; l <<= 1)
	{
		sortsa(l);
		Disc(l);
	}
	for (int i = 1; i <= n; i++)
		printf("%d ", sa[i]);
	return 0;
}

话说基数排序常数那么大吗？少了一个 $\log$ 反而跑不过了？还是我的写法哪里有问题？请大佬指教！