[ABC249F] Ignore Operations Solution

更好的阅读体验戳此进入

题面

存在变量 $x$$x$，初始时 $x=0$$x = 0$。给定 $n$$n$ 次操作按序进行，存在两种，1 y 表示 $x\leftarrow y$$x \leftarrow y$，2 y 表示 $x\leftarrow x+y$$x \leftarrow x + y$，你可以从中删除不超过 $k$$k$ 个操作，要求最大化操作后的 $x$$x$，输出最大值。

Solution

这题比 E 简单多了。。 观察发现如果有一个 $1$$1$ 操作被我们保留，那么它将覆盖所有在其之前的操作。所以我们不难想到可以考虑以每个 $1$$1$ 操作为分割点，考虑是否保留这个操作。

显然我们希望让这个东西无后效性，所以具体地，我们将整个操作逆序遍历。如果为 $2$$2$ 操作则记录，如果为 $1$$1$ 操作则先假设我们保留这个操作，那么之后的所有都可以忽略了。此时我们只需要在前面记录的所有 $2$$2$ 操作中的所有负数中找到前 $k$$k$ 小的将其删除，此时剩下的即为当前的最优操作。然后考虑如果不保留这个操作，此时首先需要保证 $k>0$$k > 0$，然后令 $k\leftarrow k-1$$k \leftarrow k - 1$，也就是将这个 $1$$1$ 操作删除，只剩下后面的 $2$$2$ 操作，然后按照刚才的做法继续遍历下去。

有个细节就是注意当删 $1$$1$ 操作的时候已经把 $k$$k$ 用完了之后，就应该直接 break 了，因为此时无法将当前的 $1$$1$ 删掉，自然后面的所有操作就无效了。

然后我们刚才找到前 $k$$k$ 小的和这个操作，不难想到用平衡树或者权值线段树就行。权值线段树比较好写一些，但是注意需要离散化做个映射。具体地，权值线段树维护每个位置有多少个数，以及区间和，查询的时候就是在权值线段树上二分即可。

显然这个东西的复杂度最坏是 $O(n\log n)$$O(n \log n)$ 的。

然后还有两个老生常谈的 AtCoder 独有的问题，一个就是 C++17 似乎不支持 basic_string < pair < int, int > >，大概的原因时 is_trivial < pair < int, int > >::value 为 false，所以会报 CE，这个东西在 [ABC248Ex] Beautiful Subsequences 题解 也提到过。然后就是 AtCoder 里面 data 似乎时保留字符。

Code

xxxxxxxxxx
103
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
template < typename T = int >
23
inline T read(void);
24

25
int N, K;
26
ll sum(0);
27
ll ans(LONG_LONG_MIN);
28
int mp[210000];
29
struct Pair{int first, second;};
30
basic_string < Pair > opt;
31
basic_string < int > _data;
32

33
class SegTree{
34
private:
35
    int tr[210000 << 2];
36
    ll sum[210000 << 2];
37
    #define LS (p << 1)
38
    #define RS (LS | 1)
39
    #define MID ((gl + gr) >> 1)
40
public:
41
    void Pushup(int p){
42
        tr[p] = tr[LS] + tr[RS];
43
        sum[p] = sum[LS] + sum[RS];
44
    }
45
    void Modify(int pos, int p = 1, int gl = 1, int gr = N){
46
        if(gl == gr)return tr[p]++, sum[p] += mp[pos], void();
47
        if(pos <= MID)Modify(pos, LS, gl, MID);
48
        else Modify(pos, RS, MID + 1, gr);
49
        Pushup(p);
50
    }
51
    ll Query(int K, int p = 1, int gl = 1, int gr = N){
52
        if(tr[p] <= K)return sum[p];
53
        if(gl == gr)return 0;
54
        if(tr[LS] > K)return Query(K, LS, gl, MID);
55
        else return sum[LS] + Query(K - tr[LS], RS, MID + 1, gr);
56
    }
57
}st;
58

59
int main(){
60
    // freopen("in.txt", "r", stdin);
61
    N = read(), K = read();
62
    opt += {1, 0};
63
    for(int i = 1; i <= N; ++i){
64
        int f = read(), v = read();
65
        opt += {f, v};
66
        if(f == 2)_data += v;
67
    }sort(_data.begin(), _data.end());
68
    _data.erase(unique(_data.begin(), _data.end()), _data.end());
69
    // N = _data.size();
70
    for(auto &op : opt){
71
        if(op.first == 1)continue;
72
        int dis = distance(_data.begin(), upper_bound(_data.begin(), _data.end(), op.second));
73
        mp[dis] = op.second, op.second = dis;
74
    }
75
    for(auto it = opt.rbegin(); it != opt.rend(); ++it){
76
        if(it->first == 1){
77
            ans = max(ans, (ll)it->second + sum - st.Query(K--));
78
            if(K < 0)break;
79
            // printf("cur, ans = %lld\n", it->second + sum - st.Query(K + 1));
80
        }else{
81
            sum += mp[it->second];
82
            if(mp[it->second] < 0)st.Modify(it->second);
83
        }
84
    }printf("%lld\n", ans);
85
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
86
    return 0;
87
}
88

89
template < typename T >
90
inline T read(void){
91
    T ret(0);
92
    int flag(1);
93
    char c = getchar();
94
    while(c != '-' && !isdigit(c))c = getchar();
95
    if(c == '-')flag = -1, c = getchar();
96
    while(isdigit(c)){
97
        ret *= 10;
98
        ret += int(c - '0');
99
        c = getchar();
100
    }
101
    ret *= flag;
102
    return ret;
103
}

UPD

update-2022_11_30 初稿