LOJ 2074 灯塔

题目链接

题目要求\(p-i\geq h-j+\sqrt{|i-j|}-h-i\)
即\(p-i=\max\limits_{j=1}^{n}h-j+\left\lceil\sqrt{|i-j|}\right\rceil -h-i\)

因为可以观察的到\(\left\lceil\sqrt{|i-j|}\right\rceil\)取值个数是\(\mathjaxcal{O}(\sqrt{n})\)的。
所以枚举所有长度根号的上取整值，\(RMQ\)上查询对应区间的最大最小值。
即可\(\mathjaxcal{O}(n\log n+n\sqrt{n})\)时间内完成。

据说还有\(\mathjaxcal{O}(n\log n)\)的做法，咱也不会啊...
这题把高度改成小数就没法把小数改成上取整的了，这做法不就被卡了吗

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
int n, a[N], cnt, f[N][21], lo[N];
pair<int, int> sq[N / 100];
int sqrt(int n) {
	return (int)ceil(sqrt(n * 1.0));
}

void init() {
	for (int i = 1; i <= n; i++) f[i][0] = a[i];
	for (int j = 1; (1 << j) <= n; j++)
		for (int i = 1; i <= n - (1 << j) + 1; i++) {
			f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
		}
    for (int i = 2; i <= n; i++) lo[i] = lo[i / 2] + 1;
}
int qry(int i, int j, int now, int k) {
	i = max(1, i), j = min(j, n);
    int len = j - i + 1;
	int res = max(f[i][lo[len]], f[j - (1 << lo[len]) + 1][lo[len]]);
	return res + k - a[now];
}

int main() {
    scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    int head = 1,  now = sqrt(1);
	for (int i = 1; i <= n + 1; i++) {
		if (sqrt(i) != now) {
            sq[++cnt] = {head, i - 1};
			now = sqrt(i);
			head = i;
		}
	}
	if (head != n + 1) sq[++cnt] = {head, n};
	init();
	for (int i = 1; i <= n; i++) {
		int res = 0;
		bool le = 1, re = 1;
		for (int j = 1; j <= cnt; j++) {
			if (!le && !re) break;
			int l = sq[j].first, r = sq[j].second;
			if (le) res = max(qry(i - r, i - l, i, j), res);
			if (re) res = max(qry(i + l, i + r, i, j), res);
			if (i - r <= 1) le = 0;
			if (i + r >= n) re = 0;
		}
		printf("%d\n", res);
	}
	return 0;
}