自动搬运

查看原文

来自洛谷，原作者为

	AThousandSuns Simultaneous release!

搬运于2025-08-24 22:11:26，当前版本为作者最后更新于2019-09-09 18:04:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我是真的纳闷……这明显就是搬了 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$ 无关，所以转移可以按任意顺序，那就可以分治。

这里选择分治，毕竟码量小，好想。

$solve(l,r,L,R)$ 表示正在计算 $[l,r]$ 的 $p$，已知决策在 $[L,R]$ 里面。

取 $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$ 存成实数，最后再取整，那么决策点可以看作是唯一的。就不会出现一些奇怪的情况……

（别问我为什么挂了那么久……）

#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]));
}