题目传送门

做法：维护一棵Splay，如果现在来的是人，且还有宠物，那就找前驱和后缀与之差值的较小值，否则就加到树上。如果是宠物则同理。（这里的前驱后缀可以等于对应的值）

Code:

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
//Mystery_Sky
//
#define M 1000100
#define INF 0x3f3f3f3f
#define Mod 1000000
inline int read()
{
    int x=0,f=1; char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}

struct Splay{
    int cnt, size;
    int val;
    int fa, son[2];
}t[M];
int root, tot;
int n, opt, x;
int peo, ani, ans;

inline void push_up(int x) 
{
    if(x) {
        t[x].size = t[x].cnt;
        if(t[x].son[0]) t[x].size += t[t[x].son[0]].size;
        if(t[x].son[1]) t[x].size += t[t[x].son[1]].size;
    }
}
inline bool check(int x) {return t[t[x].fa].son[1] == x;}
inline void Clear(int x) {t[x].val = t[x].size = t[x].cnt = t[x].fa = t[x].son[0] = t[x].son[1] = 0;}
inline int New(int x, int fa) 
{
    t[++tot].val = x;
    t[tot].size = t[tot].cnt = 1;
    t[tot].son[0] = t[tot].son[1] = 0;
    t[tot].fa = fa;
    return tot;
}

inline void Rotate(int x)
{
    int y = t[x].fa, z = t[y].fa, k = check(x), w = t[x].son[k^1];
    t[y].son[k] = w; t[t[y].son[k]].fa = y;
    t[y].fa = x;
    t[x].son[k^1] = y;
    t[x].fa = z;
    if(z) t[z].son[t[z].son[1] == y] = x;
    push_up(y);
    push_up(x);
}

inline void splay(int x)//Splay->一直Rotate到根节点 
{
    for(int y; (y = t[x].fa); Rotate(x))
        if(t[y].fa) Rotate((check(x) == check(y) ? y : x));
    root = x;
}

inline void Insert(int x)
{
    if(!root) {
        root = New(x, 0);
        return;
    }
    int now = root, y = 0;
    while(1) {
        //printf("1\n");
        if(t[now].val == x) {
            t[now].cnt++;
            push_up(now), push_up(y);
            splay(now);
            break;
        }
        y = now;
        now = t[now].son[t[now].val < x];
        if(!now) {
            New(x, y);
            t[y].son[t[y].val < x] = tot;
            push_up(y);
            splay(tot);
            return;
        }
    }
}

inline int query_rank(int x)
{
    int ans = 0, now = root;
    while(1) {
        if(x < t[now].val) now = t[now].son[0];
        else {
            ans += t[t[now].son[0]].size;
            if(x == t[now].val) {
                splay(now);
                return ans + 1; 
            }
            ans += t[now].cnt;
            now = t[now].son[1];
        }
    }
}

inline int query_val(int rank)
{
    int now = root;
    while(1) {
        if(t[now].son[0] && rank <= t[t[now].son[0]].size) now = t[now].son[0];
        else {
            int temp = t[t[now].son[0]].size + t[now].cnt;
            if(rank <= temp) return t[now].val;
            rank -= temp;
            now = t[now].son[1];
        } 
    }
} 

inline int Pre()
{
    int now = t[root].son[0];
    while(t[now].son[1]) now = t[now].son[1];
    return now; 
}

inline int Succ()
{
    int now = t[root].son[1];
    while(t[now].son[0]) now = t[now].son[0];
    return now;
}

inline void Delete(int x)
{
    int q = query_rank(x);
    if(t[root].cnt > 1) {
        t[root].cnt--;
        push_up(root);
        return;
    }
    if(!t[root].son[0] && !t[root].son[1]) {
        Clear(root);
        root = 0;
        return;
    }
    if(!t[root].son[0]) {
        int y = root;
        root = t[y].son[1];
        t[root].fa = 0;
        Clear(y);
        return;
    }
    else if(!t[root].son[1]) {
        int y = root;
        root = t[y].son[0];
        t[root].fa = 0;
        Clear(y);
        return;
    }
    int lc = Pre(), y = root;
    splay(lc);
    t[t[y].son[1]].fa = root;
    t[root].son[1] = t[y].son[1];
    Clear(y);
    push_up(root);
    return;
}

int main() {
    n = read();
    Insert(INF), Insert(-INF);
    for(int i = 1; i <= n; i++) {
        opt = read(), x = read();
        if(opt == 0) {
            if(peo > 0) {
                Insert(x);
                if(t[root].cnt > 1) {
                    Delete(x);
                }
                else {
                    int pre = Pre();
                    int nxt = Succ();
                    int del_1 = abs(x - t[pre].val);
                    int del_2 = abs(t[nxt].val - x);
                    if(del_1 <= del_2) {
                        Delete(t[pre].val);
                        ans += del_1;
                        ans %= Mod;
                    }
                    else {
                        Delete(t[nxt].val);
                        ans += del_2;
                        ans %= Mod;
                    } 
                }
                Delete(x);
                peo--;
            }
            else Insert(x), ani++;
        }
        else {
            if(ani > 0) {
                Insert(x);
                if(t[root].cnt > 1) {
                    Delete(x);
                }
                else {
                    int pre = Pre();
                    int nxt = Succ();
                    int del_1 = abs(x - t[pre].val);
                    int del_2 = abs(t[nxt].val - x);
                    if(del_1 <= del_2) {
                        Delete(t[pre].val);
                        ans += del_1;
                        ans %= Mod;
                    }
                    else {
                        Delete(t[nxt].val);
                        ans += del_2;
                        ans %= Mod;
                    } 
                }
                Delete(x);
                ani--;
            }
            else Insert(x), peo++;
        }
    }
    printf("%d\n", ans);
    return 0;
}

洛谷 P2286 [HNOI2004]宠物收养场

原文：https://www.cnblogs.com/Benjamin-cpp/p/11537542.html