P10673 【MX-S1-T2】催化剂 题解

要解决这个问题，我们需要高效地处理动态更新的糖果种类数量，并在每次询问时快速计算最小的愤怒值总和。以下是详细的解决方案和实现步骤：

问题分析

1. 糖果的种类和数量：

   • 每个糖果有一个类型，代表不同的种类。
   • 我们需要跟踪每种类型的糖果数量，以便在分配时计算重复的糖果数量，从而确定愤怒值。

2. 操作类型：

   • 添加糖果 (1 x)：增加一种类型为 x 的糖果数量。
   • 删除糖果 (2 x)：减少一种类型为 x 的糖果数量，保证删除前该类型至少有一个糖果。
   • 查询 (3 k)：将所有糖果分给 k 个小朋友，计算最小的愤怒值总和。

解决思路

为了高效地处理大规模的数据，我们采用以下策略：

1. 频率计数：

   • 使用一个数组 f[x] 来记录每种类型 x 的糖果数量。

2. 利用树状数组（Fenwick Tree）：

   • 我们需要快速查询糖果数量大于 k 的类型数量以及这些类型的总糖果数。
   • 为此，我们使用两个树状数组：
     • BIT_freq：记录每个频率（糖果数量）对应的类型数量。
     • BIT_f_freq：记录每个频率对应的糖果总数。

3. 处理操作：

   • 添加糖果：
     • 更新 f[x] 的值。
     • 更新 BIT_freq 和 BIT_f_freq，减少旧频率的计数，增加新频率的计数。
   • 删除糖果：
     • 同样更新 f[x] 的值。
     • 更新两个树状数组，减少旧频率的计数，增加新频率的计数（如果新频率大于零）。
   • 查询：
     • 通过 BIT_freq 查询频率大于 k 的类型数量 cnt_over。
     • 通过 BIT_f_freq 查询这些类型的糖果总数 sum_f_over。
     • 计算总愤怒值为 sum_f_over - k * cnt_over。

4. 优化：

   • 快速输入输出：使用 ios::sync_with_stdio(false) 和 cin.tie(0) 来加速输入输出操作。
   • 预处理：初始化频率计数和树状数组。

C++ 实现

以下是基于上述思路的 C++ 实现：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

// 树状数组结构体
struct BIT {
    int size;
    vector<ll> tree;

    BIT(int n){
        size = n;
        tree.assign(n+2, 0LL);
    }

    // 更新操作：在 index 位置增加 delta
    void add(int index, ll delta){
        while(index <= size){
            tree[index] += delta;
            index += index & (-index);
        }
    }

    // 查询前缀和
    ll query(int index){
        ll res = 0;
        while(index > 0){
            res += tree[index];
            index -= index & (-index);
        }
        return res;
    }

    // 查询区间和 [l, r]
    ll query_range(int l, int r){
        if(l > r) return 0;
        return query(r) - query(l-1);
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, q;
    cin >> n >> q;
    
    // 假设类型编号从 1 到 n
    // f[x] 表示类型 x 的糖果数量
    vector<int> f(n+1, 0);
    for(int i = 0; i < n; i++){
        int a;
        cin >> a;
        f[a]++;
    }
    
    // 最大可能的频率是 n + q，设为 2e6 以适应所有操作
    int MAX_F = 2000001;
    BIT BIT_freq(MAX_F);     // 记录每个频率对应的类型数量
    BIT BIT_f_freq(MAX_F);   // 记录每个频率对应的糖果总数
    
    // 初始化树状数组
    for(int x = 1; x <= n; x++){
        if(f[x] >= 1){
            BIT_freq.add(f[x], 1);
            BIT_f_freq.add(f[x], (ll)f[x]);
        }
    }
    
    // 处理每个操作
    while(q--){
        int op;
        cin >> op;
        if(op == 1){
            // 添加糖果
            int x;
            cin >> x;
            int old_f = f[x];
            int new_f = old_f + 1;
            if(old_f >= 1){
                BIT_freq.add(old_f, -1);
                BIT_f_freq.add(old_f, - (ll)old_f);
            }
            f[x] = new_f;
            BIT_freq.add(new_f, 1);
            BIT_f_freq.add(new_f, (ll)new_f);
        }
        else if(op == 2){
            // 删除糖果
            int x;
            cin >> x;
            int old_f = f[x];
            int new_f = old_f - 1;
            BIT_freq.add(old_f, -1);
            BIT_f_freq.add(old_f, - (ll)old_f);
            f[x] = new_f;
            if(new_f >= 1){
                BIT_freq.add(new_f, 1);
                BIT_f_freq.add(new_f, (ll)new_f);
            }
        }
        else if(op == 3){
            // 查询
            int k;
            cin >> k;
            if(k >= MAX_F){
                // 没有频率大于 k 的类型
                cout << "0\n";
                continue;
            }
            // 查询频率大于 k 的糖果总数
            ll sum_f_over = BIT_f_freq.query_range(k+1, MAX_F);
            // 查询频率大于 k 的类型数量
            ll cnt_over = BIT_freq.query_range(k+1, MAX_F);
            // 计算总愤怒值
            ll total_anger = sum_f_over - ((ll)k * cnt_over);
            cout << total_anger << "\n";
        }
    }
}

代码解释

1. 树状数组（BIT）的实现：

   • add(int index, ll delta)：在指定位置 index 增加 delta。
   • query(int index)：查询从 1 到 index 的前缀和。
   • query_range(int l, int r)：查询区间 [l, r] 的和。

2. 初始化：

   • 读取初始糖果种类，更新频率数组 f。
   • 根据初始频率，初始化两个树状数组 BIT_freq 和 BIT_f_freq。

3. 处理每个操作：

   • 添加糖果 (1 x)：
     • 减少旧频率在 BIT_freq 和 BIT_f_freq 中的计数。
     • 增加新频率在两个树状数组中的计数。
   • 删除糖果 (2 x)：
     • 减少旧频率在两个树状数组中的计数。
     • 如果新的频率大于等于 1，则在两个树状数组中增加新频率的计数。
   • 查询 (3 k)：
     • 使用 BIT_f_freq 查询频率大于 k 的糖果总数 sum_f_over。
     • 使用 BIT_freq 查询频率大于 k 的类型数量 cnt_over。
     • 计算总愤怒值 total_anger = sum_f_over - k * cnt_over。

4. 注意事项：

   • 确保 k 不超过 MAX_F，否则愤怒值为 0。
   • 使用 long long 类型防止溢出，因为糖果数量可能很大。

总结

通过使用树状数组，我们能够在对糖果种类进行动态更新的同时，快速响应查询操作。这种方法能够在 O(log N) 的时间复杂度内完成每次更新和查询，适用于大规模的数据处理需求。