题意
给定一个可重集 \(S\)，求所有的前缀的集合的代价。
定义一个集合的代价为：
\[\max_x \left( (\max_i b_i \lvert x) - (\min_i b_i \lvert x)\right) \]\(n \le 10 ^ 6, V \le 2 \times 10 ^ 6\)
Sol
首先看到这个式子直接开划。
称较大的数为 \(b_i\)，较小的数为 \(b_j\)。
直接考虑二进制位，发现 \(x\) 会取到所有 \(b_{j, k} = 1\) 而 \(b_{i, k} = 0\) 的位置上。
我们发现答案的值域很小，集中注意力，思考答案会满足什么样的性质。
事实上答案 \(ans\) 满足 \(ans \subseteq b_i\) 以及 \(ans \subseteq \overline b_j\)。
这个玩意是充要条件。
接下来就很简单了，直接考虑维护两个集合 \(Sx\), \(Sy\)，分别表示加入 \(x \subseteq b_i\)，\(y \subseteq \overline b_j\)，即可。
假如一个数 \(x\) 同时出现在了两个集合中，直接更新答案即可。
标签：省选,T1,overline,20240627,答案,ans,集合,subseteq From： https://www.cnblogs.com/cxqghzj/p/18282412