BZOJ4850
很容易发现
sqrt(|i−j|)
很多情况下都是相等的。 那么就可以考虑分块。(题目应该是
hj≤hi+p−sqrt(|i−j|)
) 当
sqrt(|i−j|)=x
时，令
Mx
为所有满足
sqrt(|i−j|)=x
的
j
中，最大的hj值。 那么
p>=Mx+sqrt(|i−j|)−hi
一开始直接将
sqrt(|i−j|)=x
四舍五入了。。显然错了。应该向上取整。 然后发现长度为
1
时，x=1，长度为
2,3,4
时，
x=2
，长度为
5,6,7,8,9
时，
x=3
…… 那么
(i−1)2+1到i2
的
sqrt(|i−j|)
是相等的。就可以分块了。 对于每一块，用
RMQ
求出块内最大值，对于每一块，求出最大值即可。
Ansi=Max(Mx+x−hi)
复杂度
O(NN−−√)
。只要打的不算太丑都能水过去。。
QAQ
dsy垫底
1.15s
噢不能用线段树。。加个
log
就跑不过去了。 至于正解。。决策单调性整体二分什么的。。反正我不会
【代码】
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#define N 100005
#define mod 1000000007
#define INF 0x7fffffff
using namespace std;
typedef long long ll;
ll read()
{
ll x=
0,f=
1;
char ch=getchar();
while(!
isdigit(ch)){
if(ch==
'-') f=-
1;ch=getchar();}
while(
isdigit(ch)){x=(x<<
1)+(x<<
3)+ch-
'0';ch=getchar();}
return x*f;
}
int n,sum;
int h[N],DP[N][
30],Bit[N];
void RMQ()
{
int temp=(
int)(
log((
double)n)/
log(
2.0));
for(
register int i=
1;i<=n;i++) Bit[i]=(
int)(
log((
double)i)/
log(
2.0));
for(
register int i=
1;i<=n;i++)
DP[i][
0]=h[i];
for(
register int j=
1;j<=temp;j++)
for(
register int i=
1;i<=n;i++)
if(i+(
1<<j)<=n) DP[i][j]=max(DP[i][j-
1],DP[i+(
1<<(j-
1))][j-
1]);
}
int Query(
int L,
int R)
{
int k=Bit[R-L+
1];
return max(DP[L][k],DP[R-(
1<<k)+
1][k]);
}
void Solve(
int x)
{
int i=
1,j=x-
1,ans=
0;
while(
1)
{
int len=i*i-(i-
1)*(i-
1);
int jj=j-len+
1;jj=max(jj,
1);
if(jj>j)
break;
int mx=Query(jj,j);
ans=max(ans,mx-h[x]+i);
if(jj==
1)
break;j=jj-
1;i++;
}
i=
1,j=x+
1;
while(
1)
{
int len=i*i-(i-
1)*(i-
1);
int jj=j+len-
1;jj=min(jj,n);
if(jj<j)
break;
int mx=Query(j,jj);
ans=max(ans,mx-h[x]+i);
if(jj==n)
break;j=jj+
1;i++;
}
printf(
"%d\n",ans);
}
int main()
{
n=read();
for(
register int i=
1;i<=n;i++) h[i]=read();
RMQ();
for(
register int i=
1;i<=n;i++) Solve(i);
return 0;
}
