[bzoj 2216] [Poi2011] Lightning Conductor

[bzoj 2216] [Poi2011] Lightning Conductor

Description

已知一个长度为n的序列a1,a2,…,an。
对于每个1<=i<=n，找到最小的非负整数p满足 对于任意的j, aj < = ai + p – sqrt(abs(i-j))

Input

第一行n，(1<=n<=500000)
下面每行一个整数，其中第i行是ai。(0<=ai<=1000000000)

Output

n行，第i行表示对于i，得到的p

Sample Input

6
5
3
2
4
2
4

Sample Output

2
3
5
3
5
4

将不等式变一下形就可以得到这个:
\[P\ge { A }_{ j }+\sqrt { \left| i-j \right| } -{ A }_{ i }\]
由于对任意的A都成立,那么就有:
\[P=max\{ { A }_{ j }+\sqrt { \left| i-j \right| } -{ A }_{ i }\} \]

这个是满足决策单调性的,假设存在 $ j>k $ 且j比k更优,考虑到函数 $ f\left( x \right) =\sqrt { x } $ 为一个上凸函数,那么由于 $ i-k $ 于 $ i-j $ 的增长速度相同,而 \(i-k\) 更大,所以$ f\left( k \right) =\sqrt { i-k } $也就增长得越快(就是下跌得更猛).所以可以用决策单调性优化.(即k永世不得翻身).那么就可以二分决策的端点进行dp了.绝对值左右两遍dp一下就可以去掉了.

#include <cstdio>
#include <cmath>
#include <algorithm>

using std :: max;
using std :: sqrt;
using std :: ceil;

static const int maxm = 1e6 + 10;

int f[maxm],g[maxm],A[maxm];
int n;

void solve1(int l,int r,int L,int R){
    if(l > r || L > R) return;
    
    int pos = 0,mid = (l + r) >> 1; double mx = 0;
    
    for(int i = L;i <= R && i <= mid;i++)
        if((double) A[i] + sqrt(mid - i) >= mx)
            pos = i,mx = (double) A[i] + sqrt(mid - i);
            
    f[mid] = A[pos] + ceil(sqrt(mid - pos));
    
    solve1(l,mid - 1,L,pos);
    solve1(mid + 1,r,pos,R);
}

void solve2(int l,int r,int L,int R){
    if(l > r || L > R) return;
    
    int pos = 0,mid = (l + r) >> 1; double mx = 0;
    
    for(int i = R;i >= L && i >= mid;i--)
        if((double) A[i] + sqrt(i - mid) >= mx)
            pos = i,mx = (double) A[i] + sqrt(i - mid);
            
    g[mid] = A[pos] + ceil(sqrt(pos - mid));
    
    solve2(l,mid - 1,L,pos);
    solve2(mid + 1,r,pos,R);
}

int main(){
    scanf("%d",&n);
    for(int i = 1;i <= n;i++)scanf("%d",&A[i]);
    
    solve1(1,n,1,n);solve2(1,n,1,n);
    
    for(int i = 1;i <= n;i++)printf("%d\n",max(f[i],g[i])-A[i]);
    
    return 0;
}

传送门(权限题,非bzoj)