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

__ryp__ · 2024-06-29 19:03:17 · 题解

首先奇耻大辱。赛时以为 Unrated 就不要紧，帮人调码交了两发，然后棕了。确实该罚，以后牢记。

然后来看题。

先不管操作一二。对于操作三，要求我们把所有糖果分成 k 份，所要统计的是重复出现的糖果的数量，别的没有要求。

如果每人每种糖果先分一颗，这时候每种糖果数量减去 k，接下来还没分完的糖果每颗都会带来 1 的贡献。

换句话说，我们就是对于每次询问的 k，统计每种糖果超出 k 部分的总和。也就是说，大于 k 的数的总和，减去大于 k 的数的数量乘上 k 就是答案。

这个操作用什么可以完成？平衡树，树状数组，权值线段树都可以做到。赛时无脑上了平衡树，但是实际上因为值域很小，所以后两者不需要离散化就可以。

总的来说，我们的做法就是：用桶维护每种糖果的数量，然后用上面三种数据结构之一维护；加减可以先删再插入，查询就查大于某数的数的和以及数量。

这里是代码。

平衡树有几个点注意：

• 需要加哨兵，否则需要注意边界情况；

• 查大于某数的数的数量，可以找后继然后用根减去左子树。