题解 [模拟赛 2023.3.24] 破解密码

· · 个人记录

赛时没看到 a_i, x 是 long long 范围内的，结果 100 \to 60。我是小丑，哈哈哈哈哈。

到时候省选不要再这样挂分了啊 /fn

题意翻译一下就是 x \in \cup_{|S| = |T|} [sum(S), sum(T))。贪心地，对于每个 |S| = |T| = i，选择前 i 小和前 i 大可以涵盖其他所有情况，则 x \in \cup_{i = 1}^n [pre_i, suf_i)。

然后就可以开始写暴力了：每加入 / 删除一个数就重算一遍 pre, suf，然后求出线段并的长度即可。时间复杂度为 O(nq)，可以获得跟正解没开 long long 一样的 60 分。

如果线段都不交是很好办的（即样例 1 中的情况），直接求按值排序的后缀和之和减去前缀和之和即可。这个可以上平衡树维护。

现在考虑线段啥时候会相交。不难发现 i, i - 1 的线段可以被视作相交当且仅当 pre_i \leq suf_{i - 1}。

再观察一下样例 2 会发现相交的似乎一定是中间的一坨线段，这里我们来进行一下证明：

最低点之一显然为 \lceil \frac{n'}{2} \rceil（其中 n' 为当前集合中的元素个数），于是我们先判一下有没有相交，若有则从这里开始向两边二分找到极长相交段即可。时间复杂度为 O(n \log n + q \log^2 n)，常数较大。

下面讲一下如何卡常：

代码：

#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <ctime>

typedef long long ll;

namespace Fread {
    const int BUFFER_SIZE = 1 << 25;
    char buffer[BUFFER_SIZE + 7];
    char *pstart = buffer, *pend = buffer;

    inline char getchar(){
        if (pstart < pend) return *pstart++;
        pstart = buffer;
        pend = buffer + fread(buffer, 1, BUFFER_SIZE, stdin);
        return pstart == pend ? EOF : *pstart++;
    }

    inline int read_int(){
        int ans = 0;
        char ch = getchar();
        while (ch < '0' || ch > '9'){
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9'){
            ans = ans * 10 + (ch ^ 48);
            ch = getchar();
        }
        return ans;
    }

    inline ll read_ll(){
        ll ans = 0;
        char ch = getchar();
        while (ch < '0' || ch > '9'){
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9'){
            ans = ans * 10 + (ch ^ 48);
            ch = getchar();
        }
        return ans;
    }
}

using namespace std;

typedef struct {
    int ls;
    int rs;
    int size;
    int heap_val;
    ll real_val;
    ll sum;
    ll pre_sum;
    ll suf_sum;
} Node;

int id = 0, root = 0;
ll a[200007];
Node tree[400007];

inline int new_node(ll x){
    int ans = ++id;
    tree[ans].size = 1;
    tree[ans].heap_val = rand();
    tree[ans].real_val = tree[ans].sum = tree[ans].pre_sum = tree[ans].suf_sum = x;
    return ans;
}

inline void update(int x){
    int ls = tree[x].ls, rs = tree[x].rs;
    tree[x].size = tree[ls].size + tree[rs].size + 1;
    tree[x].sum = tree[ls].sum + tree[x].real_val + tree[rs].sum;
    tree[x].pre_sum = tree[ls].pre_sum + (tree[ls].sum + tree[x].real_val) * (tree[rs].size + 1) + tree[rs].pre_sum;
    tree[x].suf_sum = tree[rs].suf_sum + (tree[rs].sum + tree[x].real_val) * (tree[ls].size + 1) + tree[ls].suf_sum;
}

int merge(int x, int y){
    if (x == 0) return y;
    if (y == 0) return x;
    if (tree[x].heap_val < tree[y].heap_val){
        tree[x].rs = merge(tree[x].rs, y);
        update(x);
        return x;
    }
    tree[y].ls = merge(x, tree[y].ls);
    update(y);
    return y;
}

int build(int l, int r){
    if (l == r) return new_node(a[l]);
    int mid = (l + r) >> 1;
    return merge(build(l, mid), build(mid + 1, r));
}

void split_by_val(int x, int &y, int &z, ll k){
    if (x == 0){
        y = z = 0;
        return;
    }
    if (tree[x].real_val <= k){
        y = x;
        split_by_val(tree[x].rs, tree[x].rs, z, k);
    } else {
        z = x;
        split_by_val(tree[x].ls, y, tree[x].ls, k);
    }
    update(x);
}

inline void insert(ll x){
    int y, z;
    split_by_val(root, y, z, x - 1);
    root = merge(y, merge(new_node(x), z));
}

inline void erase(ll x){
    int y, z, w;
    split_by_val(root, y, z, x - 1);
    split_by_val(z, z, w, x);
    root = merge(y, w);
}

void split_by_size(int x, int &y, int &z, int k){
    if (x == 0){
        y = z = 0;
        return;
    }
    if (tree[tree[x].ls].size < k){
        y = x;
        split_by_size(tree[x].rs, tree[x].rs, z, k - tree[tree[x].ls].size - 1);
    } else {
        z = x;
        split_by_size(tree[x].ls, y, tree[x].ls, k);
    }
    update(x);
}

inline ll get_pre(int x, int k){
    if (x == 0 || k == 0) return 0;
    if (k == tree[x].size) return tree[x].sum;
    if (k <= tree[tree[x].ls].size) return get_pre(tree[x].ls, k);
    return tree[tree[x].ls].sum + tree[x].real_val + get_pre(tree[x].rs, k - tree[tree[x].ls].size - 1);
}

inline ll get_suf(int x, int k){
    if (x == 0 || k == 0) return 0;
    if (k == tree[x].size) return tree[x].sum;
    if (k <= tree[tree[x].rs].size) return get_suf(tree[x].rs, k);
    return tree[tree[x].rs].sum + tree[x].real_val + get_suf(tree[x].ls, k - tree[tree[x].rs].size - 1);
}

inline ll get_pre_sub(int x){
    int y, z;
    ll ans;
    split_by_size(root, y, z, x);
    ans = (tree[y].suf_sum + x * tree[z].sum) - tree[y].pre_sum;
    root = merge(y, z);
    return ans;
}

inline ll get_suf_sub(int x){
    int y, z;
    ll ans;
    split_by_size(root, y, z, x);
    ans = tree[z].suf_sum - (tree[z].pre_sum + tree[z].size * tree[y].sum);
    root = merge(y, z);
    return ans;
}

inline ll solve(){
    if (tree[root].size <= 1) return 0;
    int mid = (tree[root].size + 1) / 2;
    if (get_pre(root, mid) - get_suf(root, mid - 1) > 0) return tree[root].suf_sum - tree[root].pre_sum;
    int l = 1, r = mid, pos1, pos2;
    while (l <= r){
        int _mid = (l + r) >> 1;
        if (get_pre(root, _mid) - get_suf(root, _mid - 1) <= 0){
            r = _mid - 1;
            pos1 = _mid;
        } else {
            l = _mid + 1;
        }
    }
    pos2 = tree[root].size - pos1 + 1; 
    return (get_suf(root, pos2) - get_pre(root, pos1 - 1)) + get_pre_sub(pos1 - 2) + get_suf_sub(pos2 + 1);
}

int main(){
    int n = Fread::read_int(), q = Fread::read_int();
    srand(time(NULL));
    for (register int i = 1; i <= n; i++){
        a[i] = Fread::read_ll();
    }
    sort(a + 1, a + n + 1);
    root = build(1, n);
    printf("%lld\n", solve());
    for (register int i = 1; i <= q; i++){
        int x;
        ll y;
        x = Fread::read_int();
        y = Fread::read_ll();
        if (x == 1){
            insert(y);
        } else {
            erase(y);
        }
        printf("%lld\n", solve());
    }
    return 0;
}