POI2011 避雷针 Lightning Conductor

题意

气候变化使 \(Byteburg\) 不得不建造一个大型避雷针来保护城市里的所有建筑物。建筑物恰好沿一条街，从 \(1\) 到 \(n\) 编号。

建筑物的高度和避雷针的高度都是非负整数。\(Byteburg\)经费有限，只能建造一个避雷针。而且避雷针越高，价格越贵。

在建筑物 \(i\)（高度为 \(h_i\) ）屋顶放置高为 \(p\) 的避雷针能够保护建筑物 \(j\) 的条件是：

\[h_j \le h_i + p - \sqrt{\lvert i - j \rvert}\]

其中 \(\lvert i - j \rvert\) 表示 \(i\) 和 \(j\) 差的绝对值。

\(Byteburg\) 需要你帮它计算，如果在第\(i\)个建筑物的屋顶放置这样的避雷针的话，避雷针的最小高度是多少。

题解

感觉这题好套路啊……

显然的一个计算公式:

\[ h_i+p=Max \{ h_j+ \sqrt{ | i - j | } \}\]

于是我们就可以分前半部分和后半部分来算，最后取个\(Max\)。考虑前半部分，那么这个决策实际上是单调的。假设\(j<k\)，如果\(h_j+\sqrt{ | i - j | } < h_k + \sqrt { | i - k |}\)，那么\(j\)的决策是永远不会变成最优的。因为\(\sqrt{x}\)的增长速度比\(x\)要慢。于是我们就可以维护单调队列了。正着做一遍，反着做一遍就可以了。

Code

#include
    
     using namespace std;const int N=5e5+500;typedef long long ll;int n,tail,head;ll h[N];double ans[2][N];struct node {  int l,r,idx;};node que[N],nw;double Calc(int x,int y) {  return (double)h[x]+sqrt(abs(x-y))-h[y];}int Check(node x,int i) {  double ans1=Calc(x.idx,x.l),ans2=Calc(i,x.l);  return ans1
     
      que[head].r) ++head;      if(head<=tail) {        ans[tp][i]=Calc(que[head].idx,i);      }    }    if(head>tail||Calc(que[tail].idx,n)
      
       >1;          if(Calc(que[tail].idx,Mid)