【启发式分裂】BZOJ5200 [NWERC2017]Factor-Free Tree

题面在这里

​

考虑一个子树（序列），\(i\)能作为根当且仅当区间内所有数与\(a_i\)互质

可以预处理出左边第一个与\(a_i\)不互质的位置\(L_i\)和右边第一个与\(a_i\)不互质的位置\(R_i\)

具体方法：枚举每个数的质因子，取所有质因子出现位置最大的

还有一个结论：对于任意区间，更靠两端的点满足与整个区间互质却不能作为根，则里面的点一定也不能

然后就可以启发式分裂找每个子树的根啦

启发式分裂：由于指针移动次数为分裂出较小的那个区间长度，可以看作时启发式合并的逆过程

​

示例程序：

#include<cstdio>
#include<algorithm>
using namespace std;
inline char nc(){
	static char buf[100000],*l=buf,*r=buf;
	return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
inline int red(){
	int res=0,f=1;char ch=nc();
	while (ch<'0'||'9'<ch) {if (ch=='-') f=-f;ch=nc();}
	while ('0'<=ch&&ch<='9') res=res*10+ch-48,ch=nc();
	return res*f;
}
inline void put(int x){
	static int stk[11];stk[0]=0;
	do stk[++stk[0]]=x%10,x/=10; while (x);
	while (stk[0]) putchar(stk[stk[0]--]+48);
}

const int maxn=1000005,maxa=10000005;
int n,a[maxn],L[maxn],R[maxn];
int gcd(int x,int y) {return y==0?x:gcd(y,x%y);}
int p[maxa],pre[maxa],lst[maxa];
bool vis[maxa];
void makep(int n){
	for (int i=2;i<=n;i++){
		if (!vis[i]) p[++p[0]]=i,pre[i]=i;
		for (int j=1;j<=p[0]&&i*p[j]<=n;j++){
			vis[i*p[j]]=1; pre[i*p[j]]=p[j];
			if (i%p[j]==0) break;
		}
	}
}
int fa[maxn];
bool solve(int l,int r,int f){
	if (l>r) return 1;
	for (int i=l,j=r;i<=j;i++,j--){
		if (L[i]<l&&r<R[i]){
			fa[i]=f;return solve(l,i-1,i)&&solve(i+1,r,i);
		}
		if (L[j]<l&&r<R[j]){
			fa[j]=f;return solve(l,j-1,j)&&solve(j+1,r,j);
		}
	}
	return 0;
}
int main(){
	n=red();
	for (int i=1;i<=n;i++) a[i]=red();
	makep(10000000);
	for (int i=1;i<=n;i++){
		int x=a[i];
		while (x!=1){
			int p=pre[x];
			L[i]=max(L[i],lst[p]);
			lst[p]=i;
			while (x%p==0) x/=p;
		}
	}
	for (int i=1;i<=p[0];i++) lst[p[i]]=n+1;
	for (int i=n;i;i--){
		int x=a[i];R[i]=n+1;
		while (x!=1){
			int p=pre[x];
			R[i]=min(R[i],lst[p]);
			lst[p]=i;
			while (x%p==0) x/=p;
		}
	}
	if (solve(1,n,0))
	 for (int i=1;i<=n;i++) put(fa[i]),putchar(' ');
	else puts("impossible");
	return 0;
}