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 位置增加 deltavoid 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) 的时间复杂度内完成每次更新和查询，适用于大规模的数据处理需求。