P5902

Nygglatho · 2025-07-02 00:07:45 · 题解

令 dp_{t,i} 表示时间为 t，此时在 i 结束的最大利润，m_{t,i} 表示时间 t 时 l 点展销会的盈利，若不存在展销会则 m_{t,i} 为 0。显然最后答案为 \max(\max\{dp_{T_{\max},i}+D\times (S-i)\mid i<S\},\max\{dp_{T_{\max},i}+U\times (i-S)\mid i\ge S\})。

先考虑没有两个展销会在同一天举行的情况。

转移分在上游和在下游转移，即：

• dp_{t,0}=\begin{cases}U\times (S-i)& i<S\\D\times (i-S)& i\ge S\end{cases}

然后考虑存在的情况。

显然一天内肯定是只朝一个方向走是最优的。

那么考虑分从上游到下游转移和从下游到上游转移。

令 f_{t,i} 表示钦定上游到下游转移，g_{t,i} 表示钦定从下游到上游转移，时间为 t，此时在 i 结束的最大利润，有：

这样是 O((L_{\max})^2\times T_{\max}) 的，考虑优化。

首先显然 dp_t 是只和 dp_{t-1} 有关的，因此可以滚动数组把 t 这一维删掉。然后就可以用四个线段树分别维护 \max\{f_{j}+D\times (i-j)\},\max\{dp_{j}+U\times (j-i)\},\max\{dp_{j}+D\times (i-j)\},\max\{g_{j}+U\times (j-i)\}，因为 D\times (i-j),U\times (j-i) 的相对大小是不改变的，每次只需要整体修改这个，查询合法部分的 \max，加入 f_j 和 g_j。最后再更新 dp_j，这样就把复杂度降到了 O(L_{\max}\log (L_{\max})\times T_{\max})。

然后可以发现对于 j 只需要在存在展销会的这几天更新 dp_j。否则更新 dp_j 时假如从 k 转移到 j，显然转移时直接找 dp_k 转移一定比找 dp_j 转移不劣，统计答案时同理。

那么只需要在线段树里存下 dp_j 的值，然后令 f_j,g_j\gets dp_j，如果这一天 j 存在展销会，那么就更新 f_j,g_j,dp_j，同时更新线段树里的值。复杂度 O(n\log L_{\max})。常数略大。

struct Info {
    int l; ll m;
} ;

vector <Info> v[N];
int n, s;
ll u, d;
constexpr int w = 500005;
ll dp1[N], dp2[N], dp[N], tmp[N];
struct Sgt {
    ll d[N << 2], b[N << 2];
    void Pd (int l, int r, int p) {
        int m = (l + r) >> 1;
        d[p << 1] += b[p], d[p << 1 | 1] += b[p], b[p << 1] += b[p], b[p << 1 | 1] += b[p], b[p] = 0LL;
    }
    void Add (int l, int r, int s, int t, int p, ll v) {
        if (l <= s && t <= r) {
            d[p] += v;
            b[p] += v;
            return ;
        }
        int m = (s + t) >> 1;
        Pd (s, t, p);
        if (l <= m) Add (l, r, s, m, p << 1, v);
        if (m < r) Add (l, r, m + 1, t, p << 1 | 1, v);
        d[p] = max (d[p << 1], d[p << 1 | 1]);
    }
    ll Qry (int l, int r, int s, int t, int p) {
        if (l <= s && t <= r) return d[p];
        int m = (s + t) >> 1;
        Pd (s, t, p);
        ll res = -inf;
        if (l <= m) res = Qry (l, r, s, m, p << 1);
        if (m < r) res = max (res, Qry (l, r, m + 1, t, p << 1 | 1));
        return res;
    }
    void Update (int x, ll v) {
        ll tmp = Qry (x, x, 0, w, 1);
        Add (x, x, 0, w, 1, v - tmp);
    }
} st1, st2; // 这里开的线段树重复使用，所以只开了两颗
int main () {
    // OPEN
    IOS
    cin >> n >> u >> d >> s;
    F (i, 1, n) {
        int t, l, m;
        cin >> t >> l >> m;
        v[t].push_back ({l, m});
    }
    int ls = s;
    F (i, 0, w) {
        if (i < s) dp[i] = - u * (s - i);
        else dp[i] = - d * (i - s);
        dp1[i] = dp2[i] = -inf;
    }
    F (i, 0, w) st1.Add (i, i, 0, w, 1, - d * (ls - i) + dp[i]);
    F (i, 0, w) st2.Add (i, i, 0, w, 1, - u * (i - ls) + dp[i]);
    F (t, 1, 500000) {
        sort (v[t].begin (), v[t].end (), [] (Info x, Info y) {return x.l < y.l; });
        for (auto [l, m] : v[t]) tmp[l] = dp[l];
        for (auto [l, m] : v[t]) {
            st1.Add (0, w, 0, w, 1, d * (ls - l));
            st2.Add (0, w, 0, w, 1, u * (l - ls));
            ls = l;
            ll tmp1 = dp1[l];
            dp1[l] = max (st1.Qry (0, l - 1, 0, w, 1), st2.Qry (l + 1, w, 0, w, 1)) + m;
            st1.Update (l, max (dp1[l], tmp1));
            st2.Update (l, max (dp1[l], tmp1));
        }
        for (auto [l, m] : v[t]) st1.Update (l, tmp[l] - d * (ls - l)), st2.Update (l, tmp[l] - u * (l - ls));
        sort (v[t].begin (), v[t].end (), [] (Info x, Info y) {return x.l > y.l; });
        for (auto [l, m] : v[t]) {
            st1.Add (0, w, 0, w, 1, d * (ls - l));
            st2.Add (0, w, 0, w, 1, u * (l - ls));
            ls = l;
            ll tmp1 = dp2[l];
            dp2[l] = max (st1.Qry (0, l - 1, 0, w, 1), st2.Qry (l + 1, w, 0, w, 1)) + m;
            st1.Update (l, max (dp2[l], tmp1));
            st2.Update (l, max (dp2[l], tmp1));
        }
        for (auto [l, m] : v[t]) dp[l] = max (dp[l], max (dp1[l], dp2[l]));
        for (auto [l, m] : v[t]) st1.Update (l, dp[l] - d * (ls - l)), st2.Update (l, dp[l] - u * (l - ls));
        for (auto [l, m] : v[t]) dp1[l] = dp2[l] = -inf;
    }
    ll ans = 0LL;
    F (i, 1, 500000) {
        if (i < s) ans = max (ans, dp[i] - d * (s - i));
        else ans = max (ans, dp[i] - u * (i - s));
    }
    cout << ans << '\n';
}