TIOJ 2285：花花世界

10月 05, 2022

TIOJ 2285：花花世界

題目大意：給你 $a_0\sim a_n,\ b_1\sim b_n,\ m_1\sim m_n$，$F_i = \max\limits_{\max(0, b_i - k + 1)\leq j \leq b_i}(F_j + (a_i - a_j + 1)\times m_i)$，請你輸出 $\sum\limits_{i = 0}^n F_i\ (\text{mod }1020050909)$。

解法：式子可以寫成 $F_i = (-a_j)\times m_i + F_j + (a_i + 1)\times m_i$，可以用斜率優化，但是因為斜率、查詢不單調，要用李超線段樹。如果用線段樹套李超線段樹要 $O(n\times\log^2(n))$，會 $\text{TLE}$，所以要壓到 $O(n\times\log(n))$。可以觀察到區間固定都是 $k$，如果我們每 $k$ 個分一塊，那每個區間都會剛好蓋住一個分界點，我們照分界點向右插入線段，向左插入線段，就可以 $O(n\times\log(n))$ 了！

$\text{Code：}$

#pragma GCC optimize("O3")
#pragma GCC target("popcnt")
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int MOD = 1020050909;
const ll INF = 5e18;
const int SIZE = 1e6 + 5;
const int MAX = 1e6;

struct Line {
    int m = 0;
    ll k = -INF;
    Line() {}
    Line (int m, ll k) : m (m), k (k) {}
    ll operator () (int x) {
        return 1ll * m * x + k;
    }
};

struct Node {
    Line line;
    int ls, rs;
    Node() {}
    Node (Line line) : ls (0), rs (0), line (line) {}
} node[SIZE];

int root, cnt;

int newnode (Line line) {
    node[++cnt] = Node (line);
    return cnt;
}

void Ins (int &pos, int l, int r, Line line) {
    if (pos == 0) {
        pos = newnode (line);
        return;
    }
    Node &nd = node[pos];
    if (l == r) {
        if (line (l) > nd.line (l)) swap (line, nd.line);
        return;
    }
    int mid = (l + r) / 2;
    if (line (mid) > nd.line (mid)) swap (line, nd.line);
    if (line.m <= nd.line.m) Ins (nd.ls, l, mid, line);
    else Ins (nd.rs, mid + 1, r, line);
}

ll Que (int pos, int l, int r, int x) {
    if (pos == 0) return -INF;
    Node nd = node[pos];
    if (l == r) return nd.line (x);
    int mid = (l + r) / 2;
    return max (nd.line (x), x <= mid ? Que (nd.ls, l, mid, x) : Que (nd.rs, mid + 1, r, x));
}

int n, k;
ll ans, dp[SIZE];
vector<int> L[SIZE], R[SIZE];
int a[SIZE], b[SIZE], m[SIZE];

int main() {
    ios::sync_with_stdio (false), cin.tie (0);
    cin >> n >> k;
    for (int i = 0; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    for (int i = 1; i <= n; i++) cin >> m[i];
    for (int i = 1; i <= n; i++) {
        int l = max (0, b[i] - k + 1), r = b[i];
        L[l].emplace_back (i);
        R[r].emplace_back (i);
        dp[i] = -INF;
    }
    for (int i = 0; i <= n; i++) {
        if (i % k == 0) {
            int l = max (0, i - k + 1), r = i;
            root = cnt = 0;
            while (r >= l) {
                Ins (root, 0, MAX, Line (-a[r], dp[r]));
                for (int pos : L[r]) {
                    dp[pos] = max (dp[pos], Que (root, 0, MAX, m[pos]) + 1ll * m[pos] * (a[pos] + 1));
                }
                r--;
            }
            root = cnt = 0;
        }
        Ins (root, 0, MAX, Line (-a[i], dp[i]));
        for (int pos : R[i]) {
            dp[pos] = max (dp[pos], Que (root, 0, MAX, m[pos]) + 1ll * m[pos] * (a[pos] + 1));
        }
        ans += dp[i] % MOD;
    }
    cout << ans % MOD << '\n';
}