和bzoj4059: [Cerc2012]Non-boring sequences非常相似
Description
一棵Factor-Free Tree是指一棵有根二叉树,每个点包含一个正整数权值,且每个点的权值都与其所有祖先的权值互质。
二叉树中序遍历是指按照左子树-根-右子树的顺序递归遍历二叉树,将每个点的权值依次写下来得到的序列。
给定一个序列a_1,a_2,...,a_n,请判断它是不是可能是某棵Factor-Free Tree的中序遍历序列,如果是的话请给出例子。
![](https://www.lydsy.com/JudgeOnline/upload/201803/1(1).jpg)
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$,它所能影响到的区间是连续的,即非法之后不会再次合法。
不要忘记左右横跳。
1 #include<bits/stdc++.h> 2 #define REG register int 3 const int maxn = 1000035; 4 const int maxNum = 10000035; 5 6 int n,mx,a[maxn],fa[maxn]; 7 int pr[maxn],res[maxNum],pre[maxn],nxt[maxn],lst[maxNum]; 8 std::bitset<maxNum> vis; 9 10 inline char nc(){ 11 static char buf[100000],*p1=buf,*p2=buf; 12 return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; 13 } 14 #define getchar nc 15 int read() 16 { 17 char ch = getchar(); 18 int num = 0, fl = 1; 19 for (; !isdigit(ch); ch=getchar()) 20 if (ch=='-') fl = -1; 21 for (; isdigit(ch); ch=getchar()) 22 num = (num<<1)+(num<<3)+ch-48; 23 return num*fl; 24 } 25 void write(int x){if (x/10) write(x/10);putchar(x%10+'0');} 26 void makePrime(int Top) 27 { 28 for (int i=2; i<=Top; i++) 29 { 30 if (!vis[i]) res[i] = i, pr[++pr[0]] = i; 31 for (int j=1; j<=pr[0]&&1ll*pr[j]*i<=Top; j++) 32 { 33 vis[i*pr[j]] = 1, res[i*pr[j]] = pr[j]; 34 if (i%pr[j]==0) break; 35 } 36 } 37 } 38 bool merge(int l, int r, int fat) 39 { 40 if (l > r) return 1; 41 int L = l, R = r; 42 while (L <= R) 43 { 44 if (pre[L] < l&&nxt[L] > r){ 45 fa[L] = fat; 46 return merge(l, L-1, L)&&merge(L+1, r, L); 47 } 48 if (pre[R] < l&&nxt[R] > r){ 49 fa[R] = fat; 50 return merge(l, R-1, R)&&merge(R+1, r, R); 51 } 52 L++, R--; 53 } 54 return 0; 55 } 56 int main() 57 { 58 n = read(); 59 for (REG i=1; i<=n; i++) a[i] = read(), mx = a[i]>mx?a[i]:mx; 60 makePrime(mx); 61 for (REG i=1; i<=n; i++) 62 { 63 REG num = a[i], tmp = 0, div; 64 while (num!=1) 65 { 66 div = res[num]; 67 if (lst[div] > tmp) tmp = lst[div]; 68 lst[div] = i; 69 while (num%div==0) num /= div; 70 } 71 pre[i] = tmp; 72 } 73 for (REG i=1; i<=mx; i++) lst[i] = n+1; 74 for (REG i=n; i; i--) 75 { 76 REG num = a[i], tmp = n+1, div; 77 while (num!=1) 78 { 79 div = res[num]; 80 if (lst[div] < tmp) tmp = lst[div]; 81 lst[div] = i; 82 while (num%div==0) num /= div; 83 } 84 nxt[i] = tmp; 85 } 86 if (merge(1, n, 0)){ 87 for (REG i=1; i<=n; i++) 88 write(fa[i]), putchar(i!=n?' ':' '); 89 }else puts("impossible"); 90 return 0; 91 }
END