[BZOJ2216][Poi2011]Lightning Conductor 决策单调性


原题链接
我们只统计j<i的,然后翻过来再做一遍,就把绝对值去掉了.
然后容易证明:对于任意的i1<i2,i1的决策点必然不会超过i2的决策点.
那么就有了两种做法,一种是整体二分,看看中间点的决策点是谁,然后将序列劈成两半;另一种是利用队列维护每个点能够更新的区间.

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 502333
using namespace std;
typedef double f32;
const f32 eps=1e-7;
inline char nc()
{
    static char buf[100000],*p1,*p2;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &x)
{
    x=0;char c=nc();
    while(!isdigit(c))c=nc();
    while(isdigit(c))x=x*10+c-'0',c=nc();
}
int n,a[N];
f32 f[N],g[N],sq[N];
inline int getsq()
{
    for(int i=1;i<=n;++i)sq[i]=sqrt(1.0*i);
}
inline int flor(f32 x)
{
    return (int)(x-eps)+1;
}
void cdq(int l,int r,int b,int e,f32 *dp)
{
    if(l>r)return;
    int mid=(l+r)>>1,p,i;
    f32 tmp,maxx=-1;
    for(i=b;i<=min(e,mid);++i)
    {
        tmp=a[i]+sq[mid-i];
        if(tmp>maxx)maxx=tmp,p=i;
    }
    dp[mid]=maxx;
    cdq(l,mid-1,b,p,dp),cdq(mid+1,r,p,e,dp);
}
int main()
{
    read(n);
    getsq();
    int i;
    for(i=1;i<=n;++i)read(a[i]);
    cdq(1,n,1,n,f);
    for(i=1;i*2<=n;++i)swap(a[i],a[n-i+1]);
    cdq(1,n,1,n,g);
    for(i=1;i<=n;++i)printf("%d\n",flor(max(f[i],g[n-i+1]))-a[n-i+1]);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注