Luogu P3515 [POI2011]Lightning Conductor 题解

题意

题目传送门 已知一个长度为$n$的序列$a_1,a_2,…,a_n$。 对于每个$1\leq i\leq n$，找到最小的非负整数$p$满足 对于任意的$j$,$ a_j \leq a_i + p - \sqrt{ i-j }$

思路

首先先把题目中的式子化简一下： $p\geq a_j+\sqrt{i-j}-a_i$ 原来就是求对于每个$1\leq i \leq n$，对于任意的$j$,求出$a_j+\sqrt{i-j}-a_i$的最大值啊~~~ 考虑跑两次决策单调性，一次$i>j$，另一次$i<j$，那么就可以把绝对值去掉了。 这里就只考虑$i>j$的情况。 对于每个$1\leq i \leq n$，只要求出最大的$a_j+\sqrt{i-j}$即可。 然而发现$a_j+\sqrt{i-j}$可以决策单调性优化。 也就是说，当i增大时 $a[j1]+sqrt(abs(i-j1))$增大值比$a[j2]+sqrt(abs(i-j2))$增大值小。 存在一个临界点$k$ 对于$j2+1<=i<=k，a[j1]+sqrt(abs(i-j1))>a[j2]+sqrt(abs(i-j2))$ 对于$k<i，a[j1]+sqrt(abs(i-j1))<a[j2]+sqrt(abs(i-j2))$ 考虑使用分治来做决策单调性优化。 $Solve(l,r,ql,qr)$表示在区间$[ql,qr]$中，已经决策出最大值在区间$[l,r]$中。 对于每次$Solve(l,r,ql,qr)$直接暴力扫一遍$[l,r]$求出其中的最大值，所以在区间$[ql,mid-1]$中，最大值肯定在$[l,这个区间的最大值所在位置]$，同理，在区间$[mid+1,qr]$中，最大值肯定在$[这个区间的最大值所在位置,r]$。 那么就好了呀O(∩_∩)O。

Code

#include<bits/stdc++.h>
#define LD double
#define int long long
using namespace std;
int n,a[500010],f[2][500010];
LD calc(int x,int y){
    return (LD)(sqrt((LD)abs((x-y)))+(LD)a[x]);
}
void solve(int l,int r,int ql,int qr,int dd){
    if(l>rql>qr) return;
    int s=l,mid=ql+qr>>1ll;
    double tmp=-19260817.19260817;
    for(int i=l;i<=r&&i<=mid;i++)
        if(tmp<=calc(i,mid)) tmp=calc(i,mid),s=i;
    f[dd][mid]=max(f[dd][mid],((int)tmp)+(((LD)((int)tmp))!=(LD)tmp)-a[mid]);
    solve(l,s,ql,mid-1ll,dd);
    solve(s,r,mid+1ll,qr,dd);
}
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lld",a+i);
    solve(1,n,1,n,0);
    for(int i=1;i<=n/2;i++) swap(a[i],a[n-i+1]);
    solve(1,n,1,n,1);
    for(int i=1;i<=n;i++) printf("%lld\n",max(f[0][i],f[1][n-i+1]));
}