Dyd's Blog

He who has a strong enough why can bear almost any how.

luoguP5503 [JSOI2016]灯塔

Posted on In
Symbols count in article: 2.8k Reading time ≈ 3 mins.

明明 $O(n \sqrt{n})$ 可以的……

灯塔

题意

给定 $n \le 10^5$ 个数 $0 \le h_i \le 10^9$ ，对于每个数求出一个最小的 $p_i$ 使得 $h_j \le h_i + p_i - \sqrt{\mid i - j \mid}$ 对任意 $h_j$ 成立

正常做法

化式子为 $h_j - h_i + \sqrt{\mid i - j \mid} \le p_i$ ，直接暴力是 $n^2$ 的，麻烦点是那个根号，考虑枚举 $k = \sqrt{\mid i - j \mid}$ ，对于枚举到的每个 $k$ ，扫描整个数列，对于当前点 $i$ ，找到满足条件的最大 $h_j$ （用 ST 表可以做到 $O(1)$ ），跟新答案，时间复杂度为 $O(n \sqrt{n})$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
#define STC static
using namespace std;
const int N = 1e5 + 5, D = 15;
namespace ST
{
    int lg2[N], mx[N][D];
    void prev(int x[], int len)
    {
        lg2[1] = 0;
        for (int i = 2; i <= len; ++i) lg2[i] = lg2[i >> 1] + 1;
        for (int i = 1; i <= len; ++i) mx[i][0] = x[i];
        for (int j = 1; j < D; ++j)
            for (int i = 1; i <= len; ++i) mx[i][j] = max(mx[i][j - 1], mx[i + (1 << (j - 1))][j - 1]);
    }
    int ask(int l, int r)
    {
        int k = lg2[r - l + 1];
        return max(mx[l][k], mx[r - (1 << k) + 1][k]);
    }
}
int main()
{
    int n;
    STC int h[N], p[N];
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &h[i]);
    ST::prev(h, n);
    for (int k = 1, t = ceil(sqrt(n)); k <= t; ++k)
        for (int i = 1, l, r; i <= n; ++i)
        {
            l = (k - 1) * (k - 1) + i + 1, r = min(k * k + i, n);
            if (l <= r) p[i] = max(p[i], ST::ask(l, r) - h[i] + k);
            l = max(i - k * k, 1), r = i - (k - 1) * (k - 1) - 1;
            if (l <= r) p[i] = max(p[i], ST::ask(l, r) - h[i] + k);
        }
    for (int i = 1; i <= n; ++i) printf("%d\n", p[i]);
    return 0;
}

蒟蒻我到这就结束了，但总有巨佬觉得时间还可以再优

巨佬的时间

某位巨佬想出了 $O(n \log n)$ 的做法

首先去掉绝对值，只考虑 $j < i$ 的情况，设 d[i] 表示“第 $i$ 个数对所有 $j \le i$ 满足条件的最小 $p_i$ ”，然后倒过来再做一遍即可，显然 $d[i] = \max(h_j - h_i + \sqrt{i - j})$

然后，考虑根号，注意到这是典型的 $d[i] = \max_{j = 1}^{i - 1} (d[j] + w(j, i))$ 的形式，考虑四边形不等式，那么就要证明 $\forall a < b, w(a, b + 1) + w(a + 1, b) \le w(a, b) + w(a + 1, b + 1)$ （这里因为 $\max$ 所以符号和 $\min$ 相反），对于本题来说 $\sqrt{(b + 1) - a} + \sqrt{b - (a + 1)} \ge \sqrt{b - a} + \sqrt{(b + 1) - (a + 1)}$ 即 $\sqrt{b - a + 1} + \sqrt{b - a - 1} \ge 2\sqrt{b - a}$ 设 $t = b - a$ ，我们要证明 $\sqrt{t + 1} + \sqrt{t - 1} \ge 2 \sqrt{t}$ ，两边平方即可

因此决策具有单调性，直接用队列 + 二分维护三元组即可，巨佬说因为转移顺序没有要求，所以可以分治，但是我不会，不管如何实现，时间为 $O(n \log n)$

贺的巨佬的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
#define DB double
#define get(i, j) (h[j] + sqrt(i - j))
using namespace std;
const int N = 1e5 + 5;
int n, h[N];
DB p[N];
struct Node{ int l, r, x; } stk[N];
int find(int i, int j) //找到i比j更优的最后一个点 
{
    int l = max(i, j), r = n, res = -1, mid;
    while (l <= r)
    {
        mid = l + r >> 1;
        if (get(mid, i) >= get(mid, j)) res = mid, l = mid + 1;
        else r = mid - 1;
    }
    return res;
}
void work()
{
    int l, r;
    stk[l = r = 1] = {1, n ,1};
    for (int i = 2; i <= n; ++i)
    {
        while (l < r && stk[l].r < i) ++l;
        p[i] = max(get(i, stk[l].x), p[i]);
        if (get(n, i) <= get(n, stk[l].x)) continue;
        while (l < r && get(stk[r].l, stk[r].x) <= get(stk[r].l, i)) --r;
        stk[r].r = find(stk[r].x, i), stk[++r] = {stk[r - 1].r + 1, n, i};
    }
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &h[i]);
    work();
    reverse(h + 1, h + 1 + n), reverse(p + 1, p + 1 + n);
    work();
    reverse(h + 1, h + 1 + n), reverse(p + 1, p + 1 + n);
    for (int i = 1; i <= n; ++i) printf("%d\n", max((int)ceil(p[i]) - h[i], 0));
    return 0;
}