题解-luogu-p5503灯塔

#include <bits/stdc++.h>
using namespace std;

int st[100005][18];
int lg[100005];
int power[320];
int p[100005];
int N;

inline int query(int l, int r) {
    int s = lg[r - l + 1];
    return max(st[l][s], st[r - (1 << s) + 1][s]);
}

int main() {
    lg[1] = 0;
    for (register int i = 2; i <= 100000; ++i)
        lg[i] = lg[i >> 1] + 1;
    for (register int i = 1; i <= 319; ++i) {
        power[i] = i * i;
    }
    scanf("%d", &N);
    for (register int i = 1; i <= N; ++i)
        scanf("%d", &st[i][0]);
    for (register int j = 1; j <= lg[N]; ++j)
        for (register int i = 1; i + (1 << j) - 1 <= N; ++i)
            st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
    for (register int i = 1; i <= N; ++i) {
        int delta = 0, l = i, r = i;
        while (l >= 1) {
            p[i] = max(p[i], query(l, r) + delta - st[i][0]);
            r = l - 1, l = i - power[++delta];
        }
        if (r >= 1) p[i] = max(p[i], query(1, r) + delta - st[i][0]);

    }
    for (register int i = N; i >= 1; --i) {
        int delta = 0, l = i, r = i;
        while (r <= N) {
            p[i] = max(p[i], query(l, r) + delta - st[i][0]);
            l = r + 1, r = i + power[++delta];
        }
        if (l <= N) p[i] = max(p[i], query(l, N) + delta - st[i][0]);
    }
    for (register int i = 1; i <= N; ++i)
        printf("%d\n", p[i]);
    return 0;
}