题解：P13532 [OOI 2023] Buying gifts / 购买礼物

cjrqwq · 2025-09-04 21:15:51 · 题解

我们考虑固定 a 的最大值，来通过某些数据结构维护 b。

把 a 从小到大排序，遍历。设当前的最大值为 a_x。那比 a_x 小的 a_i 的选择是可以选 a_i，也可以选 b_i，选 a_i 对答案无影响，b_i 会影响答案，所以我们要尝试使用 b_i 更新答案。比 x 大的 a_j 是必须选择 b_j，否则与固定 a_x 矛盾。

所以对于 i 需要维护 b 中的前驱，后继。对于 j 需要维护 b 中的最大值。

具体而言，对于 i，我们使用 std::set。找到与 a_x 在数轴上最近的 b_i。 对于 j。我们可以使用线段树（单点修改，查询全局最大），或者优先队列（每次标记 x 失效，查询第一个有效的最大值）。

时间复杂度 O(n\log n)。

#include<bits/stdc++.h>
using namespace std;
constexpr int N = 2e5+10;
int n,a[N],b[N];

struct Node{
    int val,ma;
}c[N<<2];
#define mid (l+r)/2
#define ls (u*2)
#define rs (u*2+1)
void pushup(int u) {
    c[u].ma = max(c[ls].ma, c[rs].ma);
}
void build(int u,int l,int r) {
    if (l == r) {
        c[u].val = c[u].ma = b[l];
        return ;
    }
    build(ls,l,mid), build(rs,mid+1,r);
    pushup(u);
}
void upd(int u,int l,int r,int x,int v) {
    if (l == r) {
        c[u].val = c[u].ma = v;
        return ;
    }
    if (x <= mid) upd(ls,l,mid,x,v);
    else upd(rs,mid+1,r,x,v);
    pushup(u);
}
int mp[N];
void slove() {
    cin>>n;
    set<int>s;
    for (int i=1;i<=n;i++) {
        cin>>a[i]>>b[i];
    }
    build(1,1,n);
    iota(mp+1,mp+n+1,1);
    sort(mp+1,mp+n+1,[](int x,int y) {
        return a[x] < a[y];
    });
    int mxA = 0, ans = 2e9;
    for (int i=1;i<=n;i++) {
        mxA = a[mp[i]];
        upd(1,1,n,mp[i],0);
        auto it = s.lower_bound(mxA);
        if (it != s.end()) {
            int x = *it;
            if (x > c[1].ma) {
                ans = min(ans, abs(mxA - x));
            }
        }
        if (it != s.begin()) {
            int x = *prev(it);
            if (x > c[1].ma) {
                ans = min(ans, abs(mxA - x));
            }
        }
        ans = min(ans, abs(mxA - c[1].ma));
        s.insert(b[mp[i]]);
    }
    cout << ans << '\n';
}
int main() {
    cin.tie(nullptr) -> sync_with_stdio(false);
    int T=1;
    while(T--) {
        slove();
    }
    return 0;
}