正題

題目連結:https://www.luogu.com.cn/problem/P3507

題目大意

\(n\)個數字的一個序列\(a\)，對于每個位置\(i\)求一個\(p_i\)使得對于任意\(j\)滿足

\[p_i+a_i-\sqrt{|i-j|}\geq p_j

解題思路

化簡一下發現我們是需要求出\(max\{\sqrt{|i-j|}+p_j\}\)

分成兩次去掉絕對值。

因為這個根号的性質是增長的越來越小，那麼對于一個位置\(i\)若它的\(max\)值位置為\(j\)，那麼\(i+1\)就一定不小于\(j\)。

利用這個單調性來優化，我們每次直接對于區間正中間\(mid\)暴力求出它的答案\(pos\)，那麼\([l,mid-1]\)的答案就在\([L,pos]\)，而\([mid+1,r]\)的答案就在\([pos,R]\)。

然後遞歸下去就好了。時間複雜度\(O(n\log n)\)

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<stack>
#define ll long long
using namespace std;
const ll N=5e5+10;
ll n;double a[N],f[N],sqr[N];
stack<ll> s;
double count(ll i,ll j)
{return a[j]+sqr[abs(j-i)];}
void CDQ(ll l,ll r,ll L,ll R){
    if(l>r)return;
    ll mid=(l+r)>>1,pos=L;
    double tmp=count(mid,L);
    for(int i=L+1;i<=R&&i<=mid;i++)
        if(count(mid,i)>tmp)
            pos=i,tmp=count(mid,i);
    f[mid]=max(tmp,f[mid]);
    CDQ(l,mid-1,L,pos);CDQ(mid+1,r,pos,R);
    return;
}
signed main()
{
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++){
        scanf("%lf",&a[n-i+1]);
        sqr[i]=sqrt((double)i);
    }
    CDQ(1,n,1,n);
    for(ll i=1;n-i+1>i;i++)
        swap(a[i],a[n-i+1]),swap(f[i],f[n-i+1]);
    CDQ(1,n,1,n);
    for(ll i=1;i<=n;i++)
        printf("%lld\n",(ll)ceil(f[i]-a[i]));
    return 0;
}