已知一个长度为n的序列a1,a2,…,an。 对于每个1<=i<=n，找到最小的非负整数p满足对于任意的 j ,aj≤ai p−abs(i−j)−−−−−−−−√
转化一下原式就可以把它变成 p≥aj+abs(i−j)−−−−−−−−√−ai 即对于每一个 i 求p=max(aj abs(i−j)−−−−−−−−√)−ai 因为 y=x√ 这个函数的 Δy=x√−x−1−−−−√ 是递减的（可以求导证明） 于是对于 j<k ，若 aj+abs(i−j)−−−−−−−−√≤ak+abs(i−k)−−−−−−−−√ 则决策点 k 永远优于决策点j; 而若 aj+abs(i−j)−−−−−−−−√>ak+abs(i−k)−−−−−−−−√ ，随着 i 的增大，k后可能比 j 优。
（下文中设val(i,pos)=a[pos] i−pos−−−−−−√ | i>pos）
解法一:我们不妨用set维护一个单调队列，使得对于当前 i ,val(i,que[j])是不上升的。然后考虑加入决策点 i ,若aque[r] abs(i−que[r])−−−−−−−−−−−√≤ai直接弹掉队尾,否则二分 que[r] 会在哪里被 i 超越，把点对塞进那个点的vector里。 然后枚举在i有哪些点对相互超越，然后在set中维护一下就行了。
解法二：（HCX大佬想出来的，我反正只能抄抄POPOQQQ大爷的代码。） 类似于解法一，我们维护一个三元组单调队列 (pos,lef,rig) ，表示决策点 pos 目前看来对于区间 (lef,rig) 最优，加入决策点 i 时，若val(lefr,posr)<=val(lefr,i),则 posr可以舍弃 ,否则可以在 lefr到rigr+1 间二分一下 lefi ,更新一下就行了。
最后时间分别是22524ms和4000ms，感到自己深深地垃圾。
代码一:(set实现)
/************************************************************** Problem: 2216 User: bzjudge2 Language: C++ Result: Accepted Time:22524 ms Memory:28800 kb ****************************************************************/ #include<cstdio> #include<iostream> #include<cmath> #include<algorithm> #include<cstring> #include<vector> #include<set> using namespace std; #define MAXN 500000 #define MAXM #define INF 0x3f3f3f3f typedef long long int LL; template<class T> void Read(T &x){ x=0;char c=getchar();bool flag=0; while(c<'0'||'9'<c){if(c=='-')flag=1;c=getchar();} while('0'<=c&&c<='9'){x=x*10+c-'0';c=getchar();} if(flag)x=-x; } int n; int a[MAXN+10]; double VAL(int i,int pos){return (double)a[pos]+sqrt(i-pos);} int find(int x,int y){//二分x在什么时候被y超过 int l=y+1,r=n+1,mid; int ans=n+1; while(l<=r){ mid=(l+r)>>1; if(VAL(mid,x)<VAL(mid,y)){ ans=mid; r=mid-1; } else l=mid+1; } return ans; } set<int>op; vector< pair<int,int> >s[MAXN+10]; void work(int *dp){ for(int i=1;i<=n+1;++i)s[i].clear(); op.clear(); set<int>::iterator it,tmp; for(int i=1;i<=n;++i){ //维护后缀单调 while(!op.empty()){//弹弹弹，弹走鱼尾纹... it=op.end(),--it; if(VAL(i,*it)<=a[i]) op.erase(it); else break; } if(!op.empty()){//准备弹飞 it=op.end(),--it; s[find(*it,i)].push_back(make_pair(*it,i)); } op.insert(i); //维护中间单调 while(!s[i].empty()){//看看当前可以弹飞那些决策点 int x=s[i].back().first,y=s[i].back().second; s[i].pop_back(); if(op.find(y)==op.end())//y已被弹出（已有更优解） continue;//不需替换 if((it=op.find(x))==op.end())//x已被弹出...防卡死 continue; while(true){ if(VAL(i,*it)<=VAL(i,y)){//能弹就使劲弹 if(it==op.begin()){ op.erase(it); break; } else{ tmp=it--; op.erase(tmp); } } else{//不能弹出，再次准备 s[find(*it,y)].push_back(make_pair(*it,y)); break; } } } //取出最优解 it=op.begin(); dp[i]=a[*it]+ceil(sqrt(i-*it))-a[i]; } } int dpfront[MAXN+10],dpback[MAXN+10]; int main(){ Read(n); for(int i=1;i<=n;++i)Read(a[i]); work(dpfront); for(int i=1;i<=(n>>1);++i) swap(a[i],a[n-i+1]); work(dpback); for(int i=1;i<=n;++i) printf("%d\n",max(dpfront[i],dpback[n-i+1])); }代码二:（数组实现）
/************************************************************** Problem: 2216 User: bzjudge2 Language: C++ Result: Accepted Time:4000 ms Memory:13020 kb ****************************************************************/ #include<cstdio> #include<iostream> #include<cmath> #include<algorithm> #include<cstring> using namespace std; #define MAXN 500000 #define MAXM #define INF 0x3f3f3f3f typedef long long int LL; template<class T> void Read(T &x){ x=0;char c=getchar();bool flag=0; while(c<'0'||'9'<c){if(c=='-')flag=1;c=getchar();} while('0'<=c&&c<='9'){x=x*10+c-'0';c=getchar();} if(flag)x=-x; } int n; int a[MAXN+10]; const double EPS = 1e-6; int Sign(const double x){ if(x>EPS)return 1; else if(x<-EPS)return -1; else return 0; } double VAL(int i,int pos){return (double)a[pos]+sqrt(i-pos);} //单调队列{ int que[MAXN+10];//决策点位置（按决策区间的左端点单调） int l[MAXN+10],r[MAXN+10];//决策点可以覆盖的最优解范围 int ql,qr; //} void work(int *dp){ ql=1,qr=0; for(int i=1;i<=n;++i){ while(ql<=qr&&r[ql]<i)++ql;//当前决策点已过期 if(ql<=qr)l[ql]=max(l[ql],i);//更新最优决策点决策区间 //加点&&维护单调性 if(ql>qr||VAL(n,que[qr])<VAL(n,i)){//如果决策点i可以代替决策点que[r] //向单调队列中加点 while(ql<=qr&&VAL(l[qr],que[qr])<VAL(l[qr],i)) --qr;//若i比que[qr]在l[qr]端点都要优，que[qr]是一定可以抛弃的 if(ql>qr)que[++qr]=i,l[qr]=i,r[qr]=n;//若队列为空 else{//二分超越点&&更新 int pos=r[qr]+1; int ll=l[qr],rr=r[qr]+1,mid; while(ll<=rr){ mid=(ll+rr)>>1; if(VAL(mid,que[qr])<=VAL(mid,i)){ pos=mid; rr=mid-1; } else ll=mid+1; } r[qr]=pos-1; que[++qr]=i,l[qr]=pos,r[qr]=n; } } dp[i]=a[que[ql]]+ceil(sqrt(i-que[ql]))-a[i];//得到答案 } } int dpfront[MAXN+10],dpback[MAXN+10]; int main(){ Read(n); for(int i=1;i<=n;++i)Read(a[i]); work(dpfront); for(int i=1;i<=(n>>1);++i) swap(a[i],a[n-i+1]); work(dpback); for(int i=1;i<=n;++i) printf("%d\n",max(dpfront[i],dpback[n-i+1])); }