题意
已知一个长度为n的序列a1,a2,...,an。
对于每个1<=i<=n，找到最小的非负整数p满足 对于任意的j, aj < = ai + p - sqrt(abs(i-j))
题解
决策单调性是个好东西
等学会了再滚回来填坑
1 //minamoto 2 #include<iostream> 3 #include<cstdio> 4 #include<cmath> 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<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;} 9 inline int read(){ 10 #define num ch-'0' 11 char ch;bool flag=0;int res; 12 while(!isdigit(ch=getc())) 13 (ch=='-')&&(flag=true); 14 for(res=num;isdigit(ch=getc());res=res*10+num); 15 (flag)&&(res=-res); 16 #undef num 17 return res; 18 } 19 char sr[1<<21],z[20];int C=-1,Z; 20 inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;} 21 inline void print(int x){ 22 if(C>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]=' '; 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<t&&k[t-1]>=bound(q[t],i)) --t; 42 k[t]=bound(q[t],i),q[++t]=i; 43 while(h<t&&k[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 }