题解：P13649 [NOISG 2016] Panda Ski

Register_int · 2026-01-21 19:13:24 · 题解

一血。

这个题就是两个题啊！火大。两个题我们分开做。

Part I：E_i 均相等。

设 E=E_i。先将 (X_i,Y_i)=(X_j,Y_j) 的缩成同一个点。

考虑朴素转移。将所有点按 (Y_i,X_i) 从小到大排序、容易发现，对于 Y 相等的两个点 i,j，若 i 能到达 j，则 j 也能到达 i。连边后同一个 y 构成若干个连续段，我们把每个连续段当成一个大点转移即可。处理掉这种情况后可以得出转移：

瓶颈在于一个矩形查询。因为 E 固定，可以直接对 Y_i 双指针，维护 X_i 的区间最大值即可。时间复杂度 \mathcal{O}(n\log n)。

struct node {
    int x, y; ll s; int e;
    node(int x = 0, int y = 0, ll s = 0, int e = 0) : x(x), y(y), s(s), e(e) {}
    bool operator < (const node &rhs) const { return y == rhs.y ? x < rhs.x : y < rhs.y; }
} a[MAXN];

int n, m;

namespace PartI {

    const int D = 5e4 + 1;

    ll t[MAXM << 2];

    inline void pushup(int p) { t[p] = max(t[p << 1], t[p << 1 | 1]); }

    void modify(int k, ll x, int l = 1, int r = D << 1, int p = 1) {
        if (l == r) return t[p] = x, void();
        int mid = l + r >> 1;
        if (k <= mid) modify(k, x, l, mid, p << 1);
        if (k > mid) modify(k, x, mid + 1, r, p << 1 | 1); pushup(p);
    }

    ll ask(int ql, int qr, int l = 1, int r = D << 1, int p = 1) {
        if (ql <= l && r <= qr) return t[p];
        int mid = l + r >> 1;
        if (qr <= mid) return ask(ql, qr, l, mid, p << 1);
        if (ql > mid) return ask(ql, qr, mid + 1, r, p << 1 | 1);
        return max(ask(ql, qr, l, mid, p << 1), ask(ql, qr, mid + 1, r, p << 1 | 1));
    }

    int p[MAXM]; ll dp[MAXN];

    inline 
    void solve() {
        sort(a + 1, a + n + 1);
        for (int i = 2; i <= n; i++) {
            if (a[i].x == a[i - 1].x && a[i].y == a[i - 1].y) {
                a[i + 1].s += a[i].s, a[i].e = 0;
            } 
        }
        for (int i = 1, j = 1; i <= n; i++) {
            if (!a[i].e) continue;
            for (; j < i && a[j].e; j++);
            if (j < i) swap(a[i], a[j]);
        }
        for (; !a[n].e; n--); int e = a[1].e;
        for (int i = 1; i <= n; i++) a[i].x += D;
        for (int i = 1, j = 1; i <= n; ) {
            for (; j < i && a[j].y < a[i].y - e; j++) {
                if (p[a[j].x] == a[j].y) modify(a[j].x, 0);
            }
            int k = i;
            for (; k < n && a[k + 1].y == a[k].y && a[k + 1].x - a[k].x <= e; k++);
            ll sum = 0, val = ask(a[i].x - e, a[k].x + e);
            for (int l = i; l <= k; l++) sum += a[l].s;
            for (int l = i; l <= k; l++) modify(a[l].x, dp[l] = sum + val);
            for (int l = i; l <= k; l++) p[a[l].x] = a[l].y; i = k + 1;
        }
        ll ans = 0;
        for (int i = 1; i <= n; i++) ans = max(ans, dp[i]);
        printf("%lld", ans);
    }

}

Part II：Y_i 互不相等。

还是写出转移：

仍然按 (Y_i,X_i) 从小到大排序，对 X 一维开线段树，我们希望在每个节点上维护 \ge Y_i-E_i 的所有 dp 值的最大值。对每个点开单调栈，查询时在单调栈上二分即可。时间复杂度 \mathcal{O}(n\log^2n)。

namespace PartII {

    const int D = 5e4 + 1;

    vector<pair<int, ll>> t[MAXM << 2];

    void modify(int x, int y, ll w, int l = 1, int r = D << 1, int p = 1) {
        for (; !t[p].empty() && t[p].back().second < w; t[p].pop_back());
        t[p].emplace_back(y, w);
        if (l == r) return ; int mid = l + r >> 1;
        if (x <= mid) modify(x, y, w, l, mid, p << 1);
        else modify(x, y, w, mid + 1, r, p << 1 | 1);
    }

    ll ask(int ql, int qr, int y, int l = 1, int r = D << 1, int p = 1) {
        if (ql <= l && r <= qr) {
            auto it = lower_bound(t[p].begin(), t[p].end(), make_pair(y, 0ll));
            return it == t[p].end() ? 0ll : it->second;
        }
        int mid = l + r >> 1;
        if (qr <= mid) return ask(ql, qr, y, l, mid, p << 1);
        if (ql > mid) return ask(ql, qr, y, mid + 1, r, p << 1 | 1);
        return max(ask(ql, qr, y, l, mid, p << 1), ask(ql, qr, y, mid + 1, r, p << 1 | 1));
    }

    inline 
    void solve() {
        sort(a + 1, a + n + 1); ll ans = 0;
        for (int i = 1; i <= n; i++) a[i].x += D;
        for (int i = 1; i <= n; i++) {
            ll w = a[i].s + ask(a[i].x - a[i].e, a[i].x + a[i].e, a[i].y - a[i].e);
            ans = max(ans, w), modify(a[i].x, a[i].y, w);
        }
        printf("%lld", ans);
    }

}