(luogu2073) 送花

发表于 分类于 ， ，

原题链接

思路:

使用权值树状数组.

插入操作先查找对应的位置值是不是 0, 然后插入.

删除操作二分查找最大值和最小值.

美丽值总和做个前缀和就行，至于总的价格在插入和删除的时候维护即可.

代码:

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
#include <cstdio>
#include <cstdlib>
typedef long long LL;
const int Mn(1000050);

class BinT {    //树状数组(我也不知道我为什么要建个类)
private:
    int len;    //树状数组长度
    LL* c;        //数组本体
    inline int lb(int x) {    //lowbit
        return x&(-x);
    }
public:
    explicit BinT(int n=Mn) {
        this->len = n;
        c = (LL*)malloc((n+1)*sizeof(LL));
    }
    void add(int p,LL x) {    //修改操作
        while(p<=len) {
            c[p] += x;
            p += lb(p);
        }
    }
    LL sum(int p) {            //查询前缀和
        LL ret(0);
        while(p) {
            ret += c[p];
            p -= lb(p);
        }
        return ret;
    }
}bt;

int main() {
    int opt;    //操作数
    LL prc(0);    //价值总和
    while(~scanf("%d",&opt)) {
        if(opt == -1) {
            break;
        } else if(opt == 1) {
            int x,y;
            scanf("%d %d",&x,&y);
            if(bt.sum(y)-bt.sum(y-1)==0) {    //是否可以插入
                bt.add(y,x);
                prc += y;
            }
        } else if(opt == 2) {
            if(bt.sum(Mn)==0) {
                continue;
            }
            int l(1),r(Mn);
            while(r-l>3) {    //二分查找最大值
                int mid((l+r)/2);
                if(bt.sum(r)-bt.sum(mid)>0) {    //如果右区间有值
                    l = mid+1;
                } else {
                    r = mid;
                }
            }
            /*二分区间长度较小时暴力查找, 避免边界问题*/
            for(int i(r);i>=l;--i) {
                LL tmp;
                if((tmp=bt.sum(i)-bt.sum(i-1))>0) {
                    bt.add(i,-tmp);
                    prc -= i;
                    break;
                }
            }
        } else if(opt == 3) {
            if(bt.sum(Mn)==0) {
                continue;
            }
            int l(1),r(Mn);
            while(r-l>3) {    //同样是二分
                int mid((l+r)/2);
                if(bt.sum(mid)==0) {
                    l = mid+1;
                } else {
                    r = mid;
                }
            }
            for(int i(l);i<=r;++i) {
                LL tmp;
                if((tmp=bt.sum(i)-bt.sum(i-1))>0) {
                    bt.add(i,-tmp);
                    prc -= i;
                    break;
                }
            }
        }
    }
    printf("%lld %lld",bt.sum(Mn),prc);
    return 0;
}