给定一个正整数组成的数组,每次询问一个区间[l r]内不能组成的最小的正整数.
区间内的数字最多被用一次,可以一个都不选(结果为0).
询问特别多,所以每一次的回答复杂度应该要控制到\(O(1) ~ O(log)\)的范围比较好,这给了我们一个方向.
现在来思考,如果区间为空的话,只能组成数字\(0\),所以答案是\(1\),尽管"区间为空"这种情况是不会出现的,但是我们可以作为一个思考的起点.
前面是一个个给区间里面加数字,现在回到这道题的题意,给定一个固定的区间.其实和前面的分析差不多,定义\(k\):当前状态下,能够从0开始连续表示的最大的数字.
现在的问题变为,如何维护"区间内值在[0 k + 1]的范围的数字之和",这个可以用可持久化线段树(主席树)来维护.