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](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找第一个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

#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));
	}
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据