题目
展开 题目描述 一个可重复数字集合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]所构成的可重复数字集合的神秘数。
输入格式 第一行一个整数n，表示数字个数。
第二行n个整数，从1编号。
第三行一个整数m，表示询问个数。
以下m行，每行一对整数l,r，表示一个询问。
输出格式 对于每个询问，输出一行对应的答案。
输入输出样例 输入 #1复制 5 1 2 4 9 10 5 1 1 1 2 1 3 1 4 1 5 输出 #1复制 2 4 8 8 8 说明/提示 对于100%的数据点，n,m <= 100000n,m<=100000，∑a[i] <= 10^9∑a[i]<=10 9
思路
首先我们挖一下这道题的性质 假设我们S集合中的树能表示的值域是[1,x]，考虑新加进来一个数t 如果t<=x+1那么值域变为表示[1,x+t]，否则值域不变，这是很容易证明的 所以暴力就是从小到大加数求值域 考虑怎么优化这个过程 设当前值域[1,x] 则ans=x+1 若小于等于ans的数的和res≥ans，则一定有未选的且小于等于ans的数，令ans=res+1即可。 反之说明答案就是ansans，直接breakbreak 因为ai比较大,用主席树维护
代码
#include<bits/stdc++.h>
#define mid ((lb+rb)>>1)
#define ll long long
using namespace std
;
int cnt
,root
[1000001],n
,m
;
const int inf
=1e9;
struct node
{
int l
,r
,sum
;
}seg
[5000001];
void update(int &rt
,int lb
,int rb
,int x
)
{
seg
[++cnt
]=seg
[rt
];rt
=cnt
;seg
[rt
].sum
+=x
;
if(lb
==rb
) return;
(mid
>=x
?update(seg
[rt
].l
,lb
,mid
,x
):update(seg
[rt
].r
,mid
+1,rb
,x
));
}
int query(int i
,int j
,int lb
,int rb
,int l
,int r
)
{
if(!(seg
[j
].sum
-seg
[i
].sum
)||r
<lb
|rb
<l
) return 0;
if(lb
>=l
&&rb
<=r
) return (seg
[j
].sum
-seg
[i
].sum
);
return query(seg
[i
].l
,seg
[j
].l
,lb
,mid
,l
,r
)+query(seg
[i
].r
,seg
[j
].r
,mid
+1,rb
,l
,r
);
}
int main()
{
scanf("%d",&n
);
for(int i
=1,x
; i
<=n
; i
++)
{
root
[i
]=root
[i
-1];
scanf("%d",&x
);
update(root
[i
],1,inf
,x
);
}
scanf("%d",&m
);
while(m
--)
{
int l
,r
;
scanf("%d%d",&l
,&r
);
int mx
=0,pos
=0;
for(int Sum
; ; )
{
Sum
=query(root
[l
-1],root
[r
],1,inf
,mx
+1,pos
+1);
if(!Sum
) break;
mx
=pos
+1;pos
+=Sum
;
}
printf("%d\n",pos
+1);
}
}
