毒瘤题目

主要思路：线段树（权值线段树）

可能很多同学做题之前会看一下题目标签。

这题的题目标签就是线段树与平衡树，然而写不出来以后，一看题解里全是STL，一脸茫然，，，

我这里是一篇正了八经的线段树解法。

首先我们要看清题： 

1.操作的编号一定不能看倒，不能理所当然

2.记得是有这么一句话：“如果加入的花朵价格已经与花束中已有花朵价格重复，则这一朵花不能加入花束。”一定不能忘了！！！

首先我们想一下如何插入删除。

我们看题目数据范围可知，W,C<=1000000，这就很好了，既然我们需要按最大最小排钱数，我们不如直接维护一个以花的价格为权值线段树所维护信息的序列。注意：权值线段树维护的是花的价格！

然后我们维护一个区间里的最大价格与最小价格，这样就可以方便2,3操作了。我们不是不能重复加入吗？那没关系，我们可以先把每个结点的区间内最大价格和最小价格分别设为-INF和INF，使得只要这个点中有一个数就可以改变之前初始化，那么我们在每次插入时，记得判断一下区间最大和区间最小和其中的价格权值是否是初始化状态就好了，如果不是初始化状态，就干脆不改了。

然后就是————

代码实现： 

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define go(i, j, n, k) for (int i = j; i <= n; i += k)
#define fo(i, j, n, k) for (int i = j; i >= n; i -= k)
#define rep(i, x) for (int i = h[x]; i; i = e[i].nxt)
#define mn 1000010
#define inf 2147483647
#define ll long long
#define ld long double
#define fi first
#define se second
#define root 1, 1000000, 1
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define bson l, r, rt
//#define LOCAL
#define mod 
#define Debug(...) fprintf(stderr, __VA_ARGS__)
inline int read(){
    int f = 1, x = 0;char ch = getchar();
    while (ch > '9' || ch < '0'){if (ch == '-')f = -f;ch = getchar();}
    while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
    return x * f;
}
//This is AC head above...
struct tree{
    int minn, maxx, sumw, sumc;
} z[mn << 2];
inline void update(int rt){
    z[rt].minn = min(z[rt << 1].minn, z[rt << 1 | 1].minn);
    z[rt].maxx = max(z[rt << 1].maxx, z[rt << 1 | 1].maxx);
    z[rt].sumw = z[rt << 1].sumw + z[rt << 1 | 1].sumw;
    z[rt].sumc = z[rt << 1].sumc + z[rt << 1 | 1].sumc;
}
inline void build(int l,int r,int rt){
    if(l == r) {
        z[rt].minn = inf;
        z[rt].maxx = -inf;
        z[rt].sumw = z[rt].sumc = 0;
        return;
    }
    int m = (l + r) >> 1;
    build(lson), build(rson), update(rt);
}
inline void modify_add(int l,int r,int rt,int c,int v){
    if(l == r) {
        if(z[rt].minn != inf || z[rt].maxx != -inf || z[rt].sumc){
            return;
        }
        z[rt].minn = z[rt].maxx = c;
        z[rt].sumw = v, z[rt].sumc = c;
        return;
    }
    int m = (l + r) >> 1;
    if(c <= m)
        modify_add(lson, c, v);
    else
        modify_add(rson, c, v);
    update(rt);
}
inline void modify_del(int l,int r,int rt,int c){
    if(l == r) {
        z[rt].minn = inf, z[rt].maxx = -inf;
        z[rt].sumw = z[rt].sumc = 0;
        return;
    }
    int m = (l + r) >> 1;
    if(c <= m)
        modify_del(lson, c);
    else
        modify_del(rson, c);
    update(rt);
}
int vis[mn], tot, s;
int main(){
    build(root);
    s = read();
    while(s != -1){
        if(s == 1){
            int x = read(), y = read();
            modify_add(root, y, x);
        }else if(s == 2){
            int maxx = z[1].maxx;
            modify_del(root, maxx);
        }else{
            int minn = z[1].minn;
            modify_del(root, minn);
        }
        s = read();
    }
    printf("%d %d\n", z[1].sumw, z[1].sumc);
#ifdef LOCAL
    Debug("\nMy Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC);
#endif
    return 0;
}