(POI) XVIII OI Round I Task Lightning Conductor [決策點單調優化]

https://szkopul.edu.pl/problemset/problem/iYVwsAcHHCRZzAtQh0QFKbsu/site/?key=statement

先說明： f(x) = sqrt(x) 在經過差分後，會形成一個遞減序列 (ex: sqrt(2) - sqrt(1) > sqrt(3) - sqrt(2) )

再看看我們要求的式子：ans[i] = max( h[j] + sqrt(i-j) ) (先假設j < i)，因為sqrt差分後遞減，所以可以發現一件事情：假設pos[i]代表i的轉移點(h[ pos[i] ] + sqrt(i-pos[i])最大)，若j < i，則pos[j] <= pos[i]。(可以自行用反證法證證看XDD)。

因此，我們可以發現：轉移點單調性。隨著i的增大，pos[i]會越來越大，所以就可以很開心的用分治去求了~。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

const int N = 500006;
const int INF = 1e9 + 7;

int h[N];
double ans1[N],ans2[N];

void solve1(int range_L,int range_R,int decision_L,int decision_R,double* ans)
{
    //for a fixed i, only looking for j < i
    if (range_L > range_R) return;
    int mid = (range_L+range_R) >> 1;
    ans[mid] = -INF;
    int decision_pos = -1;
    for (int i=decision_L;decision_R >= i && mid >= i;i++)
    {
        if (sqrt(mid-i) + h[i] >= ans[mid])
        {
            ans[mid] = sqrt(mid-i) + h[i];
            decision_pos = i;
        }
    }
    solve1(range_L,mid-1,decision_L,decision_pos,ans);
    solve1(mid+1,range_R,decision_pos,decision_R,ans);
}

int main ()
{
    int n;
    scanf("%d",&n);
    for (int i=1;n>=i;i++)
    {
        scanf("%d",&h[i]);
    }
    solve1(1,n,1,n,ans1);
    reverse(h+1,h+n+1);
    solve1(1,n,1,n,ans2);
    reverse(ans2+1,ans2+n+1);
    reverse(h+1,h+n+1);
    for (int i=1;n>=i;i++)
    {
        printf("%d\n",int( ceil( max(ans1[i],ans2[i])-h[i] ) ));
    }
}