F - Factor-Free Tree Gym - 101623F（质数，中序遍历，区间）

本文主要是介绍F - Factor-Free Tree Gym - 101623F（质数，中序遍历，区间），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

题意：
给出一颗树的中序遍历，要求还原这棵树使得每一个节点的值和其祖先互质

思路：
参考claris博客题解。

对每个数质因子分解，算出每个数左边的第一个不互质位置，右边第一个不互质位置。
维护每个点对应的区间，也就是其对应子树。
将这些区间放在栈里面，如果当前区间包含栈顶区间，那么弹出栈顶。
则按照中序遍历左中右的顺序，最后一个弹出的区间为当前点的左子树，当前栈顶区间为节点父子节点。

则无解情况为栈顶区间不包含当前区间，此时父节点不能包括子节点。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;const int INF = 0x3f3f3f3f;
const int maxn = 1e6 + 7;
const int MAXN = 1e7 + 7;
struct STK {int l,r;int id;
}stk[maxn];int n;
int fa[maxn];
int L[maxn],R[maxn],a[maxn];
int pre[MAXN],p[MAXN],v[MAXN],tot;void init() {for(int i = 2;i < MAXN;i++) {if(!v[i]) {p[++tot] = i;v[i] = i;}for(int j = 1;j <= tot && 1ll * i * p[j] < MAXN;j++) {v[i * p[j]] = p[j];if(i % p[j] == 0) break;}}
}void Pre() {for(int i = 1;i <= n;i++) {int x = a[i];while(x > 1) {L[i] = max(L[i],pre[v[x]]);x /= v[x];}L[i]++;x = a[i];while(x > 1) {pre[v[x]] = i;x /= v[x];}}for(int i = 2;i < MAXN;i++) pre[i] = n + 1;for(int i = n;i >= 1;i--) {R[i] = n + 1;int x = a[i];while(x > 1) {R[i] = min(R[i],pre[v[x]]);x /= v[x];}R[i]--;x = a[i];while(x > 1) {pre[v[x]] = i;x /= v[x];}}
}int main() {init();scanf("%d",&n);for(int i = 1;i <= n;i++) scanf("%d",&a[i]);Pre();int top = 0;stk[0].l = 0;stk[0].r = INF;for(int i = 1;i <= n;i++) {int left = i;stk[top + 1].id = 0;while(L[i] <= stk[top].l && stk[top].r <= R[i]) {left = min(left,stk[top].l);top--;}fa[stk[top + 1].id] = i;fa[i] = stk[top].id;stk[++top].l = left;stk[top].id = i;stk[top].r = min(R[i],stk[top - 1].r);if(stk[top - 1].r < i) {printf("impossible\n");return 0;}}for(int i = 1;i <= n;i++) {printf("%d ",fa[i]);}return 0;
}