题解：P11882 [RMI 2024] 彩虹糖 / Skittlez

· · 题解

枚举二进制位 i。将所有颜色在 i 位上为 1 的操作单独抠出来作为集合 S。对于每个位置求被 S 集合覆盖的次数，然后判断是否大于被全集覆盖次数的一半。通过这个操作我们能得到每个位置的答案（如果不是-1）。

判 -1 就对于每种颜色数点即可。

时间复杂度 O(n\log n)，只需要树状数组与二维前缀和。

fun fact：发现了很多人使用二维树状数组来解决二维数点。