宠物收养所

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 4216 字
宠物与领养者交替到来；同一时刻收容所只有一种
一本通
练习
正文

/*
原题：T1566 「一本通 4.6 练习 1」宠物收养所（HNOI2004）
题意：宠物(a=0)与领养者(a=1)交替到来；同一时刻收容所只有一种。异类到来时，
匹配特点值最接近的一个并累加不满意度 |a-b|，对 1e6 取模。
思路：用一棵 Treap 维护当前在场的若干特点值。同类到来直接插入；异类到来时找前驱/后继中
绝对值差最小者（距离相等取较小值），累加后删除该值。若已有相同特点值则差为 0。
复杂度：时间 O(n log n)，空间 O(n)。
易错点：收容所始终只有一类，空时切换类型；删除的是“被匹配的那个”而非新来者；
答案对 1e6 取模。split/merge 用下标返回，避免 vector 重分配导致悬垂引用。
*/
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000;
struct Treap {
    struct Node {
        int l, r, pri, cnt, sz;
        long long key;
    };
    vector<Node> t;
    int root;
    Treap(){
        t.push_back({0, 0, 0, 0, 0, 0});
        root = 0;
    }
    int rnd(){
        return rand();
    }
    int newNode(long long key){
        t.push_back({0, 0, rnd(), 1, 1, key});
        return (int)t.size() - 1;
    }
    void upd(int x){
        if(x) t[x].sz = t[t[x].l].sz + t[t[x].r].sz + t[x].cnt;
    }
    pair<int, int> split(int x, long long key){
        if(!x) return {0, 0};
        if(t[x].key < key){
            auto p = split(t[x].r, key);
            t[x].r = p.first;
            upd(x);
            return {x, p.second};
        }else{
            auto p = split(t[x].l, key);
            t[x].l = p.second;
            upd(x);
            return {p.first, x};
        }
    }
    int merge(int L, int R){
        if(!L || !R) return L | R;
        if(t[L].pri > t[R].pri){
            t[L].r = merge(t[L].r, R);
            upd(L);
            return L;
        }else{
            t[R].l = merge(L, t[R].l);
            upd(R);
            return R;
        }
    }
    void insert(long long key){
        auto p = split(root, key);
        int L = p.first, R = p.second;
        auto p2 = split(R, key + 1);
        int M = p2.first, R2 = p2.second;
        if(M){
            t[M].cnt++;
            t[M].sz++;
        }else{
            M = newNode(key);
        }
        root = merge(merge(L, M), R2);
    }
    void eraseOne(long long key){
        auto p = split(root, key);
        int L = p.first, R = p.second;
        auto p2 = split(R, key + 1);
        int M = p2.first, R2 = p2.second;
        if(M){
            t[M].cnt--;
            t[M].sz--;
            if(t[M].cnt == 0) M = 0;
        }
        root = merge(merge(L, M), R2);
    }
    int kthIn(int x, int k){
        while(x){
            int ls = t[t[x].l].sz;
            if(k <= ls) x = t[x].l;
            else if(k <= ls + t[x].cnt) return (int)t[x].key;
            else {
                k -= ls + t[x].cnt;
                x = t[x].r;
            }
        }
        return -1;
    }
    long long pred(long long key){
        auto p = split(root, key);
        int L = p.first, R = p.second;
        long long res = -1;
        if(t[L].sz) res = kthIn(L, t[L].sz);
        root = merge(L, R);
        return res;
    }
    long long succ(long long key){
        auto p = split(root, key + 1);
        int L = p.first, R = p.second;
        long long res = -1;
        if(t[R].sz) res = kthIn(R, 1);
        root = merge(L, R);
        return res;
    }
    bool contains(long long key){
        auto p = split(root, key);
        int L = p.first, R = p.second;
        auto p2 = split(R, key + 1);
        int M = p2.first, R2 = p2.second;
        bool ok = (M != 0 && t[M].cnt > 0);
        root = merge(merge(L, M), R2);
        return ok;
    }
    int size(){
        return t[root].sz;
    }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    Treap tr;
    int curtype = -1;
    long long ans = 0;
    while(n--){
        int a;
        long long b;
        cin >> a >> b;
        if(tr.size() == 0){
            curtype = a;
            tr.insert(b);
        } else if(a == curtype){
            tr.insert(b);
        }else{
            long long p = tr.pred(b), s = tr.succ(b);
            long long best = LLONG_MAX;
            if(p != -1) best = min(best, b - p);
            if(s != -1) best = min(best, s - b);
            if(tr.contains(b)) best = 0;
            ans = (ans + best) % MOD;
            if(tr.contains(b)) tr.eraseOne(b);
            else if(p != -1 && (s == -1 || (b - p) <= (s - b))) tr.eraseOne(p);
            else tr.eraseOne(s);
        }
    }
    cout << ans << "\n";
    return 0;
}
宠物收养所

正文

一本通·提高篇的其它内容
