P1486 [NOI2004] 郁闷的出纳员

简要题意

给定 $n$ 次操作和一个阈值 $min$，每次操作包含一个字符 $opt$ 和一个整数 $k$，操作可以是一下四种之一：

  • I k 如果 $k$ 小于 $min$ 不操作，否则将 $k$ 扔进一个集合 $s$ 中。
  • A K 把 $s$ 里所有元素值加上 $k$。
  • S k 把 $s$ 里所有元素值减去 $k$。
  • F k 查询 $s$ 里第 $k$ 大的值，如果 $k > \left | s \right | $ 输出 -1。

在每次操作中，一旦 $s$ 中有元素的值低于阈值 $min$，就要删除这个元素，程序最后要输出删除的元素总数（插入时就因为小于阈值没有插入进来的不算）

策略分析

我们看到插入，删除，查询排名理所当然地想到了平衡树；看到全加上，全减去，理所当然地想到了线段树。但是很显然，这题肯定不是树套树。我们考虑，既然是全部加，单点查，我们其实并不用关心每个元素的更改，因为集体的更改不会导致排名的变化，只会影响我们后查询值，所以我们可以把这种更改用一个变量 $tag$ 记下来。

插入

在新插入元素的时候，我们要先对插入的元素减去 $tag$，这样做是为了消除其对插入的值的排名的影响。当我们输出的时候，因为这一部分的值刚好被抵消，所以加上的就是插入它以后对它操作的值，满足题目的要求。与此同时我们要拿一个 $sum$ 来记一共插入了多少次，拿一个 $cnt$ 来记当前集合中的元素个数。

元素加减

增加元素必然是直接加到 $tag$ 上就好了，但是为了维护集合内小于阈值的数的个数并成功把他们删除，我们必须要同步更改 $min$，如果集体增加就要下调 $min$，集体减少就要上调 $min$。每次减少的时候我们要进行删除操作，我们在平衡树上不断寻找 $min$ 的前驱并删除（一个数的前驱定义为小于它的最大的数），直到删完为止。

查询

查询直接查就好了，需要注意的是平衡树查排名的时候查的是第 $k$ 小，而我们查的是第 $k$ 大，所以查的时候要传的参数是 $cnt - k + 1$。在这里我们不建议更改平衡树的代码，因为平衡树细节较多码量较大，如果在考场上改写可能会导致不必要的错误以及浪费更多时间，除非万不得已，否则建议只在传参上调整。最后只需要输出总的插入次数减去当前集合的大小就是被删掉的元素个数。

参考代码

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
117
118
119
120
121
122
123
124
125
126
127
128
#include <iostream>
#include <cstdio>
#include <random>
#include <ctime>
#include <limits.h>
#define LL long long
using namespace std;

namespace SHAWN {
    const int N = 2e5 + 7;
    mt19937 rd(time(nullptr));
    namespace Treap {
        #define ls son[ro][1]
        #define rs son[ro][0]
        int cont, root;
        int son[N][2], pre[N], size[N], cnt[N]; LL val[N];
        void update(int ro) {
            if (!ro) { return; }
            size[ro] = cnt[ro];
            if (ls) { size[ro] += size[ls]; }
            if (rs) { size[ro] += size[rs]; } 
        }
        void rotate(int ro, int fa, int opt) {
            int s = son[ro][opt];
            son[ro][opt] = son[s][!opt];
            son[s][!opt] = ro;
            if (!fa) { root = s; }
            else { son[fa][son[fa][1] == ro] = s; } 
            update(ro); update(s);
        }
        void insert(int ro, int fa, LL x) {
            if (!ro) {
                ro = ++cont;
                cnt[ro] = 1; val[ro] = x;
                pre[ro] = rd() % INT_MAX;
                update(ro);
                if (!fa) { root = ro; }
                else { son[fa][x < val[fa]] = ro; }
            }
            else {
                if (x == val[ro]) { ++cnt[ro]; update(ro); }
                else if (x < val[ro]) {
                    insert(ls, ro, x); update(ro);
                    if (pre[ls] < pre[ro]) { rotate(ro, fa, 1); }
                }
                else {
                    insert(rs, ro, x); update(ro);
                    if (pre[rs] < pre[ro]) { rotate(ro, fa, 0); }
                }
            }
        }
        void del(int ro, int fa, LL x) {
            if (!ro) { return; }
            if (x == val[ro]) {
                --cnt[ro];
                if (!cnt[ro]) {
                    int f = fa, s;
                    update(ro);
                    while(ls && rs) {
                        if (pre[ls] < pre[rs]) { s = ls; rotate(ro, f, 1); f = s; }
                        else { s = rs; rotate(ro, f, 0); f = s; }
                    }
                    while (ls) { s = ls; rotate(ro, f, 1); f = s; }
                    while (rs) { s = rs; rotate(ro, f, 0); f = s; }
                    if (root == ro) { root = 0; }
                    else { son[f][son[f][1] == ro] = 0; }
                }
                update(ro);
            }
            else {
                if (x < val[ro]) { del(ls, ro, x); update(ro); }
                else { del(rs, ro, x); update(ro); }
            }
        }
        LL find_pre(int ro, LL x) {
            if (!ro) { return LONG_LONG_MIN; }
            else if (x > val[ro]) { return max(val[ro], find_pre(rs, x)); }
            else { return find_pre(ls, x); }
        }
        LL get_num(int ro, int x) {
            if (x <= size[ls]) { return get_num(ls, x); }
            else if (x <= size[ls] + cnt[ro]) { return val[ro]; }
            else { return get_num(rs, x - size[ls] - cnt[ro]); }
        }
        void insert(LL x) { insert(root, 0, x); }
        void del(LL x) { del(root, 0, x); }
        LL findpre(LL x) { return find_pre(root, x); }
        LL getnum(int x) { return get_num(root, x); }
        #undef ls
        #undef rs
    }

    int n; LL _min, tag, cnt, sum;
    signed work()
    {
        cin >> n >> _min;
        for (int i = 1; i <= n; ++i) { 
            char opt; LL k; cin >> opt >> k;
            if (opt == 'I') {
                if (k - tag >= _min) {
                    Treap :: insert(k - tag);
                    ++cnt; ++sum;
                }
            }
            else if (opt == 'A') { _min -= k; tag += k; }
            else if (opt == 'S') {
                _min += k; tag -= k;
                LL tmp;
                while ((tmp = Treap :: findpre(_min)) != LONG_LONG_MIN) {
                    Treap :: del(tmp);
                    --cnt;
                }
            }
            else if (opt == 'F') {
                if (cnt < k) { cout << "-1\n"; }
                else { cout << Treap :: getnum(cnt - k + 1) + tag << '\n'; }
            }
        }
        cout << sum - cnt << '\n';
        return 0;
    }
}

signed main() {
    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    return SHAWN :: work();
}

说些什么吧！

twikoo