BZOJ 4408: [Fjoi 2016]神秘数

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，求由a[l],a[l+1],…,a[r]所构成的可重复数字集合的神秘数。

Input

第一行一个整数n，表示数字个数。

第二行n个整数，从1编号。

第三行一个整数m，表示询问个数。

以下m行，每行一对整数l,r，表示一个询问。

Output

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

Sample Input

“`

1 2 4 9 10

1 1

1 2

1 3

1 4

1 5

“`

Sample Output

“`

HINT

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

Source

鸣谢yyh上传

Solution

假设区间固定？

首先考虑暴力做法，询问区间l,r时，将a中的l到r这一部分元素取出，排序后求前缀和pre找第一个ai ＞ prei + 1的i，然后prei + 1就是答案了；

如果我们预先知道了pre，和排序后的a，能不能小于O(n)的时间内求出来i？

有个看上去比较low的想法，当我们在i时，我们用pre二分一个最大的aj使得我们在i一步能跳到j

不断的二分+跳直到跳不动为止，此时就是答案。

看上去复杂度要爆炸？

其实不然因为两部之内，aj会增长一倍多！

为什么呐？？

考虑从p1跳到p2然后跳到p3这个过程

ap3+1 ＞ prep1 + ap2

而ap2 ≥ prep1

所以ap3+1 ＞ 2*prep1

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

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

然后需要实现在权值线段树上二分

题目变成了给你一棵权值线段树，你只能用支持加法的合并操作来搞出支持询问小于x的数的和是多少。

这个做法比较简单，留给读者自己练习。

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

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#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));
	}
}