P4655[CEO2017]Building Bridges

Posted on Edited on In Word count in article: 781 Reading time ≈ 3 mins.
李超线段树好题

Building Bridges

\(CDQ\)分治

对, 这道题我的第一反应就是斜率优化

先推一波式子：

\[ \text{先令Dp[i]表示以i结尾的这一段的贡献, S[i]表示关于W[i]的一个前缀和}\\ \begin{align*} Dp[i] &= (h[i]-h[t])^2+S[i-1]-S[t]\\ Dp[j] &= (h[j]-h[t])^2+S[j-1]-S[t]\\ \end{align*}\\ \]

若\(Dp[j]>Dp[i]\), 那么有： \[ \begin{align*} (h[j]-h[t]^2)+S[j-1]-S[t]&>(h[i]-h[t]^2)+S[i-1]-S[t]\\ h[j]^2-2h[j]h[t]+h[t]^2+S[j-1]-S[t]&>h[i]^2-2h[i]h[t]+h[t]^2+S[i-1]-S[t]\\ h[j]^2-2h[j]h[t]+S[j-1]&>h[i]^2-2h[i]h[t]+S[i-1]\\ (h[j]+S[j-1])-(h[i]-S[i-1])&>2h[t]*(h[j]-h[i])\\ \frac{g[j]-g[i]}{h[j]-h[i]}&>2h[t] \end{align*} \] 那么这个式子要想写斜率优化的话，\(h\)数组要保证单调

嗯，就分治，排序，然后斜率\(Dp\)

时间复杂度

\(O(\log^2n)\)应该没有问题吧，没有写代码，口胡

李超线段树

？？？，怎么回事，看错题了？

没有，个人认为这才是正解！！！

再来看看我们的式子： \[ \begin{align*} Dp[i]&=(h[i]-h[t])^2+S[i-1]-S[t]+Dp[t]\\ &=h[i]^2-2h[i]h[t]+h[t]^2+S[i-1]-S[t]+Dp[t]\\ &=h[i]^2+S[i-1]+\min_{t=1}^{i-1}(h[t]^2-2h[t]h[i]-S[t]+Dp[t]) \end{align*} \] 看见其实对于我们的\(i\)，它的答案其实有一部分是定值，还有一部分与之前的信息相关联

那么我们可以新定义一个函数叫\(f_t(x)\)： \[ f_t(x)=-2h[t]\times x+h[t]^2-S[t]+Dp[t] \] 那么，原式可以化为 \[ Dp[i]=h[i]+S[i-1]+\min_{t=1}^{i-1}f_t(H[i]) \]

相当于是向一个坐标系中加入了很多条线段，问你在某个点时的最小值，是吧

此时，\(f_t(x)\)的斜率为\(-2h[t]\)，截距为\(h[t]^2-S[t]+Dp[t]\)

就可以了

Code

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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int Maxn = 1e5 + 10, L = 0, R = 1e6, MWi = 1e6 + 10;
ll K[Maxn], B[Maxn] = {1e18}, H[Maxn], W[Maxn], F[Maxn];\\B[0]一定要初始化，否则当x取0时，不会进行更新的
int S[MWi << 2], Qx, N;

inline ll Fx(int X, int Id)
{
    return K[Id] * X + B[Id];
}

void UpDate(int L, int R, int K, int X = 1)
{
    if (L == R)
    {
        if (Fx(L, K) < Fx(L, S[X])) S[X] = K;
        return ;
    }
    int Mid = L + R >> 1;
    if (Fx(Mid, K) < Fx(Mid, S[X])) swap(K, S[X]);
    if (Fx(L, K) < Fx(L, S[X])) UpDate(L, Mid, K, X << 1);
    else if (Fx(R, K) < Fx(R, S[X])) UpDate(Mid + 1, R, K, X << 1 | 1);
}

ll Query(int L, int R, int X = 1)
{
    if (L == R) return Fx(L, S[X]);
    int Mid = L + R >> 1;
    ll Temp = Fx(Qx, S[X]);
    if (Qx <= Mid) return min(Temp, Query(L, Mid, X << 1));
    return min(Temp, Query(Mid + 1, R, X << 1 | 1));
}

int main()
{
    scanf ("%d", &N);
    for (int i = 1; i <= N; ++i) scanf ("%lld", K + i);
    for (int i = 1; i <= N; ++i) scanf 
    ("%lld", W + i), W[i] += W[i - 1];
    B[1] = K[1] * K[1] - W[1];
    K[1] *= -2;
    UpDate (L, R, 1);
    for (int i = 2; i <= N; ++i)
    {
        Qx = K[i];
        F[i] = K[i] * K[i] + W[i - 1] + Query(L, R);
        B[i] = F[i] + K[i] * K[i] - W[i];
        K[i] *= -2;
        UpDate (L, R, i);
    }
    printf ("%lld\n", F[N]);
    system ("pause");
}