Lightning Conductort题解-二分和单调性的一道好题
题目：Lightning Conductort
网址：
https://www.luogu.com.cn/problem/P3515
题面翻译
给定一个长度为 $n$ 的序列 ${a_n}$，对于每个 $i\in [1,n]$ ，求出一个最小的非负整数 $p$ ，使得 $\forall j\in[1,n]$，都有 $a_j\le a_i+p-\sqrt{|i-j|}$
$1 \le n \le 5\times 10^{5}$，$0 \le a_i \le 10^{9}$ 。
参考的博客
https://www.luogu.com.cn/blog/wby1427421659/lightning-conductort-ti-xie
柿子的推导
先将答案p移到一边并且去掉绝对值
那么可以得到
$$
p>=a[j]-a[i]+\sqrt{i-j}(i>=j)
$$
以及
$$
p>=a[j]-a[i]+\sqrt{j-i}(j>=i)
$$
很显然这两个柿子是十分相似的，那我们试着用前面这个来尝试做一做
我们要试着找最佳的答案（不然呢）
我们可以发现对于每个ans[i](程序是f[i]），是递增的
那么就好打分治了
还不懂？看代码！很详细的（solve1solve2是参考上帖子打出来的，如果分析有误请麻烦指出，十分感谢）
#include<bits/stdc++.h>
using namespace std;
long double ans1[6000005];
long double ans2[6000005];
long long a[6000005];
//十年oi一场梦，不开long long 见祖宗
//https://www.luogu.com.cn/blog/wby1427421659/lightning-conductort-ti-xie
//我个人只想到了单调性这一步，没想出来怎么做
//参考博客后就才明白是上课讲的nlogn算法（至少有点像
//两个solve照着打了一遍，尝试理解，详细见注释
void solve1(int L,int R,int l,int r){//ans[i]=max(a[j]+sqrt(i-j))-a[i] (1<=j<=i)
//solve(L,R,l,r)表示f[L]~f[R](下标）的最优决策点在l~r（ans)
if (L>R){
return;
}
int mid=(L+R)/2;
//常规二分
int g=0;
long double tmp=0;
ans1[mid]=a[mid];
for (int i=l;i<=min(r,mid);i++){//利用n的时间找到这一段的最佳决策点
tmp=a[i]+sqrt(double(mid-i));//某个点的决策点下的值
if (tmp>ans1[mid]){//如果这个点是更佳的点（找最优）
ans1[mid]=tmp;//记录这个点的值
g=i;//记录这个点的位置
}
}
if(g==0){//全程都没有找到的话，说明这一部分没有找到最佳
g=mid;//g的位置变为mid,就相当于这一次什么p用都没做，只能继续二分下去
}
ans1[mid]-=a[mid];//这是原式变化而来最后差的部分
solve1(L,mid-1,l,g);
solve1(mid+1,R,g,r);//最佳决策点是递增的，因此下标增则决策点增，下标减则决策点减
}
void solve2(int L,int R,int l,int r){//相比solve1就是反着做
if (L>R) return ;
int mid=(L+R)/2;
int g=0;
long double tmp=0;
ans2[mid]=a[mid];
for (int i=r;i>=max(mid,l);i--){
tmp=a[i]+sqrt(double(i-mid));
if (tmp>ans2[mid]){
ans2[mid]=tmp;
g=i;
}
}
if (g==0){
g=mid;
}
ans2[mid]-=a[mid];
solve2(L,mid-1,l,g);
solve2(mid+1,R,g,r);
}
int main(){
ios::sync_with_stdio(false);
long long n;
cin >> n;
for(int i=1;i<=n;i++){
cin >> a[i];
}
solve1(1,n,1,n);
solve2(1,n,1,n);
for (int i=1;i<=n;i++){
cout<<(long long)ceil(max(ans1[i],ans2[i]))<<endl;
}
}