P3515 [POI2011] Lightning Conductor

· · 题解

P3515 [POI2011] Lightning Conductor

线性做法！

题目相当于对每个 i 求 f_i = \max\limits_{j = 1} ^ n a_j + \lceil\sqrt {|i - j|} \rceil。分成 j < i 和 j > i 分别求解，考虑 j < i 的情况。

因为贡献函数 f = \sqrt x 二阶导恒为负且求最大值，所以前面的决策会被后面的决策反超，具有决策单调性。这样，我们可以通过二分队列优化 \max\limits_{j = 1} ^ {i - 1} a_j + \lceil\sqrt {|i - j|} \rceil 的求解。时间复杂度 \mathcal{O}(n\log n)。

我们发现二分队列最耗时间的部分只有二分反超点。因为本题要求的式子较特殊，我们可以 \mathcal{O}(1) 计算反超点。设两个决策点 k < j，我们希望求出最小的 i > j 使得 k\to i 劣于 j\to i。

\begin{aligned} a_k + \sqrt {i - k} & < a_j + \sqrt {i - j} \\ \sqrt {i - k} - \sqrt{i - j} & < a_j - a_k \end{aligned}

设 d = a_j - a_k。当 d \leq 0 时，上式恒不成立，i 不存在。因此 d > 0。

\begin{aligned} \sqrt{i - k} & < d + \sqrt{i - j} \\ i - k & < d ^ 2 + i - j + 2d \sqrt{i - j} \\ j - k - d ^ 2 & < 2d \sqrt{i - j} \end{aligned}

当 j - k - d ^ 2 \leq 0，即 j - k \leq d ^ 2 时，上式恒成立，j 一定会把 k 弹出而不会进入二分反超点的过程。因此 j - k > d ^ 2。根据实际意义也容易理解，当 a_j 过大时，a_k\to j 甚至不如 a_j。

不等号两侧同时平方。设 v = \dfrac {(j - k - d ^ 2) ^ 2} {4d ^ 2}，则 v < i - j，即 i > j + v。这样，我们 \mathcal{O}(1) 得到反超点 j + \lfloor v\rfloor + 1。时间复杂度 \mathcal{O}(n)。

获得了 Luogu 和 LOJ 最优解（2022.10.27）。

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define TIME 1e3 * clock() / CLOCKS_PER_SEC
using ll = long long;
using ld = long double;
// using lll = __int128;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using us = unsigned short;
// using uint = unsigned int;
using ull = unsigned long long;
char buf[1 << 21], *p1 = buf, *p2 = buf, obuf[1 << 25], *O = obuf;
#define gc (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
#define pc(x) (*O++ = x)
inline int read() {
  int x = 0;
  char s = gc;
  while(!isdigit(s)) s = gc;
  while(isdigit(s)) x = x * 10 + s - '0', s = gc;
  return x;
}
inline void print(int x) {
  if(x >= 10) print(x / 10);
  pc(x % 10 + '0');
}
bool Mbe;
constexpr int N = 5e5 + 5;
int n, a[N], f[N];
double sqr[N];
struct dat {int p, l, r;} q[N];
double get(int u, int v) {return a[u] + sqr[v - u];}
int hd, tl;
void solve() {
  f[1] = max(f[1], a[1]);
  q[hd = tl = 0] = {1, 1, n};
  for(int i = 2; i <= n; i++) {
    if(q[hd].r < i) hd++;
    q[hd].l = i;
    while(hd <= tl && get(q[tl].p, q[tl].l) < get(i, q[tl].l)) tl--;
    if(hd > tl) q[hd = tl = 0] = {i, i, n};
    else {
      int k = q[tl].p, j = i, d = a[j] - a[k];
      ll pos;
      if(d <= 0) pos = q[tl].r + 1;
      else {
        ll v = j - k - d * d;
        pos = j + v * v / (d * d << 2) + 1;
      }
      if(pos <= n) q[tl].r = pos - 1, q[++tl] = {i, pos, n};
    }
    f[i] = max(f[i], (int) ceil(get(q[hd].p, i)));
  }
}
bool Med;
int main() {
  fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
  #ifdef ALEX_WEI
    FILE* IN = freopen("1.in", "r", stdin);
    FILE* OUT = freopen("1.out", "w", stdout);
  #endif
  cin >> n;
  for(int i = 1; i <= n; i++) sqr[i] = sqrt(i);
  for(int i = 1; i <= n; i++) a[i] = read();
  solve();
  reverse(a + 1, a + n + 1);
  reverse(f + 1, f + n + 1);
  solve();
  for(int i = n; i; i--) print(f[i] - a[i]), pc('\n');
  cerr << TIME << " ms\n";
  return fwrite(obuf, 1, O - obuf, stdout), 0;
}
/*
2022/10/27
author: Alex_Wei
start coding at 
finish debugging at 
*/