题意

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

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

题解

决策单调性是个好东西

等学会了再滚回来填坑

1 //minamoto 2 #include
     
       3 #include
      
        4 #include
       
         5 using namespace std; 6 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 7 char buf[1<<21],*p1=buf,*p2=buf; 8 template
        
         inline bool cmax(T&a,const T&b){
   return a
         
          1<<20)Ot();if(x<0)sr[++C]=45,x=-x;23     while(z[++Z]=x%10+48,x/=10);24     while(sr[++C]=z[Z],--Z);sr[++C]='\n';25 }26 const int N=5e5+5;27 int n,q[N],k[N],a[N];28 double p[N];29 inline double calc(int i,int j){
   return a[j]+sqrt(i-j);}30 inline int bound(int x,int y){31     int l=1,r=n,mid,res=r+1;32     while(l<=r){33         mid=l+r>>1;34         if(calc(mid,x)<=calc(mid,y)) res=mid,r=mid-1;35         else l=mid+1;36     }37     return res;38 }39 void work(){40     for(int i=1,h=1,t=0;i<=n;++i){41         while(h
          
           =bound(q[t],i)) --t;42 k[t]=bound(q[t],i),q[++t]=i;43 while(h
           
            <=i) ++h;44 cmax(p[i],calc(i,q[h]));45 }46 }47 int main(){48 //freopen("testdata.in","r",stdin);49 n=read();50 for(int i=1;i<=n;++i) a[i]=read();51 work();52 for(int i=1;i<=n+1-i;++i)53 swap(a[i],a[n-i+1]),swap(p[i],p[n-i+1]);54 work();55 for(int i=n;i;--i) print(ceil(p[i])-a[i]);56 Ot();57 return 0;58 }