题目大意：一个可重复数字集合S的神秘数定义为最小的不能被S的子集的和表示的正整数。
给定一个序列 $a$，每次询问一个区间的神秘数。
很久之前还讲过这个题，当时还要求带修。
考虑加入当前的神秘数为 $x$。当加入一个数 $y$ 且 $y\le x$ 时神秘数会变为 $x+y$。当 $y>x$ 时对答案不造成贡献。
可以考虑值域倍增，对 $[1,1],[2,3],[4,7],\cdots,[2^k,2^k-1],\cdots$ 之间的元素分别维护前缀和和 rmq。
每次查询的时候依次查区间最小值是否小于当前神秘数即可。如果小于的话直接加上区间和去下一个区间，不然直接返回答案。
如果 $O(n)-O(1)$ 求 rmq 的话复杂度可以做到 $O(n\log\max(a[i]))$。
我的代码就直接用 st 表了。
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
| #include<bits/stdc++.h>
using namespace std;
#define il inline
#define rg register
#define ll long long
il int read()
{
int re=0,k=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')k=-1;ch=getchar();}
while(ch<='9'&&ch>='0'){re=re*10+ch-48;ch=getchar();}
return re*k;
}
il void write(int x)
{
if(x<0)return putchar('-'),write(-x),void();
if(x<=9)return putchar(x+48),void();
return write(x/10),write(x%10),void();
}
int LOG[100005],a[100005],n,m;
struct st{
int st[100005][17];ll sum[100005];
void init(int liml,int limr)
{
sum[0]=0;
for(rg int i=1;i<=n;i++)
if(a[i]>=liml&&a[i]<=limr)st[i][0]=a[i],sum[i]=sum[i-1]+a[i];
else st[i][0]=0x3f3f3f3f,sum[i]=sum[i-1];
for(rg int j=1;(1<<j)<=n;j++)
for(rg int i=1;i+(1<<j)<=n+1;i++)
st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
ll query(int l,int r)
{
int d=LOG[r-l];
return min(st[l][d],st[r-(1<<d)+1][d]);
}
ll Sum(int l,int r)
{
return sum[r]-sum[l-1];
}
}b[30];
signed main()
{
n=read();
for(rg int i=1;i<=n;i++)
a[i]=read();
m=read();
for(rg int i=2;i<=n;i++)
LOG[i]=LOG[i>>1]+1;
b[0].init(1,1);
for(rg int i=1,t=2;i<=29;i++,t<<=1ll)
b[i].init(t,t+t-1);
for(rg int i=1,l,r;i<=m;i++)
{
l=read();r=read();
ll ans=0;int t=0;
while(t<=29)
{
if(ans+1ll<min(b[t].query(l,r),(1ll<<(t+1))-1))
break;
ans+=b[t].Sum(l,r);
t++;
}
write(ans+1ll);puts("");
}
}
|