洛谷P3515 [POI2011]Lightning Conductor（决策单调性）

题意

已知一个长度为n的序列a1,a2,...,an。

对于每个1<=i<=n，找到最小的非负整数p满足 对于任意的j, aj < = ai + p - sqrt(abs(i-j))

题解

决策单调性是个好东西

等学会了再滚回来填坑

 //minamoto

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 using namespace std;

 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

 char buf[<<],*p1=buf,*p2=buf;

 template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,:;}

 inline int read(){

     #define num ch-'0'

     char ch;bool flag=;int res;

     while(!isdigit(ch=getc()))

     (ch=='-')&&(flag=true);

     for(res=num;isdigit(ch=getc());res=res*+num);

     (flag)&&(res=-res);

     #undef num

     return res;

 }

 char sr[<<],z[];int C=-,Z;

 inline void Ot(){fwrite(sr,,C+,stdout),C=-;}

 inline void print(int x){

     if(C><<)Ot();if(x<)sr[++C]=,x=-x;

     while(z[++Z]=x%+,x/=);

     while(sr[++C]=z[Z],--Z);sr[++C]='\n';

 }

 const int N=5e5+;

 int n,q[N],k[N],a[N];

 double p[N];

 inline double calc(int i,int j){return a[j]+sqrt(i-j);}

 inline int bound(int x,int y){

     int l=,r=n,mid,res=r+;

     while(l<=r){

         mid=l+r>>;

         if(calc(mid,x)<=calc(mid,y)) res=mid,r=mid-;

         else l=mid+;

     }

     return res;

 }

 void work(){

     for(int i=,h=,t=;i<=n;++i){

         while(h<t&&k[t-]>=bound(q[t],i)) --t;

         k[t]=bound(q[t],i),q[++t]=i;

         while(h<t&&k[h]<=i) ++h;

         cmax(p[i],calc(i,q[h]));

     }

 }

 int main(){

     //freopen("testdata.in","r",stdin);

     n=read();

     for(int i=;i<=n;++i) a[i]=read();

     work();

     for(int i=;i<=n+-i;++i)

     swap(a[i],a[n-i+]),swap(p[i],p[n-i+]);

     work();

     for(int i=n;i;--i) print(ceil(p[i])-a[i]);

     Ot();

     return ;

 }