P3515 [POI2011] Lightning Conductor 题解

· · 题解

核心代码共十行。

思路

显然可以把左侧和右侧分开处理来拆掉绝对值，下文中都考虑 j<i 的左侧情况。

鉴于 p\in\mathbb{N}，所以可以首先把式子换成 a_j+\left\lceil \sqrt{i-j}\right\rceil\leq a_i+p，之后的问题就是对于每个 i 算一下不等式左边那一坨东西的最大值就行了。

考虑一个比较容易想到的做法：

我们可以从左往右扫 i。容易发现，每次把 i 右移试图计算下一个位置上的答案时，只有根号个 a_j+\left\lceil \sqrt{i-j}\right\rceil 发生了变化，这些点就是类似距离为 9,10 这样的上取整断点。那么我们只需要扫一遍这根号个断点，再在每一个断点中间 RMQ（显然断点之间的根号上取整都是相同的），就可以移动一下重算一次最大值，从而得到一个复杂度是 \mathcal O(n\sqrt n \log n) 的做法，但这显然是过不了的。

考虑能不能不重算整个最大值。可以注意到，左侧每个点 j 总是在随着我们 i 的向右远去而贡献增大。这说明，每次有一个点 j 通过了断点需要重新给贡献的时候，它可以完美地覆盖掉自己之前对最大值的贡献。而剩下的没有通过断点的点对最大值的贡献是不变的。

所以我们根本就没必要重算最大值，直接把那几个通过断点的点的新贡献 \max 到旧的最大值里面就可以得到 i 右移一位之后新的最大值。

左右各跑一遍即可在每个 i 上都得到对于两侧的 j，a_j+\left\lceil \sqrt{|i-j|}\right\rceil 的最大值。这个东西直接减掉 a_i 就是 p 的最小值了。

这样就可以把时间复杂度降到 \mathcal O(n\sqrt n)。但是还有常数，所以看起来还是过不了。然而仔细分析一下可以发现我们其实复杂度里面根本没有顶满 n\sqrt n，而是 \sum\limits_{i=1}^{n} \sqrt i。随便积一下就能知道这个东西虽然级别是 \mathcal O(n\sqrt n)，但是可以贡献一个 \frac{2}{3} 的常数，所以清真实现一下（少用几个循环）再吸个氧就能稳过了。

下面是非常简短的代码。谷上吸了氧可以跑到 650ms 左右，LOJ 上吸氧可以跑进 500ms。

int n;
int h[N];
int maxn;
int ans[N];
int main(){
#ifdef zjh
    freopen("hack.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    ios::sync_with_stdio(false);
    cin>>n;
    fr1(i,1,n) cin>>h[i];
    maxn=0;
    fr2(i,n,1){
        ans[i]=maxn;
        for(int j=0;j*j<=n-i;j++) maxn=max(maxn,h[i+j*j]+j+1);
    }
    maxn=0;
    fr1(i,1,n){
        ans[i]=max(ans[i],maxn);
        for(int j=0;j*j<=i-1;j++) maxn=max(maxn,h[i-j*j]+j+1);
    }
    fr1(i,1,n) cout<<max(ans[i]-h[i],0)<<'\n';
    ET;
}