- 数据范围多少有点诈骗
- 首先考虑 \(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)\)
CF1894E Freedom of Choice
发布时间 2023-12-09 16:18:52作者: FOX_konata