也可以不转换将翻译方向：只要不超过一圈，每次都贪心地向前翻译到语义差距尽量大的单词显然是最优的。

考虑断环成链后分块，逐步将单词环重复一遍拼接在链末，一边拼接一边求解。对每个元素维护它跳出当前块的翻译次数和落点，在每个单词出现在链末时求解答案，这样就不会超过一圈了。

最终的时间复杂度为 $O(Tn \sqrt n)$，空间复杂度为 $O(n)$，进一步用 LCT 替换分块可以做到 $O(Tn \log n)$ 的优秀时间复杂度。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int nxt[MAXN], jmp[MAXN], stp[MAXN]; int tag[MAXN];
int blk[MAXN], bl[MAXN], br[MAXN];
void rebuild(int x) {
	for (int i = br[x]; i >= bl[x]; i--) {
		if (nxt[i] < i || nxt[i] > br[x]) jmp[i] = nxt[i], stp[i] = 1;
		else jmp[i] = jmp[nxt[i]], stp[i] = stp[nxt[i]] + 1;
	}
}
void pushdown(int x) {
	if (tag[x] != -1) {
		for (int i = bl[x]; i <= br[x]; i++) nxt[i] = tag[x];
		tag[x] = -1; rebuild(x);
	}
}
int a[MAXN], lat[MAXN], buc[MAXN];
namespace sgt {
	int f[MAXN << 2];
	void build(int rt, int l, int r) {
		f[rt] = -1; if (l == r) return; int mid = (l + r) >> 1;
		build(rt << 1, l, mid); build(rt << 1 | 1, mid + 1, r);
	}
	void modify(int rt, int l, int r, int x, int y, int w) {
		if (x > y) return; if (x <= l && r <= y) return f[rt] = max(f[rt], w), void();
		int mid = (l + r) >> 1;
		if (x <= mid) modify(rt << 1, l, mid, x, y, w);
		if (y > mid) modify(rt << 1 | 1, mid + 1, r, x, y, w);
	}
	void push(int rt, int l, int r) {
		if (l == r) return nxt[l] = f[rt], void(); int mid = (l + r) >> 1;
		f[rt << 1] = max(f[rt << 1], f[rt]);
		f[rt << 1 | 1] = max(f[rt << 1 | 1], f[rt]);
		push(rt << 1, l, mid); push(rt << 1 | 1, mid + 1, r);
	}
}
int main() {
	freopen("translation.in", "r", stdin); freopen("translation.out", "w", stdout);
	int t; scanf("%d", &t); while (t--) {
		int n; scanf("%d", &n);
		int b = sqrt(n);
		int nb = (n + b - 1) / b;
		for (int i = 1; i <= n; i++) tag[i] = -1;
		for (int i = 1; i <= nb; i++) {
			bl[i] = b * (i - 1) + 1; br[i] = min(b * i, n);
			for (int _ = bl[i]; _ <= br[i]; _++) blk[_] = i;
			rebuild(i);
		}
		for (int i = 1; i <= n; i++) scanf("%d", &a[i]), buc[a[i]] = i;
		for (int i = 1; i <= n; i++) lat[i] = buc[a[i]], buc[a[i]] = i;

		sgt::build(1, 1, n);
		for (int i = 2; i <= n; i++) {
			int p = lat[i] >= i ? n : lat[i];
			p = p % n + 1;
			sgt::modify(1, 1, n, p, i - 1, i);
		}
		sgt::push(1, 1, n);
		for (int i = 1; i <= nb; i++) rebuild(i);

		for (int i = 1; i <= n; i++) {
			int tmp = tag[blk[i]] != -1 ? tag[blk[i]] : nxt[i];
			int j = lat[i]; j = j % n + 1;
			if (j < i) {
				int bi = blk[i], bj = blk[j];
				if (bi == bj) {
					pushdown(bi); for (int _ = j; _ < i; _++) nxt[_] = i;
					nxt[i] = -1; rebuild(bi);
				}
				else {
					pushdown(bi); pushdown(bj);
					for (int _ = j; _ <= br[bj]; _++) nxt[_] = i;
					for (int _ = bj + 1; _ < bi; _++) tag[_] = i;
					for (int _ = bl[bi]; _ < i; _++) nxt[_] = i;
					nxt[i] = -1; rebuild(bi); rebuild(bj);
				}
			}
			else {
				int bi = blk[i], bj = blk[j];
				if (bi == bj) {
					pushdown(bi);
					for (int _ = j; _ <= br[bj]; _++) nxt[_] = i;
					for (int _ = bj + 1; _ <= nb; _++) tag[_] = i;
					for (int _ = 1; _ < bi; _++) tag[_] = i;
					for (int _ = bl[bi]; _ < i; _++) nxt[_] = i;
					nxt[i] = -1; rebuild(bi);
				}
				else {
					pushdown(bi); pushdown(bj);
					for (int _ = j; _ <= br[bj]; _++) nxt[_] = i;
					for (int _ = bj + 1; _ <= nb; _++) tag[_] = i;
					for (int _ = 1; _ < bi; _++) tag[_] = i;
					for (int _ = bl[bi]; _ < i; _++) nxt[_] = i;
					nxt[i] = -1; rebuild(bi); rebuild(bj);
				}
			}
			int step = 0;
			while (tmp != -1) {
				if (tag[blk[tmp]] != -1) step++, tmp = tag[blk[tmp]];
				else step += stp[tmp], tmp = jmp[tmp];
			}
			printf("%d%c", step, " \n"[i == n]);
		}
	}
}

有向环上 $a \to b$ 经过的最小边数被定义为单词 $a$ 和单词 $b$ 之间的语义偏差度 —— 由于翻译家并不像 OI 选手那样具备逆向思维，因此单词 $a$ 和单词 $b$ 之间的语义偏差度不一定等于单词 $b$ 和单词 $a$ 之间的语义偏差度。

考虑逆向思维，从单词 $i$ 沿着与题目描述相反的方向回译到单词 $i$。

（在下面的讨论中，我们默认单词 $i$ 可以翻译到单词 $i$ 本身，因为这显然不影响答案 —— 这只会增加翻译次数，而不能推进翻译进度，没人愿意这么做。）

于是我们惊喜地发现：

• 单词 $i$ 反向翻译一次能翻译到的单词恰好在环上构成一个半开半闭区间，其中闭区间的端点是单词 $i$ 本身，开区间的端点是距离单词 $i$ 反向距离最近的同语言单词 $j$。
• 在此基础上，如果我们再进行一次反向翻译，那么能翻译到的单词是所有「上一次能翻译到的单词」这次能翻译到的单词的并集。因为所有区间都是闭区间点为本身的半开半闭区间，所以这些区间的并集仍然是半开半闭区间，其中开区间的端点是所有「子区间内开区间的端点」中距离单词 $i$ 反向最远的单词。
• 随着翻译次数的增加，当这个反向最远的单词从单词 $i$ 开始绕着环反向跑了一圈又穿过单词 $i$ 来到它后面时，我们就求出了回译单词 $i$ 所需的最小翻译次数 —— 它就是使得这一事件发生所需的最小翻译次数。

直接二分每个答案并用 ST 表和（不属于 ST 表的）倍增实现对那个反向最远的单词的高效查询即可。

最终的时间复杂度为 $O(Tn \log^2 n)$，空间复杂度为 $O(n \log^2 n)$，瓶颈均在预处理部分。

（实际上，我们也可以套用 $O(n)-O(1)$ RMQ 把时间复杂度降到 $O(Tn \log n)$，空间复杂度降到 $O(n \log n)$，但是意义不大。）

#include <bits/stdc++.h>
using namespace std;
const int N = 2 * 1e5 + 12;
const int D = 17;
const int W = 18;
int a[N];
int b[N];
int logs[N];
int st[W][W][N];
void setst(int n, int x)
{
	for (int i = 1; i <= D; i++)
		for (int j = 1; j <= n - (1 << (i - 1)); j++)
			st[x][i][j] = min(st[x][i - 1][j + (1 << (i - 1))], st[x][i - 1][j]);
}
int getst(int l, int r, int x)
{
	int y = logs[r - l + 1];
	return min(st[x][y][l], st[x][y][r - (1 << y) + 1]);
}
int main()
{
	freopen("translation.in", "r", stdin);
	freopen("translation.out", "w", stdout);
	for (int i = 1; i <= D; i++)
		logs[1 << i] = i;
	for (int i = 3; i <= N - 1; i++)
		if (!logs[i]) logs[i] = logs[i - 1];
	int T;
	scanf("%d", &T);
	while (T--)
	{
		int n;
		scanf("%d", &n);
		int m = (n << 1);
		memset(st, 0x7f, sizeof st);
		for (int i = 1; i <= n; i++)
		{
			scanf("%d", &a[i]);
			a[i + n] = a[i];
			b[a[i]] = 0;
		}
		for (int i = 1; i <= m; i++)
		{
			st[0][0][i] = b[a[i]] + 1;
			b[a[i]] = i;
		}
		for (int i = 0; i <= D; i++)
			st[i][0][1] = 1;
		setst(m, 0);
		for (int i = 1; i <= D; i++)
		{
			for (int j = 2; j <= m; j++)
				st[i][0][j] = getst(st[i - 1][0][j], j, i - 1);
			setst(m, i);
		}
		for (int i = n + 1; i <= m; i++)
		{
			int ans = 1;
			int cur = i;
			for (int j = D; j >= 0; j--)
			{
				int to = getst(cur, i, j);
				if (to > i - n)
				{
					ans += (1 << j);
					cur = to;
				}
			}
			printf("%d", ans);
			if (i < m) putchar(' ');
		}
		puts("");
	}
	return 0;
}