DDOSvoid's Blog

Luogu P3515 [POI2011]Lightning Conductor

发表于 更新于 分类于
本文字数： 2.8k 阅读时长 ≈ 3 分钟

题目描述

https://www.luogu.com.cn/problem/P3515

简要题意：给定一个长度为 $n$ 的序列 $a_i$，对于每个 $i\in[1,n]$，求一个最小的非负整数 $p$，满足对于所有 $j\in [1,n]$，$p\ge a_j+\sqrt {|i-j|}-a_i$

$n\le 5\times 10^5$

Solution

容易得到 $dp$ 方程，$f_i=max\lbrace a_j+\sqrt{i-j}\rbrace -a_i$，这里仅考虑 $ji$ 的情况直接将数组翻转然后再做一遍即可，容易发现该转移满足决策单调性

证明：

我们只需要证明 $\forall a<b,w(a,b)+w(a+1,b+1)\ge w(a,b+1)+w(a+1,b)$，此题中 $w(x,y)=\sqrt{y - x}$

即只需要证明 $\sqrt{b-a}+\sqrt{b-a}\ge \sqrt{b+1-a}+\sqrt{b-1-a}$，令 $d=b-a$

得 $2\sqrt d\ge \sqrt{d+1}+\sqrt{d-1}$，化简得 $\sqrt{d}-\sqrt{d-1}\ge \sqrt{d+1}-\sqrt{d}$ 得证

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
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <deque>
#include <cmath>
#include <algorithm>
#define maxn 500010
#define ll long long
#define INF 100000000000000000
using namespace std;

int n, a[maxn];

double f[maxn];
inline double w(int x, int y) { return x >= y ? -1 : a[x] + sqrt(y - x); }

struct node {
    int l, r, k;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    
    deque<node> Q; Q.push_back({ 1, n, 0 });
    for (int i = 1; i <= n; ++i) {
        while (!Q.empty() && Q.front().r < i) Q.pop_front();
        f[i] = max(f[i], w(Q.front().k, i));
        while (!Q.empty() && w(Q.back().k, Q.back().l) <= w(i, Q.back().l)) Q.pop_back();
        int l = Q.back().l, r = Q.back().r, k = Q.back().k, mid, ans;
        while (l <= r) {
            mid = l + r >> 1;
            if (w(k, mid) > w(i, mid)) ans = mid, l = mid + 1; 
            else r = mid - 1; 
        } Q.back().r = ans; if (ans < n) Q.push_back({ ans + 1, n, i });
    }

    while (!Q.empty()) Q.pop_back(); Q.push_back({ 1, n, 0 }); reverse(a + 1, a + n + 1);
    for (int i = 1; i <= n; ++i) {
        while (!Q.empty() && Q.front().r < i) Q.pop_front();
        f[n - i + 1] = max(f[n - i + 1], w(Q.front().k, i));
        while (!Q.empty() && w(Q.back().k, Q.back().l) <= w(i, Q.back().l)) Q.pop_back();
        int l = Q.back().l, r = Q.back().r, k = Q.back().k, mid, ans;
        while (l <= r) {
            mid = l + r >> 1;
            if (w(k, mid) > w(i, mid)) ans = mid, l = mid + 1; 
            else r = mid - 1; 
        } Q.back().r = ans; if (ans < n) Q.push_back({ ans + 1, n, i });
    } reverse(a + 1, a + n + 1); 
    for (int i = 1; i <= n; ++i) cout << max(0, (int) ceil(f[i]) - a[i]) << "\n";
    return 0;
} 

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
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define maxn 500010
#define db double 
using namespace std;

int n, a[maxn];

inline db F(int x, int y) { return a[x] + sqrt(y - x) - a[y]; } 

db f[maxn], g[maxn]; 
void solve(int l, int r, int L, int R, db *f) {
    if (l > r) return ; int m = l + r >> 1, p; 
    for (int i = L; i <= min(R, m - 1); ++i)
        if (F(i, m) > f[m]) f[m] = F(i, m), p = i;
    solve(l, m - 1, L, p, f); solve(m + 1, r, p, R, f);
} 

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    solve(1, n, 1, n, f); reverse(a + 1, a + n + 1); solve(1, n, 1, n, g);
    for (int i = 1; i <= n; ++i) f[i] = max(f[i], g[n - i + 1]); 
    for (int i = 1; i <= n; ++i) printf("%d\n", max(0, (int) ceil(f[i])));
    return 0;
}