[题解] CFgym101623F Factor-Free Tree

Factor-Free Tree

当一棵二叉树中的每个节点的权值都与它所有祖先的权值互质时，我们称它为 factor-free tree。
给你一棵按照中序遍历的顺序的权值序列 \(a\)，求这个序列是否对应这一棵 factor-free tree。
如果是就输出每个节点的父亲。
\(n \le 10^5, a_i \le 10^7\)。

考虑怎么找到一棵 factor-free tree：先找到一个与其他所有数都互质的数当根，然后再递归左右两边。可以注意到如果有多个数互质选哪个都是无所谓的，因为最后总会将序列划分成相同的形态。

为了做这个东西，首先要能快速判断一个数是否与这个区间内的其他数互质。这个可以考虑对每个位置预处理出 \(L_i\) 和 \(R_i\) 表示这个数左右两边第一个不和它互质的数，然后对于一个区间 \([l, r]\)，判断区间内的数手否和它互质就是判断是否有 \(L_i \le l, r \le R_i\)。

然后可以发现这个东西最慢是 \(O(n^2)\) 的，所以还要继续优化。

对于这个递归过程，想要让它的时间复杂度正确，需要要求每次遍历的时间复杂度和 \([l, mid]\) 和 \([mid, r]\) 中较短的区间的长度相关，这样就是 \(O(n \log n)\) 的。所以考虑怎么让每次遍历的时间复杂度变成 \(O(\min(mid - l, r - mid))\)。

我们可以从 \(l\) 和从 \(r\) 同时找，这样就是 \(O(\min(mid - l, r - mid))\) 的了。

时间复杂度 \(O(n \log n)\)。

constexpr int MAXN = 1e6 + 9, MAXV = 1e7 + 9, MAXP = 7e5;
int n, a[MAXN], mnp[MAXV], id[MAXV], L[MAXN], R[MAXN],
	fa[MAXN];
vector<int> pri, pos[MAXP];
bitset<MAXV> vis;

void sieve(int N) {
	vis.reset();
	for (int i = 2; i <= N; i ++) {
		if (!vis[i]) {
			id[i] = pri.size();
			pri.emplace_back(i);
			mnp[i] = i;
		}
		for (auto j : pri) {
			if (1ll * i * j > N) break;
			vis[i * j] = 1, mnp[i * j] = j;
			if (i % j == 0) break;
		}
	}
	return;
}

bool Solve(int l, int r, int rt) {
	if (l > r) return true;
	int pl = l, pr = r, mid = 0;
	auto check = [&](int x) { return L[x] <= l && r <= R[x]; };
	while (pl <= pr) {
		if (check(pl)) { mid = pl; break; }
		if (check(pr)) { mid = pr; break; }
		pl ++, pr --;
	}
	if (mid) { fa[mid] = rt; return Solve(l, mid - 1, mid) && Solve(mid + 1, r, mid); }
	return false;
}

void slv() {
	n = Read<int>(), sieve(1e7);
	for (int i = 1; i <= n; i ++) a[i] = Read<int>();
	auto Divide = [&](int p) {
		int t = a[p];
		while (t != 1) {
			pos[id[mnp[t]]].emplace_back(p);
			t /= mnp[t];
		}
		return;
	};
	for (int i = 1; i <= n; i ++) Divide(i), L[i] = 0, R[i] = n + 1;
	for (int i = 0; i < pri.size(); i ++) {
		pos[i].emplace_back(0), pos[i].emplace_back(n + 1);
		sort(pos[i].begin(), pos[i].end());
		pos[i].erase(unique(pos[i].begin(), pos[i].end()), pos[i].end());
		for (int j = 1; j + 1 < pos[i].size(); j ++)
			cmax(L[pos[i][j]], pos[i][j - 1] + 1),
			cmin(R[pos[i][j]], pos[i][j + 1] - 1);
	}
	if (!Solve(1, n, 0)) { Puts("impossible"); return; }
	for (int i = 1; i <= n; i ++) Write(fa[i], ' ');
	return;
}