题目链接：LOJ 2074

JSOI 的国境线上有 $N$ 座连续的山峰,其中第 $i$ 座的高度是 $h_i$。为了简单起见,我们认为这 $n$ 座山峰排成了连续一条直线。

如果在第 $i$ 座山峰上建立一座高度为 $p(p \ge 0)$ 的灯塔，JYY 发现,这座灯塔能够照亮第 $j$ 座山峰,当且仅当满足如下不等式：

$$ h_j \le h_i + p - \sqrt{\vert i − j\vert} $$

JSOI国王希望对于每一座山峰，JYY 都能提供建造一座能够照亮全部其他山峰的灯塔所需要的最小高度。你能帮助 JYY 么？

数据范围：$1< n\le 10 ^ 5$，$0< h_i \le 10 ^ 9$。

Solution

我们将这个式子变形：

$$ p\ge h_j - h_i + \sqrt{\vert i - j\vert} $$

首先发现根号可以上取整，不会影响答案；这样一来对于 $i$ 确定的情况下，$\sqrt{\vert i - j\vert }$ 只有 $\mathcal O(\sqrt n)$ 种取值。

我们可以枚举 $i\in [1, n]$ 和这 $\mathcal O(\sqrt n)$ 个取值，并求出对应取值的区间。用 $\text{RMQ}$ 直接求出区间最值来更新答案。

听说可以用决策单调性优化成 $\mathcal O(n\log n)$ 但是我不会啊 QAQ

时间复杂度：$\mathcal O(n\sqrt n)$。

Code

#include <cstdio>
#include <algorithm>

const int N = 1e5 + 5, logN = 17;

int n, a[N];

struct RMQ {
    int f[N][logN], lg[N];
    void build() {
        for (int i = 1; i <= n; i++) {
            f[i][0] = a[i];
        }
        for (int i = 2; i <= n; i++) {
            lg[i] = lg[i >> 1] + 1;
        }
        for (int j = 1; (1 << j) <= n; j++) {
            for (int i = 1; i + (1 << j) - 1 <= n; i++) {
                f[i][j] = std::max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
            }
        }
    }
    int query(int l, int r) {
        int k = lg[r - l + 1];
        return std::max(f[l][k], f[r - (1 << k) + 1][k]);
    }
} rmq;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    rmq.build();
    for (int k = 1; k <= n; k++) {
        int ans = 0;
        for (int l = 1, i = k + 1, j; i <= n; l++, i = j + 1) {
            j = std::min(n, i + l * l - (l - 1) * (l - 1) - 1);
            ans = std::max(ans, rmq.query(i, j) - a[k] + l);
        }
        for (int l = 1, i = k - 1, j; i >= 1; l++, i = j - 1) {
            j = std::max(1, i - l * l + (l - 1) * (l - 1) + 1);
            ans = std::max(ans, rmq.query(j, i) - a[k] + l);
        }
        printf("%d\n", ans);
    }
    return 0;
}