题解 P5503 【[JSOI2016]灯塔】
AThousandSuns
·
·
题解
我是真的纳闷……这明显就是搬了 POI2011 的经典原题……为什么还没人写决策单调性……
在我的博客园看效果更佳：点这里
这题其实就是 p_i=\lceil\max\limits_{j}(a_j-a_i+\sqrt{|i-j|})\rceil。
拆成两边，先只考虑 j<i，然后反过来再做一遍。
然后，发现满足决策单调性。怎么发现的呢？
令 f_j(i)=\sqrt{i-j}。会发现 f_{j_1}(i) 和 f_{j_2}(i) 至多只有一个交点。
然后，由于这里是小取代大，所以可以用单调队列。然后发现式子里面与 p_i 无关，所以转移可以按任意顺序，那就可以分治。
这里选择分治，毕竟码量小，好想。
取 $l,r$ 的中点 $mid$，求出其的决策点 $MID$。那么 $[l,mid-1]$ 的决策点肯定在 $[L,MID]$，那么可以递归 $solve(l,mid-1,L,MID)$。同理 $solve(mid+1,r,MID,R)$。
由于只会递归 $\log n$ 层，每层会循环 $[L,R]$ 的并集也就是 $[1,n]$，所以复杂度是 $O(n\log n)$。
如果把 $p_i$ 存成实数，最后再取整，那么决策点可以看作是唯一的。就不会出现一些奇怪的情况……
（别问我为什么挂了那么久……）
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=500050;
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline int read(){
int x=0,f=0;char ch=getchar();
while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
return f?-x:x;
}
int n,a[maxn];
double ans[maxn];
inline double calc(int i,int j){
return sqrt(i-j)+a[j]-a[i];
}
void solve(int l,int r,int L,int R){
if(l>r) return;
int mid=(l+r)>>1,p=L;
FOR(i,L+1,min(mid,R)) if(calc(mid,p)<calc(mid,i)) p=i;
ans[mid]=max(ans[mid],calc(mid,p));
solve(l,mid-1,L,p);
solve(mid+1,r,p,R);
}
int main(){
n=read();
FOR(i,1,n) a[i]=read();
solve(1,n,1,n);
FOR(i,1,n/2) swap(a[i],a[n-i+1]),swap(ans[i],ans[n-i+1]);
solve(1,n,1,n);
FOR(i,1,n/2) swap(a[i],a[n-i+1]),swap(ans[i],ans[n-i+1]);
FOR(i,1,n) printf("%.0lf\n",ceil(ans[i]));
}
```