浅谈二分
来自8，17考试模拟24。
本题：
单调凸包。（找凸包方向：联系高考数学线性规划）
弹栈操作是一个个向后弹的。
序列转换为树上。
对于树上结构，只需记录父子关系，即可还原出一整棵树。
因为要可持久化，那么这里的栈也变为了树状。
只需记录在栈里的父亲即可。
甚至不用开一个数组作为栈。
由于单调性，搭配倍增使用，效果更佳。
二分，倍增的一些思考：
浅谈二分，倍增
1、那么普通的数组类型栈由于单调性，且是序列上的连续，可以用二分和倍增快速pop
（这里的二分指l,r,while循环,check(mid) 的二分）
2、既然既可以使用二分，也可以使用倍增，那他们的区别在哪儿？
发现：倍增是学lca时学到的，是用来解决树上问题。可以说他满足单调性，但由于树的特殊性质，无法用二分解决。
因此出现了倍增数组。良好地解决了树上二分祖先的问题。
推论：倍增数组也可以用在比树更简单的序列上。他是二分的强化版。
则二分能解决的问题倍增大多可以解决。
而大多情况下使用mid二分（也可倍增二进制拆分），是因为直接mid，不是固定log,可能会少一点。
而倍增i=20~0是二进制拆分，复杂度固定log,与二分上限相同，随机情况下会慢一点点。
不需要记录一些关系时，倍增的二进制拆分和二分是差不多的。
但是倍增数组提供了很多灵活而多样的功能，使他比单纯二分的适应性、功能性更强。
附：普通二分的倍增写法：（相比麻烦一点）（但是很帅啊）
int l,r;
for(int i,20,0){
if(check(r-(1<<i)))r=(r-(1<<i))
else l=(r-(1<<i))-1
}
本题代码：
#include<bits/stdc++.h>
#define F(i,a,b) for(rg int i=a;i<=b;++i)
#define il inline
#define rg register
#define LL long long
#define pf(a) printf("%d ",a)
#define phn puts("")
using namespace std;
int read();
/*
弹栈操作是一个个向后弹的。
序列转换为树上。
对于树上结构，只需记录父子关系，即可还原出一整棵树。
因为要可持久化，那么这里的栈也变为了树状。
只需记录在栈里的父亲即可。
甚至不用开一个数组作为栈。
由于单调性，搭配倍增使用，效果更佳。
另：1、那么普通的数组类型栈由于单调性，且是序列上的连续，可以用二分和倍增快速pop
（这里的二分指l,r,while循环,check(mid) 的二分）
2、既然既可以使用二分，也可以使用倍增，那他们的区别在哪儿？
发现：倍增是学lca时学到的，是用来解决树上问题。可以说他满足单调性，但由于树的特殊性质，无法用二分解决。
因此出现了倍增数组。良好地解决了树上二分祖先的问题。
推论：倍增数组也可以用在比树更简单的序列上。他是二分的强化版。
则二分能解决的问题倍增大多可以解决。
而大多情况下使用mid二分（也可倍增二进制拆分），是因为直接mid，不是固定log,可能会少一点。
而倍增i=20~0是二进制拆分，复杂度固定log,与二分上限相同，随机情况下会慢一点点。
不需要记录一些关系时，倍增的二进制拆分和二分是差不多的。
但是倍增数组提供了很多灵活而多样的功能，使他比单纯二分的适应性、功能性更强。
附：普通二分的倍增写法：
int l,r;
for(int i,20,0){
if(check(r-(1<<i)))r=(r-(1<<i))
else l=(r-(1<<i))-1
}
*/
#define N 500010
int n;
il double min(const double &x,const double &y){return x<y?x:y;}
int f[N];LL c[N];
vector<int>son[N];//要记录1、凸壳倍增祖先。
int las[N<<1][20+2];LL dep[N];
int jud(int k,int j,int i){return (c[i]-c[j])*(dep[j]-dep[k])<=(c[j]-c[k])*(dep[i]-dep[j]);}
void dfs(int x){
dep[x]=dep[f[x]]+1;
int p=f[x];
for(int i=20;i>=0;--i){
if(las[p][i]<2)continue;
int t=las[p][i];
if(jud(las[t][0],t,x))p=t;
}
if(p!=1){
if(jud(las[p][0],p,x))p=las[p][0];
/*
找凸包切线：类似于lca抬根。
要找凸包中最靠前一个不符合条件的点。
然后去判断他的父节点是否符合条件。
因为如果倍增跳过了，会一直斜率(i,j)>(j,k)。
所以要找最后一个(i,j)<=(j,k)的点。
然后判断他的父节点是否符合。
凸包对于1要特判。
*/
}
las[x][0]=p;
F(i,1,20)las[x][i]=las[las[x][i-1]][i-1];
int ting=son[x].size()-1;
F(i,0,ting){
dfs(son[x][i]);
}
}
int main(){
n=read();
F(i,1,n)c[i]=read();
F(i,2,n)f[i]=read(),son[f[i]].push_back(i);
dfs(1);
F(i,2,n){
printf("%.10lf\n",(double)(c[las[i][0]]-c[i])/(dep[i]-dep[las[i][0]]));
}
}
il int read(){
int s=0,f=0;char ch;
while(ch=getchar(),f+=(ch=='-'),!isdigit(ch));
for(;isdigit(ch);s=s*10+(ch^48),ch=getchar());
return f?-s:s;
}
/*
g++ 3.cpp -g
./a.out
8
31516 11930 18726 12481 79550 63015 64275 7608
1 1 2 4 2 4 5
*/
View Code