题意

题目链接

Sol

很nice的决策单调性题目

首先把给出的式子移项，我们要求的$P_i = max(a_j + \sqrt{|i - j|}) - a_i$。

按套路把绝对值拆掉，$p_i = max(max_{j = 1}^i (a_j = \sqrt{i - j}), max_{j = i + 1}^n (a_j + \sqrt{j - i})) - a_i$

对于后面的一段，我们把序列翻转之后和前一段是等价的。

也就是说，我们现在只需要找到$P_i = max_{j = 1}^i (a_j +　\sqrt{i - j})$

考虑到式子中只有一个max函数，那这玩意儿应该是有决策单调性的

直接设$f_j = a_j + \sqrt{i - j}, i \geqslant j$，其中$i$是自变量

观察这个函数，应该是一个在$[j, INF]$内有定义，过点$(j, a[j])$的函数，且增速与函数$g_i = \sqrt{i}$相同

我们需要做的，就是对每个$i$，找到最大的$f_j$

考虑到$g_i$增长速度会越来越慢，所以一个函数增长到一定程度后可能会被另一个函数取代

直接用单调队列维护，设$K_{i, j}$表示$f_i, f_j$的交点，$h, t$分别表示队首/尾，

当新加入一个元素$i$的时候，显然，若$K_{t -1, t} > K_{t - 1, i}$，那么$t$这个函数是没用的、

当$K_{h, h+1} < i$的时候，弹出队首

就是最后输出答案的时候有点“卡精度”，真恶心

经验：

以后看到$f_i = max(f_j) + g$的式子一定要往单调性上想，如果单调性不是很显然的话可以用换元法设函数找单调性

另外绝对值拆开算一般会好算一些

#include
     
      #define Pair pair
      
       #define MP(x, y) make_pair(x, y)#define fi first#define se secondusing namespace std;const int MAXN = 1e6 + 10, INF = 1e9 + 10;inline int read() {    char c = getchar(); int x = 0, f = 1;    while(c < '0' || c > '9') {
   if(c == '-') f = -1; c = getchar();}    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();    return x * f;}int N, a[MAXN], q[MAXN], Cro[MAXN];double P[MAXN], sqr[MAXN];double calc(int j, int i) {    return a[j] + sqr[i - j];}int K(int x, int y) {    int l = max(x, y), r = N, ans = N + 1;    while(l <= r) {        int mid = l + r >> 1;        if(calc(x, mid) >= calc(y, mid)) l = mid + 1;        else r = mid - 1, ans = mid;    }    return ans;}void solve() {    int h = 1, t = 0;    for(int i = 1; i <= N; i++) {        while(h < t && K(q[t - 1], q[t]) >= K(q[t], i)) t--;        q[++t] = i;        while(h < t && K(q[h], q[h + 1]) <= i) h++;        P[i] = max(P[i], calc(q[h], i));    }}main() {    N = read();    for(int i = 1; i <= N; i++) a[i] = read(), sqr[i] = sqrt(i);    solve();    reverse(a + 1, a + N + 1);    reverse(P + 1, P + N + 1);    solve();    for(int i = N; i >= 1; i--)        printf("%d\n", max(0, (int)ceil(P[i]) - a[i]));    return 0;}