Description

一个可重复数字集合S的神秘数定义为最小的不能被S的子集的和表示的正整数。例如S={1,1,1,4,13}，

“`
1 = 1
2 = 1+1
3 = 1+1+1
4 = 4
5 = 4+1
6 = 4+1+1
7 = 4+1+1+1
“`

8无法表示为集合S的子集的和，故集合S的神秘数为8。

现给定n个正整数a[1]..a[n]，m个询问，每次询问给定一个区间[l,r](l<=r)，求由a[l],a[l+1],…,a[r]所构成的可重复数字集合的神秘数。

Input

第一行一个整数n，表示数字个数。
第二行n个整数，从1编号。
第三行一个整数m，表示询问个数。
以下m行，每行一对整数l,r，表示一个询问。

Output

对于每个询问，输出一行对应的答案。

Sample Input

“`
5
1 2 4 9 10
5
1 1
1 2
1 3
1 4
1 5
“`

Sample Output

“`
2
4
8
8
8
“`

HINT

对于100%的数据点，n,m <= 100000，∑a[i] <= 10^9

Source

鸣谢yyh上传

Solution

假设区间固定？

首先考虑暴力做法，询问区间l,r时，将a中的l到r这一部分元素取出，排序后求前缀和pre找第一个a_i ＞ pre_i + 1的i，然后pre_i + 1就是答案了；
如果我们预先知道了pre，和排序后的a，能不能小于O(n)的时间内求出来i？

有个看上去比较low的想法，当我们在i时，我们用pre二分一个最大的a_j使得我们在i一步能跳到j
不断的二分+跳直到跳不动为止，此时就是答案。

看上去复杂度要爆炸？

其实不然 因为两部之内，a_j会增长一倍多！
为什么呐？？

考虑从p1跳到p2然后跳到p3这个过程
a_p3+1 ＞ pre_p1 + a_p2
而a_p2 ≥ pre_p1
所以a_p3+1 ＞ 2*pre_p1

所以最多跳⌊log(10^9)⌋次

怎么强行排序？权值线段树！

然后需要实现在权值线段树上二分
题目变成了给你一棵权值线段树，你只能用支持加法的合并操作来搞出支持询问小于x的数的和是多少。
这个做法比较简单，留给读者自己练习。

但是区间不是固定的，我们可持久化这棵线段树就好啦

Code

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 100005;
inline int getint() {
	int r = 0; bool b = true; char c = getchar();
	while ('0' > c || c > '9') {if (c == '-') b = false; c = getchar();}
	while ('0' <= c && c <= '9') {r = r * 10 + (c - '0'); c = getchar();}
	if (b) return r;
	return -r;
}
int n, m, sum[maxn*31], qsum, tot, lc[maxn*31], rc[maxn*31], cnt[maxn*31], root[maxn];
void inc(int &x, int y, int l, int r, int val) {
	x = ++tot;
	cnt[x] = cnt[y] + 1;
	sum[x] = sum[y] + val;
	lc[x] = lc[y];
	rc[x] = rc[y];
	if (l == r) return;
	int mid = (l + r) >> 1;
	if (val <= mid) inc(lc[x], lc[y], l, mid, val);
	else inc(rc[x], rc[y], mid+1, r, val);
}
void query(int x, int y, int l, int r, int val) {
	if (cnt[x] - cnt[y] == 0) return;
	if (l == r) {qsum -= sum[x] - sum[y]; return;}
	int mid = (l + r) >> 1;
	if (val <= mid) {
		qsum -= sum[rc[x]] - sum[rc[y]];
		return query(lc[x], lc[y], l, mid, val);
	} else return query(rc[x], rc[y], mid+1, r, val);
}
inline int QUERY(int l, int r) {
	int S = 0;
	while (true) {
		qsum = sum[root[r]] - sum[root[l]];
		query(root[r], root[l], 0, 1000000000, S + 2);
		if (S == qsum) return S + 1;
		else S = qsum;
	}
}
int main() {
	n = getint();
	for (int i = 1; i <= n; ++i) inc(root[i], root[i-1], 0, 1000000000, getint());
	int x, y;
	m = getint();
	while (m--) {
		x = getint(); y = getint();
		printf("%d\n", QUERY(x-1, y));
	}
}