【bzoj1208】[HNOI2004]宠物收留所

传送门：戳这里看原题

解题思路

这道题其实是第二次写了，听了金牌爷XZH的STL安利大会，对于set这个阉割版的核武器重拾自信。
所以吧，我拿这道当年splay的一血……练手……-_-||
个人感觉，对STL的更熟练掌握，是建立在对C++的运行、编译方式的深刻理解上的。
当年觉得自己splay写的妙极，现在大力打脸。

代码

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define red(i, a, b) for(int i = (a); i >= (b); i--)
#define ll long long

const int mod = 1000000;
const int INF = 2000000000;
int n, ans;
bool flag;
set<int> T;

int main() {
    scanf("%d", &n);
    T.insert(-INF);
    T.insert(INF);
    while(n--) {
        int tag, data;
        scanf("%d%d", &tag, &data);
        if (T.size() == 2) {
            flag = tag;
            T.insert(data);
        }
        else if (tag != flag) {
            int small = *--T.lower_bound(data);
            int big = *T.lower_bound(data);
            if (data - small <= big - data && small > -INF) {
                ans = (ans + data - small) % mod;
                T.erase(small);
            }
            else {
                ans = (ans + big - data) % mod;
                T.erase(big);
            }
        }
        else T.insert(data);
    }
    printf("%d\n", ans);
    return 0;
}

尾声

虽然用set写的很舒服，但当时这道题的确对我理解splay起了很大帮助
回忆向……继续加油吧

End.