#include #include #include #define Re register int using namespace std; const int N=5e5+3; int i,j,n,h,t,a[N],Q[N],Poi[N]; double p[N],sqr[N]; inline void in(Re &x){ int f=0;x=0;char c=getchar(); while(c<'0'||c>'9')f|=c=='-',c=getchar(); while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar(); x=f?-x:x; } inline double Y(Re i,Re j){return a[j]+sqr[i-j];} inline int find_Poi(int j1,int j2){// 找到两条直线的交点i Re l=j2,r=n,mid,ans=n+1;// 为了防止两条直线没有交点,预设一个最大边界值 while(l<=r){ mid=l+r>>1; if(Y(mid,j1)<=Y(mid,j2))ans=mid,r=mid-1; // 当前位置i使用直线j1的值小于直线j2的值,说明交点i在当前位置右侧,因此右边界要缩小 else l=mid+1; } return ans; } inline void sakura(){ h=1,t=0; for(i=1;i<=n;++i){ while(h=find_Poi(Q[t],i))--t; Poi[t]=find_Poi(Q[t],i),Q[++t]=i; while(h