LYDSY 1208

题目大意

暂无

题目解法

暂无

RTFC

#include <cstdio>
#include <cstdlib>
#define sz(x) (x == 0 ? 0 : x->size)
#define update(x) \
    if (x) x->size = sz(x->child[0]) + sz(x->child[1]) + 1
#define getVal(x) (x == 0 ? 0 : x->val)
typedef int valType;
struct Node
{
    valType val;
    int size;
    Node *child[2], *father;
};
typedef Node *lpNode;
struct allocator
{
private:
    int i;
    Node *data;
    lpNode *pt;

public:
    allocator(int size)
    {
        data = new Node[size];
        pt = new lpNode[size];
        this->i = 0;
        for (int j = 0; j < size; j++) pt[j] = &data[j];
    }
    lpNode alloc(int x, lpNode f)
    {
        lpNode newNode = pt[i++];
        newNode->val = x;
        newNode->father = f;
        newNode->size = 1;
        newNode->child[0] = newNode->child[1] = 0;
        return newNode;
    }
    void free(lpNode ptr) { pt[--i] = ptr; }
};
lpNode root = 0;
allocator *mem;
struct SplayTree
{
private:
    void rotate(lpNode x)
    {
        if (x == 0 || x->father == 0) return;
        int d = (x == x->father->child[0]);
        lpNode y = x->father;
        y->child[!d] = x->child[d];
        if (x->child[d]) x->child[d]->father = y;
        x->father = y->father;
        if (y->father) y->father->child[y == y->father->child[1]] = x;
        y->father = x;
        x->child[d] = y;
        update(y);
        update(x);
    }
    void Splay(lpNode x, lpNode &target)
    {
        lpNode targetFather = target->father;
        while (x->father != targetFather)
            if (x->father == target)
                rotate(x);
            else if ((x->father->father->child[0] == x->father) == (x->father->child[0] == x))
                rotate(x->father), rotate(x);
            else
                rotate(x), rotate(x);
        target = x;
    }
    lpNode find(int x)
    {
        lpNode s = root;
        while (true)
            if (s == 0)
                return 0;
            else if (s->val == x)
            {
                Splay(s, root);
                return s;
            }
            else
                s = s->child[x > s->val];
    }
    lpNode join(lpNode x, lpNode y)
    {
        if (x == 0)
            return y;
        else
        {
            lpNode m = max_min(x, 1);
            Splay(m, x);
            m->child[1] = y;
            if (y) y->father = m;
            return x;
        }
    }

public:
    SplayTree(int _) { mem = new allocator(_); }
    int size() { return sz(root); }
    lpNode max_min(lpNode x, int i)
    {
        while (x && x->child[i]) x = x->child[i];
        return x;
    }
    void insert(int x)
    {
        if (root == 0)
            root = mem->alloc(x, 0);
        else
        {
            lpNode s = root, p = 0;
            while (s)
                p = s, s = s->child[x > s->val];
            s = mem->alloc(x, p);
            p->child[x > p->val] = s;
            Splay(s, root);
        }
    }
    void remove(int x)
    {
        lpNode p = find(x);
        if (p)
        {
            root = join(p->child[0], p->child[1]);
            if (root) root->father = 0;
            mem->free(p);
        }
    }
    lpNode pred(int x)
    {
        lpNode s = root, ans = 0;
        while (s)
            if (s->val < x)
                ans = s, s = s->child[1];
            else
                s = s->child[0];
        return ans;
    }
    lpNode succ(int x)
    {
        lpNode s = root, ans = 0;
        while (s)
            if (s->val > x)
                ans = s, s = s->child[0];
            else
                s = s->child[1];
        return ans;
    }
};
int main()
{
    SplayTree st(10001);
    int n, a, b, type, ans = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d%d", &a, &b);
        if (st.size() == 0) type = a;
        if (a == type)
            st.insert(b);
        else
        {
            lpNode pr = st.pred(b), su = st.succ(b);
            if (pr == 0)
            {
                ans += su->val - b;
                st.remove(su->val);
            }
            else if (su == 0)
            {
                ans += b - pr->val;
                st.remove(pr->val);
            }
            else
            {
                int d1 = su->val - b, d2 = b - pr->val;
                if (d1 < d2)
                {
                    ans += d1;
                    st.remove(su->val);
                }
                else
                {
                    ans += d2;
                    st.remove(pr->val);
                }
            }
        }
        ans %= 1000000;
    }
    printf("%d", ans);
    return 0;
}