Luogu4587 [FJOI2016] 神秘数 发表于 2025-02-22 更新于 2025-02-26 分类于 算法竞赛 ， 题 ， 洛谷 阅读次数： 题意：对于可重整数集 ，定义 为最小的不能被 的一个子集的和表示出来的正整数。 给定序列 ，每次询问 。 ，，时限 。 考虑如何回答单组询问。 将集合 从小到大排序为 。 不难发现，找到第一个 ，则 。 回到原问题。 用主席树差分得到区间内的值域线段树。 设当前的候选答案为 （初始时为 ），求 的数的和 ，若 ，则答案为 。 若 ，则令 ，继续操作。 记连续某两次的 为 ，若不停止，则 的查询中 必然要有数，下一步至少变为 。故操作次数是 的。 复杂度为 。 加强 ：U164888 五重原题 在上一题的基础上增加单点修改操作。 ，时限。 可以用树套树来维护“区间内 的数的和”，复杂度高达 ，无法通过。 将值域按照 分块。每次操作，（由于开始时是 ）要么跳过一整块，要么停止在中间。 于是对于每一块，维护 ，判一下 会不会停止即可。 时间复杂度为 ，空间复杂度为 。 底层按 分块可以将空间复杂度改进为 。