BZOJ_2216_[Poi2011]Lightning Conductor

BZOJ_2216_[Poi2011]Lightning Conductor_决策单调性

Description

已知一个长度为n的序列a1,a2,...,an。
对于每个1<=i<=n，找到最小的非负整数p满足对于任意的j, aj < = ai + p - sqrt(abs(i-j))

Input

第一行n，(1<=n<=500000)
下面每行一个整数，其中第i行是ai。(0<=ai<=1000000000)

Output

n行，第i行表示对于i，得到的p

Sample Input

6
5
3
2
4
2
4

Sample Output

2
3
5
3
5
4

首先有f[i]=max(a[j]+sqrt(|i-j|))-a[i]

先考虑j<i的情况，然后在考虑j>i的情况。

设j1<j2<i1<i2，j2转移i1比j1转移i1优，j1转移i2比j2转移i2优。

那么上下加一下再展开可以得出这是错的，所以满足决策单调性。

这个题比较良心卡出了我以前决策单调性代码的罢嗝。

就是每次队首的l需要++，否则计算后面的时候会用到Q[l].l，而此时Q[l].l可能已经转移过了。

代码：

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

#define N 500050

typedef double f2;

struct A {

    int l,r,p;

}Q[N];

int a[N],n;

f2 f[N];

f2 Y(int j,int i) {

    return a[j]+sqrt(i>j?i-j:j-i);

}

int find1(const A &a,int x) {

    int l=a.l,r=a.r+1;

    while(l<r) {

        int mid=(l+r)>>1;

        if(Y(x,mid)<=Y(a.p,mid)) l=mid+1;

        else r=mid;

    }

    return l;

}

int find2(const A &a,int x) {

    int l=a.l,r=a.r+1;

    while(l<r) {

        int mid=(l+r)>>1;

        if(Y(x,mid)>Y(a.p,mid)) l=mid+1;

        else r=mid;

    }

    return l-1;

}

int main() {

    scanf("%d",&n);

    int i,l=0,r=0;

    for(i=1;i<=n;i++) scanf("%d",&a[i]);

    for(i=1;i<=n;i++) {

        Q[l].l++;

        while(l<r&&Q[l].l>Q[l].r) l++;

        f[i]=max(0.0,Y(Q[l].p,i)-a[i]);

        if(l==r||Y(i,n)>Y(Q[r-1].p,n)) {

            while(l<r&&Y(i,Q[r-1].l)>Y(Q[r-1].p,Q[r-1].l)) r--;

            if(l==r) Q[r++]=(A){i,n,i};

            else {

                int x=find1(Q[r-1],i);

                Q[r-1].r=x-1; Q[r++]=(A){x,n,i};

            }

        }

    }

    l=r=0;

    for(i=n;i>=1;i--) {

        Q[l].r--;

        while(l<r&&Q[l].l>Q[l].r) l++;

        f[i]=max(f[i],Y(Q[l].p,i)-a[i]);

        if(l==r||Y(i,1)>Y(Q[r-1].p,1)) {

            while(l<r&&Y(i,Q[r-1].r)>Y(Q[r-1].p,Q[r-1].r)) r--;

            if(l==r) Q[r++]=(A){1,i,i};

            else {

                int x=find2(Q[r-1],i);

                Q[r-1].l=x+1; Q[r++]=(A){1,x,i};

            }

        }

    }

    for(i=1;i<=n;i++) {

        printf("%d\n",(int)ceil(f[i]));

    }

}

巴特西