Blog of RuSun

\begin {array}{c} \mathfrak {One Problem Is Difficult} \\\\ \mathfrak {Because You Don't Know} \\\\ \mathfrak {Why It Is Diffucult} \end {array}

P3515 [POI2011]Lightning Conductor

发表于 分类于
本文字数： 4.8k 阅读时长 ≈ 4 分钟

P3515 [POI2011]Lightning Conductor

分别从两边做二分队列。

注意如果转移不合法将值设为 $-inf$ 。

查看代码 
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const double inf = 2e9;
const int N = 5e5 + 10;
template <class Type>
void read(Type &x)
{
    static char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        (c == '-') && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    (flag) && (x = ~x + 1);
}
int n, w[N];
double f[N], g[N];
double cal1(int k, int i)
{
    return i < k ? -inf : w[k] - w[i] + sqrt(i - k);
}
double cal2(int k, int i)
{
    return i > k ? -inf : w[k] - w[i] + sqrt(k - i);
}
struct Node
{
    int p, l, r;
} q[N];
int hd, tl;
void solve1()
{
    hd = 1, tl = 0;
    q[++tl] = (Node){1, 1, n};
    for (int i = 2; i <= n; i++)
    {
        while (hd <= tl && q[hd].r < i)
            hd++;
        f[i] = cal1(q[hd].p, i);
        int p = n + 1;
        while (hd <= tl && cal1(i, q[tl].l) > cal1(q[tl].p, q[tl].l))
            p = q[tl--].l;
        if (hd <= tl && cal1(i, q[tl].r) > cal1(q[tl].p, q[tl].r))
        {
            int l = q[tl].l, r = q[tl].r;
            while (l <= r)
            {
                int mid = l + r >> 1;
                cal1(i, mid) > cal1(q[tl].p, mid) ? (p = mid, r = mid - 1) : l = mid + 1;
            }
            q[tl].r = p - 1;
        }
        if (p <= n)
            q[++tl] = (Node){i, p, n};
    }
}
void solve2()
{
    hd = 1, tl = 0;
    q[++tl] = (Node){n, 1, n};
    for (int i = n - 1; i; i--)
    {
        while (hd <= tl && q[hd].l > i)
            hd++;
        g[i] = cal2(q[hd].p, i);
        int p = 0;
        while (hd <= tl && cal2(i, q[tl].r) > cal2(q[tl].p, q[tl].r))
            p = q[tl--].r;
        if (hd <= tl && cal2(i, q[tl].l) > cal2(q[tl].p, q[tl].l))
        {
            int l = q[tl].l, r = q[tl].r;
            while (l <= r)
            {
                int mid = l + r >> 1;
                cal2(i, mid) > cal2(q[tl].p, mid) ? (p = mid, l = mid + 1) : r = mid - 1;
            }
            q[tl].l = p + 1;
        }
        if (p)
            q[++tl] = (Node){i, 1, p};
    }
}
int main()
{
    read(n);
    for (int i = 1; i <= n; i++)
        read(w[i]);
    solve1(), solve2();
    for (int i = 1; i <= n; i++)
        printf("%d\n", max(0, (int)max(ceil(f[i]), ceil(g[i]))));
    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
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
55
56
57
58
59
60
61
62
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type>
void write(Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar(x % 10 + '0');
}
const int N = 5e5 + 10;
int n, w[N];
double f[N], g[N];
void solve1 (int l, int r, int L, int R)
{
    if (l > r)
        return;
    int mid = l + r >> 1, p = mid;
    f[mid] = w[mid];
    for (int i = L; i <= min(R, mid - 1); i++)
    {
        double t = w[i] + sqrt(mid - i);
        t > f[mid] && (f[mid] = t, p = i);
    }
    solve1(l, mid - 1, L, p), solve1(mid + 1, r, p, R);
}
void solve2 (int l, int r, int L, int R)
{
    if (l > r)
        return;
    int mid = l + r >> 1, p = mid;
    g[mid] = w[mid];
    for (int i = max(L, mid + 1); i <= R; i++)
    {
        double t = w[i] + sqrt(i - mid);
        t > g[mid] && (g[mid] = t, p = i);
    }
    solve2(l, mid - 1, L, p), solve2(mid + 1, r, p, R);
}
int main ()
{
    read(n);
    for (int i = 1; i <= n; i++)
        read(w[i]);
    solve1(1, n, 1, n), solve2(1, n, 1, n);
    for (int i = 1; i <= n; i++)
        write(max(0, (int)ceil(max(f[i], g[i])) - w[i])), puts("");
    return 0;
}
相关文章