标签：Freedom sum CF1894E Choice 枚举 集合 复杂度
CF1894E
- 数据范围多少有点诈骗
- 首先考虑 \(m=1\) 的情况
- 容易发现这个 \(l_i,r_i\leq 10^{17}\) 不是很对劲，因为直觉上感觉如果区间可取范围过大答案就是 \(0\)
- 我们可以取一个不是那么严格的限制条件来约束他，当 \(r-l>n\) 时，答案肯定是 \(0\)。这样我们就把区间长度取到了 \(10^5\) 数量级内
- 反美集合看起来就很反人类，因此我们直接枚举区间长度 \(x\in[l,r]\) 即可，复杂度 \(O(nm)\)
- 考虑朴素的 \(m\) 情况。限制条件变为 \(\sum r_i - \sum l_i > \sum n_i\)，现在问题是如何快速的 check 情况，这里就要用到复杂度均摊。对于存在 \(x\) 的集合我们发现会被重复计算，因此我们直接预处理好不包含 \(x\) 的所有集合的 \(r_i\)，而对于包含 \(x\) 的集合直接暴力枚举，最终总枚举量是 \(O(\sum n_i\)) 的，因此复杂度为 \(O(m+\sum n_i)\)
标签：Freedom,
sum,
CF1894E,
Choice,
枚举,
集合,
复杂度
From： https://www.cnblogs.com/fox-konata/p/17891111.html