rt,写的 st 表。不吸氧还会多 T 三个点
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5, logN = 18;
int st[N][logN], Log2[N], a[N];
int query(int x, int y){
int qwq = Log2[y - x + 1];
return max(st[x][qwq], st[y - (1 << qwq) + 1][qwq]);
}
int main (){
int n;
read(n);//略去快读板子
for (int i = 1; i <= n; i++)read(st[i][0]);
for (int i = 2; i <= n; i++)Log2[i] = Log2[i >> 1] + 1;
for (int j = 1; j < logN; j++)
for (int i = 1; i <= n; i++)
st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
for (int i = 1; i <= n; i++){
int Max = 0;
for (int j = 1; i + ((j - 1) * (j - 1) + 1) <= n; j++)
Max = max(Max, query(i + ((j - 1) * (j - 1) + 1), min(n, i + j * j)) + j);
for (int j = 1; i - ((j - 1) * (j - 1) + 1) > 0; j++)
Max = max(Max, query(max(1, i - j * j), i - ((j - 1) * (j - 1) + 1)) + j);
write(Max - st[i][0]);
}
return 0;
}