思路:
考虑往集合中添数.
假设当前集合中最大值为$R$, 和为$S$, 可以表示$[1,S]$的所有数.
则此时可以添加进集合中的数范围为$[1,S+1]$, 可以直接将该值域内所有数全部加入集合当中. 若选完后的$S$大于原来的$S$则更新, 否则说明没有新的符合条件的数, 答案为$S+1$.
区间上处理值域直接用主席树即可. 由于选数的过程中$S$是倍增的, 所以每次查询的时间复杂度是$O(log^2n)$.
代码:
1 |
|
考虑往集合中添数.
假设当前集合中最大值为$R$, 和为$S$, 可以表示$[1,S]$的所有数.
则此时可以添加进集合中的数范围为$[1,S+1]$, 可以直接将该值域内所有数全部加入集合当中. 若选完后的$S$大于原来的$S$则更新, 否则说明没有新的符合条件的数, 答案为$S+1$.
区间上处理值域直接用主席树即可. 由于选数的过程中$S$是倍增的, 所以每次查询的时间复杂度是$O(log^2n)$.
1 | #include <cstdio> |