P10538 [APIO2024] 星际列车

· · 题解

献给我死去的 APIO2024。

显然要 dp，也就是 f_i 表示经过边 i，到达点 Y_i 的最少代价。方便起见，我们多加两个起点到起点（0 时刻到 0 时刻，代价为 0），终点到终点（\infin 时刻到 \infin 时刻，代价为 0）的边，编号为 0 和 m+1。于是我们要求的就是 f_{m+1}。有转移方程：

f_i=C_i+\min_{X_i=Y_j,B_j\le A_i}f_j+T_{X_i}\cdot w(B_j+1,A_i-1)

其中 cost(l,r) 表示被 [l,r] 完全包含的 [L[i],R[i]] 个数。

我们维护两个边集 e 和 ej，一个是所有我们要计算 f_i 的 i，一个是当前可以被转移的 j。显然地，e 按照 A_i 排序，ej 按照 B_j 排序，这样每次我们的决策点与被决策点都是一段前缀，使用双指针很好处理，也方便理解决策单调性。

通过上面的方程可以推出转移具有决策单调性。具体地，若 i_1\lt i_2，e_{i_1} 的最优决策点为 p_1（即，从 ej_{p_1} 转移过来），e_{i_2} 的最优决策点为 p_2，则 p_1\le p_2。

处理决策单调性 dp 的方法是二分队列。很不幸我 APIO 之前并不会这个 trick。其过程如下：

维护结构体队列，结构体形如 (j,l,r)，表示 j 决策点可以决策 [l,r] 这段区间。

但是由于方程中还有一个 Y_i=X_j 的限制，所以要对每个结点都维护一个上述队列。同时，(j,l,r) 的含义也有改动：表示当前所在队列对应结点 u 可以转移到的 i 是第 l 个到第 r 个（起点与当前结点相同的），必要时再套一个二分即可。至于 cost(l,r) 的计算，可以离散化所有时间戳后使用主席树维护。于是总复杂度为 \Theta(n\log ^2n)。

shitcode:

struct edge {
    int u, v, p, q, w, id;
};

struct op {
    int j, l, r;
};

struct QwQ {
    vector<op> q;
    int hd = 0, tl = -1;
    void push_back(op x) { q.push_back(x), ++tl; }
    void pop_back() { q.pop_back(), --tl; }
    bool empty() { return hd > tl; }
    op& front() { return q[hd]; }
    op& back() { return q[tl]; }
    void pop_front() { hd++; }
};

struct node {
    int ch[2] = {};
    int sum = 0;
};

node tr[maxn * 22];
int rt[maxn], tot;

void modify(int &u, int pre, int l, int r, int p, int k) {
    tr[u = ++tot] = tr[pre];
    if (l == r) {
        tr[u].sum += k;
        return;
    }
    if (p <= mid) modify(ls, tr[pre].ch[0], l, mid, p, k);
    else modify(rs, tr[pre].ch[1], mid + 1, r, p, k);
    tr[u].sum = tr[ls].sum + tr[rs].sum;
}

int query(int u, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return tr[u].sum;
    int ans = 0;
    if (ql <= mid) ans += query(lc, ql, qr);
    if (qr > mid) ans += query(rc, ql, qr);
    tr[u].sum = tr[ls].sum + tr[rs].sum;
    return ans;
}

ll solve(int n, int m, int w, vi t, vi x, vi y, vi a, vi b, vi c, vi l, vi r) {
    vector<edge> e (m + 2), ej (m + 2); vector<ll> f (m + 2);
    vector<QwQ> que(n); vector<int> buc;
    vector<pii> rg;
    e[0] = {0, 0, 0, 0, 0, 0};
    f[0] = 0;
    rep(i, 0, m - 1) e[i + 1] = {x[i], y[i], a[i], b[i], c[i], i + 1};
    e[m + 1] = {n - 1, n - 1, (int) 1e9 + 1, (int) 1e9 + 2, 0, m + 1};
    rep(i, 0, m + 1) b.push_back(e[i].p), b.push_back(e[i].q);
    rep(i, 0, w - 1) b.push_back(l[i]), b.push_back(r[i]);
    sort(b.begin(), b.end());
    b.resize(unique(b.begin(), b.end()) - b.begin());
    rep(i, 0, m + 1) {
        e[i].p = lower_bound(b.begin(), b.end(), e[i].p) - b.begin() + 1;
        e[i].q = lower_bound(b.begin(), b.end(), e[i].q) - b.begin() + 1;
    }
    rep(i, 0, w - 1) {
        l[i] = lower_bound(b.begin(), b.end(), l[i]) - b.begin() + 1;
        r[i] = lower_bound(b.begin(), b.end(), r[i]) - b.begin() + 1;
        rg.push_back({r[i], l[i]});
    }
    sort(rg.begin(), rg.end());
    rep(i, 0, w - 1) modify(rt[i + 1], rt[i], 0, b.size() + 5, rg[i].sc, 1);
    rep(i, 1, m + 1) f[i] = inf;
    ej = e;
    sort(e.begin(), e.end(), [] (edge x, edge y) {
        return x.p < y.p;
    });
    sort(ej.begin(), ej.end(), [] (edge x, edge y) {
        return x.q < y.q;
    });
    vector<vector<int>> qaq (n);
    rep(i, 0, m + 1) qaq[e[i].u].push_back(i);
    auto val = [&] (int i, int j) -> ll {
        ll ans = f[ej[j].id] + e[i].w;
        int l = ej[j].q + 1, r = e[i].p - 1;
        ll cnt = 0; pii tmp = {r, 1e9};
        auto id = upper_bound(rg.begin(), rg.end(), tmp) - rg.begin();
        cnt = query(rt[id], 0, b.size() + 5, l, b.size() + 5);
        return min(ans + cnt * t[e[i].u], inf);
    };
    int mxj = 0;
    rep(i, 1, m + 1) {
        while (mxj <= (int) ej.size() - 1 && ej[mxj].q <= e[i].p) {
            int x = ej[mxj].v;
            while (!que[x].empty() && val(qaq[x][que[x].back().l], mxj) <= val(qaq[x][que[x].back().l], que[x].back().j)) que[x].pop_back();
            if (que[x].empty()) {
                int pos = lower_bound(qaq[x].begin(), qaq[x].end(), i) - qaq[x].begin();
                if (pos < qaq[x].size()) que[x].push_back({mxj, pos, (int) qaq[x].size() - 1});
                ++mxj;
                continue;
            }
            int l = que[x].back().l, r = que[x].back().r + 1;
            while (l < r) {
                if (val(qaq[x][mid], mxj) <= val(qaq[x][mid], que[x].back().j)) r = mid;
                else l = mid + 1;
            }
            que[x].back().r = l - 1;
            if (l < qaq[x].size()) que[x].push_back({mxj, l, (int) qaq[x].size() - 1});
            ++mxj;
        }
        int x = e[i].u;
        while (!que[x].empty() && qaq[x][que[x].front().r] < i) que[x].pop_front();
        int g = -1;
        if (!que[x].empty()) {
            int j = que[x].front().j;
            f[e[i].id] = min(f[e[i].id], val(i, j));
            g = j;
            que[x].front().l = lower_bound(qaq[x].begin(), qaq[x].end(), i) - qaq[x].begin();
        }
    }
    return f[m + 1] == inf ? -1 : f[m + 1];
}