题目链接：传送门

Description

这些花都很漂亮，每朵花有一个美丽值W，价格为C。 小明一开始有一个空的花束，他不断地向里面添加花。他有以下几种操作： 1 W C 添加一朵美丽值为W，价格为C的花。 3 小明觉得当前花束中最便宜的一朵花太廉价，不适合送给小红，所以删除最便宜的一朵花。 2 小明觉得当前花束中最贵的一朵花太贵，他心疼自己的钱，所以删除最贵的一朵花。 -1 完成添加与删除，开始包装花束 若删除操作时没有花，则跳过删除操作。 如果加入的花朵价格已经与花束中已有花朵价格重复，则这一朵花不能加入花束。 请你帮小明写一个程序，计算出开始包装花束时，花束中所有花的美丽值的总和，以及小明需要为花束付出的总价格

Input

若干行，每行一个操作，以-1结束。

Output

一行，两个空格隔开的正整数表示开始包装花束时，花束中所有花的美丽值的总和。以及小明需要为花束付出的总价格。

Sample Input

1 1 1 1 2 5 2 1 3 3 3 1 5 2 -1

Sample Output

8 5

Solution

再练习一道Splay的板子题，除了开始看反了价格和美丽值之外算是一遍A的吧:joy:

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <bits/stdc++.h>
using namespace std;
const int Maxn = 100000 + 100;
int N, root;
struct node
{
    int ch[2], size, fa, val, sum;
}Tree[Maxn];

inline int judge_dir (int x) { return Tree[Tree[x].fa].ch[1] == x; }

inline void Push_up (int x) { Tree[x].size = Tree[Tree[x].ch[0]].size + Tree[Tree[x].ch[1]].size + 1; }

inline void Connect(int x, int y, int dir) { Tree[x].fa = y; Tree[y].ch[dir] = x; }

inline void Rotate (int x)
{
    int f = Tree[x].fa, anc = Tree[f].fa, dirx = judge_dir(x), dirf = judge_dir(f);
    Connect(Tree[x].ch[dirx ^ 1], f, dirx);
    Connect(x, anc, dirf);
    Connect(f, x, dirx ^ 1);
    Push_up(f); Push_up(x);
}

inline void Splay (int x, int y)
{
    while (Tree[x].fa != y)
    {
        int f = Tree[x].fa, dirx = judge_dir(x), dirf = judge_dir(f);
        if (Tree[f].fa == y) Rotate(x);
        else if (dirx == dirf) Rotate(f), Rotate(x);
        else Rotate(x), Rotate(x);
    }
    if (!y) root = x;
}

inline void Create(int x, int v)
{
    if (!root)
    {
        Tree[++N].val = x; Tree[N].sum = v;
        Tree[N].size = 1; Tree[N].fa = 0;
        root = N;
        return ;
    }
    int now = root;
    while (1)
    {
        if (Tree[now].val == x)
            return ;
        now = Tree[now].ch[x > Tree[now].val];
        if (!now) break;
    }
    now = root;
    while (1)
    {
        Tree[now].size ++;
        int dir = x > Tree[now].val;
        if (!Tree[now].ch[dir])
        {
            Tree[++N].fa = now;
            Tree[N].size = 1;
            Tree[now].ch[dir] = N;
            Tree[N].val = x, Tree[N].sum = v;
            Splay(N, 0);
            return ;
        }
        now = Tree[now].ch[dir];
    }
}

inline void Delete(int type)
{
    if (!root) return ;
    int now = root;
    while (Tree[now].ch[type]) now = Tree[now].ch[type];
    Splay(now, 0);
    Tree[Tree[now].ch[type ^ 1]].fa = 0;
    root = Tree[now].ch[type ^ 1];
}

int Ans1 = 0, Ans2 = 0;

inline void Calc (int x)
{
    Ans1 += Tree[x].val;
    Ans2 += Tree[x].sum;
    if (Tree[x].ch[0]) Calc(Tree[x].ch[0]);
    if (Tree[x].ch[1]) Calc(Tree[x].ch[1]);
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);
#endif
    int type;
    while (1)
    {
        scanf("%d", &type);
        if (type == - 1) break;
        int x, y;
        if (type == 1)
        {
            scanf("%d%d", &x, &y);
            Create(y, x);
        }
        else if (type == 2) Delete(1);
        else Delete(0);
    }
    if (!root){cout<<0<<" "<<0<<endl; return 0;}
    Calc(root);
    cout<<Ans2<<" "<<Ans1<<endl;
    return 0;
}