bzoj 1208 splay set

题

BZOJ

解

题意：有一堆人和宠物。同一时刻全是人或全是宠物，少数者单向选择。要选与满意值相差最少的一个，如果有两个相等选较小的。不满意值为所选值与满意值的差。求不满意值和。

一样是随便乱跑。
md又是set比自己写的快系列。

码

Splay（1980K, 6460ms）

#include <cstdio>
#include <algorithm>
using namespace std;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}

const int mod = 1000000, INF = 0x3f3f3f3f;

struct Node
{
    int v;
    int size;
    Node *ch[2];
    Node(int a = 0) : v(a), size(1) {ch[0] = ch[1] = NULL;}
} *root;

#define lc(o) (o -> ch[0])
#define rc(o) (o -> ch[1])
#define size(o) (o ? o -> size : 0)
#define v(o) (o -> v)

inline int cmp(Node *o, int k) {return size(lc(o)) == k - 1 ? -1 : (size(lc(o)) < k ? 1 : 0);}
inline void maintain(Node* &o){if(!o)return;o->size=size(lc(o))+size(rc(o))+1;}
inline void rotate(Node* &o, int d){Node*p=o->ch[d^1];o->ch[d^1]=p->ch[d];p->ch[d]=o;maintain(o);maintain(p);o=p;}

void splay(Node* &o, int k)
{
    if(!o)
        return;
    int d = cmp(o, k);
    if(d == 1)
        k -= size(lc(o)) + 1;
    if(d != -1)
    {
        Node *p = o -> ch[d];
        int d2 = cmp(p, k);
        int k2 = (d2 == 0 ? k : k - size(lc(p)) - 1);
        if(d2 != -1)
        {
            splay(p -> ch[d2], k2);
            if(d == d2)
                rotate(o, d ^ 1);
            else
                rotate(o -> ch[d], d);
        }
        rotate(o, d ^ 1);
    }
}


int t1;
void getless(Node* o, int k)
{
    if(!o) return;
    if(v(o) <= k)
    {
        t1 = v(o); getless(rc(o), k);
    }
    else
        getless(lc(o), k);
}

int t2;
void getmore(Node* o, int k)
{
    if(!o) return;
    if(v(o) >= k)
    {
        t2 = v(o); getmore(lc(o), k);
    }
    else
        getmore(rc(o), k);
}

int siz;
void insert(Node* &o, int k)
{
    if(!o)
    {
        o = new Node(k);
        siz ++;
        return;
    }
    if(v(o) <= k)
        insert(rc(o), k), siz += size(lc(o)) + 1;
    else
        insert(lc(o), k);
    maintain(o);
}

void del(Node* &o)
{
    if(!lc(o))
        o = rc(o);
    else if(!rc(o))
        o = lc(o);
    else
    {
        splay(rc(o), 1);
        lc(rc(o)) = lc(o);
        o = rc(o);
    }
    maintain(o);
}

void remove(Node* &o, int k)
{
    if(v(o) == k)
    {
        del(o);
    }
    else if(v(o) < k)
        remove(rc(o), k);
    else
        remove(lc(o), k);
    maintain(o);
}

int main()
{
    int n;
    read(n);
    int ans = 0, last;
    root = NULL;
    for(int i = 0; i < n; i++)
    {
        int a, b;
        read(a, b);
        siz = 0;

        if(!root)
        {
            last = a, insert(root, b);
            splay(root, siz);
        }
        else if(last == a)
        {
            insert(root, b);
            splay(root, siz);
        }
        else
        {
            t1 = -INF, t2 = INF;
            getless(root, b);
            getmore(root, b);
            if(b - t1 > t2 - b)
                ans += t2 - b, ans %= mod, remove(root, t2);
            else
                ans += b - t1, ans %= mod, remove(root, t1);
        }
    }
    printf("%d\n", ans);
    return 0;
}

set（956K, 152ms）

#include <cstdio>
#include <set>
#include <algorithm>
using namespace std;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}
const int INF = 0x3f3f3f3f, mod = 1000000;
set<int> st;
int main()
{
    st.insert(INF);
    st.insert(-INF);
    int n, last = -1, ans = 0;;
    read(n);
    while(n--)
    {
        int a, b;
        read(a, b);
        if(st.size() == 2)
            last = a, st.insert(b);
        else if(last == a)
            st.insert(b);
        else
        {
            set<int>::iterator l = --st.lower_bound(b), r = st.lower_bound(b);
            if(b - *l > *r - b)
                ans += *r - b, st.erase(r), ans %= mod;
            else
                ans += b - *l, st.erase(l), ans %= mod;
        }
    }
    printf("%d\n", ans);
    return 0;
}