「JSOI 2016」灯塔

Problem

Descripton

JSOI 的国境线上有 n 座连续的山峰,其中第 i 座山峰的高度是 h_{i}
为了简单起见,我们认为这 n 座山峰排成了一条直线。如果在第 i 座山峰上建立一座高度为 p(p\ge 0) 的灯塔,其能够照亮第 j 座山峰当且仅当满足如下不等式:

h_{j}\le h_{i}+p-\sqrt{\left|i-j\right|}

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

Constraints

1<n\le 10^{5},0<h_{i}\le 10^{9}

Solution

Analysis

可以发现对于任意 i,\left\lceil\sqrt{\left|i-j\right|}\right\rceil 的取值最多有 \left\lceil\sqrt{10^{5}-1}\right\rceil=317 种。
故在对每一个 i 进行处理时,可以对于 \left\lceil\sqrt{\left|i-j\right|}\right\rceil 的值进行讨论。
则有

p_{i}=\max\left\{\max\left\{h_{j} : \left\lceil\sqrt{\left|i-j\right|}\right\rceil=k\right\}-h_{i}+k : k\le\sqrt{\max\left(i-1,n-i\right)}+1\right\}

易知当 \left\lceil\sqrt{\left|i-j\right|}\right\rceil=k 时, j\in\left[i-k^{2},i-\left(k-1\right)^{2}\right)\cup\left(i+\left(k-1\right)^{2},i+k^{2}\right]\cap[1, n]
此时问题被转化为经典的 RMQ 问题,使用 ST 表处理即可。

时间复杂度 O\left(n\sqrt{n}\right) ​。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<cstdio>

inline int Min(const int&x,const int&y){return x<y?x:y;}
inline int Max(const int&x,const int&y){return x>y?x:y;}

struct Input{
#define SIZE 98304
char BUF[SIZE],*S,*T;
Input():S(BUF),T(BUF){}
inline Input&operator>>(char&c){return(c=(S==T)&&(T=(S=BUF)+fread(BUF,1,SIZE,stdin),S==T)?EOF:*S++,*this);}
template<typename T>inline Input&operator>>(T&s){
s=0;char c;
while(*this>>c,c<48||c>57);
while(s=s*10+c-48,*this>>c,c>47&&c<58);
return*this;
}
}input;

int H[100001];
int Log[100001];
int ST[100001][18];

inline void Init(const int&N){
for(int i=1;i<=N;++i)Log[i]=Log[i-1]+((i>>Log[i-1]+1)&1);
for(int i=1;i<=N;++i)ST[i][0]=H[i];
for(int j=1;j<=Log[N];++j){
for(int i=1;i<=N;++i){
if(i+(1<<(j-1))>N)break;
ST[i][j]=Max(ST[i][j-1],ST[i+(1<<(j-1))][j-1]);
}
}
}
inline int Query(const int&L,const int&R){
int k=Log[R-L+1];
return Max(ST[L][k],ST[R-(1<<k)+1][k]);
}
int N;
inline int Slove(const int&pos){
int Ans=0;
for(int k=1,L,R=pos-1;L!=1;++k,R=L-1){
if((L=Max(1,R-(k<<1)+2))>R)break;
Ans=Max(Ans,Query(L,R)-H[pos]+k);
}
for(int k=1,L=pos+1,R;R!=N;++k,L=R+1){
if((R=Min(L+(k<<1)-2,N))<L)break;
Ans=Max(Ans,Query(L,R)-H[pos]+k);
}return Ans;
}

int main(){
input>>N;
for(int i=1;i<=N;++i)input>>H[i];
Init(N);
for(int i=1;i<=N;++i)printf("%d\n",Slove(i));
return 0;
}