Description
一棵Factor-Free Tree是指一棵有根二叉树，每个点包含一个正整数权值，且每个点的权值都与其所有祖先的权值互质。
二叉树中序遍历是指按照左子树-根-右子树的顺序递归遍历二叉树，将每个点的权值依次写下来得到的序列。
给定一个序列a_1,a_2,...,a_n，请判断它是不是可能是某棵Factor-Free Tree的中序遍历序列，如果是的话请给出例子。
Input
第一行包含一个正整数n(1<=n<=1000000)。
第二行包含n个正整数a_1,a_2,...,a_n(1<=a_i<=10^7)，表示节点编号为1到n的每个点的权值。
Output
若不是，输出impossible
否则输出一行n个整数，依次表示序列每一项代表的节点在树中的父亲节点，若是根节点则输出0。
若有多组解，输出任意一组。
题目分析
暴力做法就是在$[l,r]$内找到一个$rt$满足$\forall (a[rt],a[i])=1 \, rt≠i$，并递归做下去。这样复杂度是$O(n^3)$的。
考虑如何利用重复信息。互质看上去不好处理，但其实不过是一种二元关系而已。那么固定一个量，即处理出对于$a_i$，与其互质的数的最大区间$[l,r]$。
转成这一步，就可以用bz4059的“启发式拆分”方法去做了。
总结一下：“启发式拆分”这种方法适用于一类可拆分的、连续的区间问题。“可拆分”是指只需要在区间内寻找一个断点，并且拆分之后就不会再次合并；“连续”意味着对于固定的$i$，它所能影响到的区间是连续的，即非法之后不会再次合法。
不要忘记左右横跳。
#include<bits/stdc++.h>
#define REG register int
const int maxn = ;
const int maxNum = ; int n,mx,a[maxn],fa[maxn];
int pr[maxn],res[maxNum],pre[maxn],nxt[maxn],lst[maxNum];
std::bitset<maxNum> vis; inline char nc(){
static char buf[],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,,,stdin),p1==p2)?EOF:*p1++;
}
#define getchar nc
int read()
{
char ch = getchar();
int num = , fl = ;
for (; !isdigit(ch); ch=getchar())
if (ch=='-') fl = -;
for (; isdigit(ch); ch=getchar())
num = (num<<)+(num<<)+ch-;
return num*fl;
}
void write(int x){if (x/) write(x/);putchar(x%+'');}
void makePrime(int Top)
{
for (int i=; i<=Top; i++)
{
if (!vis[i]) res[i] = i, pr[++pr[]] = i;
for (int j=; j<=pr[]&&1ll*pr[j]*i<=Top; j++)
{
vis[i*pr[j]] = , res[i*pr[j]] = pr[j];
if (i%pr[j]==) break;
}
}
}
bool merge(int l, int r, int fat)
{
if (l > r) return ;
int L = l, R = r;
while (L <= R)
{
if (pre[L] < l&&nxt[L] > r){
fa[L] = fat;
return merge(l, L-, L)&&merge(L+, r, L);
}
if (pre[R] < l&&nxt[R] > r){
fa[R] = fat;
return merge(l, R-, R)&&merge(R+, r, R);
}
L++, R--;
}
return ;
}
int main()
{
n = read();
for (REG i=; i<=n; i++) a[i] = read(), mx = a[i]>mx?a[i]:mx;
makePrime(mx);
for (REG i=; i<=n; i++)
{
REG num = a[i], tmp = , div;
while (num!=)
{
div = res[num];
if (lst[div] > tmp) tmp = lst[div];
lst[div] = i;
while (num%div==) num /= div;
}
pre[i] = tmp;
}
for (REG i=; i<=mx; i++) lst[i] = n+;
for (REG i=n; i; i--)
{
REG num = a[i], tmp = n+, div;
while (num!=)
{
div = res[num];
if (lst[div] < tmp) tmp = lst[div];
lst[div] = i;
while (num%div==) num /= div;
}
nxt[i] = tmp;
}
if (merge(, n, )){
for (REG i=; i<=n; i++)
write(fa[i]), putchar(i!=n?' ':'\n');
}else puts("impossible");
return ;
}
END