[ABC249F] Ignore Operations Solution

• [ABC249F] Ignore Operations Solution
  • 更好的阅读体验戳此进入
  • 题面
  • Solution
  • Code
  • UPD

更好的阅读体验戳此进入

题面

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

Solution

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

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

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

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

显然这个东西的复杂度最坏是 $ 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

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

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

using namespace std;

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

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

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

int N, K;
ll sum(0);
ll ans(LONG_LONG_MIN);
int mp[210000];
struct Pair{int first, second;};
basic_string < Pair > opt;
basic_string < int > _data;

class SegTree{
private:
    int tr[210000 << 2];
    ll sum[210000 << 2];
    #define LS (p << 1)
    #define RS (LS | 1)
    #define MID ((gl + gr) >> 1)
public:
    void Pushup(int p){
        tr[p] = tr[LS] + tr[RS];
        sum[p] = sum[LS] + sum[RS];
    }
    void Modify(int pos, int p = 1, int gl = 1, int gr = N){
        if(gl == gr)return tr[p]++, sum[p] += mp[pos], void();
        if(pos <= MID)Modify(pos, LS, gl, MID);
        else Modify(pos, RS, MID + 1, gr);
        Pushup(p);
    }
    ll Query(int K, int p = 1, int gl = 1, int gr = N){
        if(tr[p] <= K)return sum[p];
        if(gl == gr)return 0;
        if(tr[LS] > K)return Query(K, LS, gl, MID);
        else return sum[LS] + Query(K - tr[LS], RS, MID + 1, gr);
    }
}st;

int main(){
    // freopen("in.txt", "r", stdin);
    N = read(), K = read();
    opt += {1, 0};
    for(int i = 1; i <= N; ++i){
        int f = read(), v = read();
        opt += {f, v};
        if(f == 2)_data += v;
    }sort(_data.begin(), _data.end());
    _data.erase(unique(_data.begin(), _data.end()), _data.end());
    // N = _data.size();
    for(auto &op : opt){
        if(op.first == 1)continue;
        int dis = distance(_data.begin(), upper_bound(_data.begin(), _data.end(), op.second));
        mp[dis] = op.second, op.second = dis;
    }
    for(auto it = opt.rbegin(); it != opt.rend(); ++it){
        if(it->first == 1){
            ans = max(ans, (ll)it->second + sum - st.Query(K--));
            if(K < 0)break;
            // printf("cur, ans = %lld\n", it->second + sum - st.Query(K + 1));
        }else{
            sum += mp[it->second];
            if(mp[it->second] < 0)st.Modify(it->second);
        }
    }printf("%lld\n", ans);
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    int flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

UPD

update-2022_11_30 初稿