题目大意

有个二叉树，满足每个点跟它的所有祖先互质。

给出二叉树的中序遍历的点权，还原一种可能的方案。

---

思考历程

首先想到的当然是找到一个跟全部互质的点作为根，然后左右两边递归下去处理……

然而考虑到和全部互质的点可能有很多个，这样的做法可能会退化到很多……

先预处理了个\(L_i\)和\(R_i\)表示\(i\)左边第一个和\(i\)不互质的位置和右边第一个和\(i\)不互质的点。

这个东西怎么预处理就不用说吧……

（我估计正解肯定也要处理这东西）

然后就是乱搞……

想不出正解，于是打了个\(O(n^3)\)的区间\(DP\)……

在时间复杂度上似乎连一分都没有……

---

正解

在比赛的后期我发现了一个很有用的结论：

如果一个区间可以成为一棵合法的子树，那么这个区间的所有子区间都可以成为一棵合法的子树。

这个是比较显然的，原因是什么自己脑补……我还拍过了几个数据……

（然而我在比赛的最后都不知道该怎么用……）

然后YMQ告诉我一个性质：如果一个区间中选择任意一个跟其它所有数互质的点，然后递归下去处理，处理完之后发现不行，那么选择其它的和所有数互质的点处理也不行。

回去一个晚上想到了证明：

上面的那个结论反过来就是说，如果一个区间不能成为一棵合法的子树，那么所有包含它的区间都不能成为一棵合法的子树。

假设这个区间是\([l,r]\)，其中的一个和其它所有数互质的点为\(x\)。

如果处理之后不行，则必然是\([l,x-1]\)或\([x+1,r]\)不行。

所以包含\([l,x-1]\)或\([x+1,r]\)的所有区间都不行啊……这区间也自然包括\([l,r]\)

接下来就有一种比较简单又自然的做法：随便找一个和其它数互质的点，作为子树的根，左右递归下去。显然时间复杂度是\(O(n^2)\)的。

回去睡了一个晚上，想到了\(O(n\lg n)\)的做法：从左右两边同时寻找，找到之后就递归。这样看上去似乎没有什么优化，实际上，相当于寻找的时间复杂度小于等于当前区间长度的一半，然后继续递归。

可以看做这个小区间递归了，大区间继续找，那最后就是大区间在区间长度的时间复杂度内，分成了若干个长度小于等于总长的一半的小区间递归下去。

所以就只有\(O(\lg n)\)层。

然后我发现这就是题解做法之一……另一种做法比较强大，在预处理之后就是\(O(n)\)的（我最后就是打了这种做法）。

用一个栈来维护最右边的一条链，栈顶就是深度最大的那个点。

设栈顶为\(b\)，栈顶下面的那一个为\(a\)。

考虑增量法，每次新增一个\(i\)进去。

然后看看能不能通过旋转使得答案更优。

能够旋转的必要条件是\(L_i< a+1\)（因为\(a+1\)是先前\(b\)子树区间的左端点）

使得更优的必要条件是\(R_i\geq R_b\)，这就意味着右儿子可以添加更多的点，当然更优。

如果可以成功旋转就一直试着旋转下去，直到变成根或者不优。

搞完之后，判断一下是否\(i<R_b\)。如果不是，那就impossible。

按照我的理解，由于前面的策略已经保证了向右延伸得最多，所以如果依然不能容纳\(i\)，那么证明肯定不合法。

这样一直建下去就行了。

---

代码

由于oj出锅了，所以我也不知道这个代码对不对……

using namespace std;#include 
    
     #include 
     
      #include 
      
       #include 
       
        //#include 
        
         #define N 1000010#define maxA 10000000inline int input(){    char ch=getchar();    while (ch<'0' || ch>'9')        ch=getchar();    int x=0;    do{        x=x*10+ch-'0';        ch=getchar();    }    while ('0'<=ch && ch<='9');    return x;}int n,a[N];int p[maxA],np;int mnp[maxA+10];int lst[maxA+10];int L[N],R[N];int st[N],top;int fa[N],son[N][2];int main(){//  freopen("in.txt","r",stdin);    freopen("tree.in","r",stdin);    freopen("tree.out","w",stdout);    for (int i=2;i<=maxA;++i){        if (!mnp[i]){            p[++np]=i;            mnp[i]=i;        }        for (int j=1;j<=np && i*p[j]<=maxA;++j){            mnp[i*p[j]]=p[j];            if (!(i%p[j]))                break;        }    }    n=input();    for (int i=1;i<=n;++i)        a[i]=input();    for (int i=1;i<=n;++i){        int t=a[i];        while (t!=1){            int x=mnp[t];            L[i]=max(L[i],lst[x]);            lst[x]=i;            while (!(t%x))                t/=x;        }    }    for (int i=1;i<=maxA;++i)        lst[i]=n+1;    for (int i=n;i>=1;--i){        R[i]=n+1;        int t=a[i];        while (t!=1){            int x=mnp[t];            R[i]=min(R[i],lst[x]);            lst[x]=i;            while (!(t%x))                t/=x;        }    }    st[top=1]=1;    for (int i=2;i<=n;++i){        if (R[st[top]]<=i){            printf("impossible\n");            return 0;        }        while (top && L[i]
         
          =R[st[top]]){ son[st[top]][1]=son[i][0]; son[i][0]=st[top]; top--; } son[st[top]][1]=i; st[++top]=i; } for (int i=1;i<=n;++i) fa[son[i][0]]=fa[son[i][1]]=i; for (int i=1;i<=n;++i) printf("%d ",fa[i]); return 0;}
         
        
       
      
     
    

---

总结

前面的那种分治做法应该是一个套路。

也就是\(T(n)=T(x)+T(n-x)+min(x,n-x)\)这种形式的分治，它的时间复杂度也是\(O(n\lg n)\)的。

其实我发现后面的这种做法有点像笛卡尔树……

这启示我们在建二叉树的过程中可以试试用栈维护最右边的那条链。