loj2074 「JSOI2016」灯塔

#include <iostream>#include <cstdio>using namespace std;int n, a[100005], st[100005][19], mlg[100005];int getMax(int l, int r){ ???if(l>r) return -0x3f3f3f3f; ???int p=mlg[r-l+1]; ???return max(st[l][p], st[r-(1<<p)+1][p]);}int main(){ ???cin>>n; ???for(int i=1; i<=n; i++){ ???????scanf("%d", &a[i]); ???????st[i][0] = a[i]; ???} ???for(int i=2; i<=n; i++) ???????mlg[i] = mlg[i>>1] + 1; ???for(int i=1; i<=17; i++) ???????for(int j=1; j<=n && j+(1<<(i-1))<=n; j++) ???????????st[j][i] = max(st[j][i-1], st[j+(1<<(i-1))][i-1]); ???for(int i=1; i<=n; i++){ ???????int p=a[i]; ???????for(int x=1; ; x++){ ???????????p = max(p, getMax(max(i-x*x, 1), i-(x-1)*(x-1)-1)+x); ???????????if(i-x*x<=1) ???break; ???????} ???????for(int x=1; ; x++){ ???????????p = max(p, getMax(i+(x-1)*(x-1)+1, min(i+x*x, n))+x); ???????????if(i+x*x>=n) ???break; ???????} ???????printf("%d\n", p-a[i]); ???} ???return 0;}