杂题选做
主要记录一下刷的非套题的思路。
2024.12.12
Luogu P3586 [POI2015] LOG 80/100
看到判定类问题可以先思考必要性条件，可以先列出一个式子：
\[\sum \min(s,a_i) \ge c \times s \]显然对于每个询问这是成立的，否则根本选不到 \(c \times s\) 个。
然后看到形如 \(\max/\min(x,c)\) （其中 \(c\) 是常数）的形式可以分类讨论，拆成大于/小于 \(c\) 的部分和小于等于/大于等于 \(c\) 的部分。
这个拆出来之后就好处理这个贡献了，可以开两个值域 BIT 分别维护大于等于 \(s\) 的数的个数和小于等于 \(s\) 的数的和即可，此部分复杂度为 \(O(\log n)\) 单次操作。
然后考虑到另一个限制就是每次查询的单次操作都必须要至少有 \(c\) 个正数。而那些大于等于 \(s\) 的数显然满足 \(s\) 轮操作，然后再猜一下结论可得 \(\sum a_i[a_i<s] \ge s \times (c-\sum [a_i \ge s])\) 是充要条件，由上面的结论可得必要性显然，然后考虑证明充分性（即证明一定存在一种构造方式使得满足限制）。
将这些小于 \(s\) 的数从大到小排序，原问题等价于给定一个 \(s \time c\) 的矩阵，现在已有 \(m=\sum [a_i \ge s]\) 列放满。我们按顺序填充每一列，由于 \(a_i \ge a_{i+1}\)，因此必然不会存在同一行放了相同元素的情况。因此问题得证。
时间复杂度 \(O(n \log n)\).
标签：小于,sum,ge,等于,大于,杂题 From： https://www.cnblogs.com/ldh081122/p/18602208