「FJOI 2016」神秘数

Problem

Description

定义一个可重数集 S 的"神秘数"为最小的不能被 S 的子集的和表示的正整数。
即集合 S 的"神秘数"为 \operatorname{mex}\left\{\sum_{x\in S'}x | S'\subseteq S\right\}

如对于集合 S=\left\{1,1,1,4,13\right\} ,有:

表示
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_{n}\} ,有 m 个询问,每次询问给定一个区间 [l, r] ,求可重数集 \left\{a_{i} | i\in[l, r]\right\} 的"神秘数"。

Constraints

1\le n,m\le 10^{5},\sum_{i=1}^{n}a_{i}\le 10^{9}

Solution

Analysis

x(S) 为可重数集 S 的"神秘数", p(S)=\left[0,x(S)\right) 。那么设在可重数集 S 中加入 y 得到的新可重数集为 S' ,则有:

p(S')=p(S)\cup\left\{z+y | z\in p(S)\right\}=\left[0,x(S)\right)\cup\left[y,x(S)+y\right)

  • y\le x(S) 时, p(S')=\left[0,x(S)+y\right) ,故 x(S')=x(S)+y
  • y>x(S) 时, p(S')=\left[0,x(S)\right) ,故 x(S')=x(S)

基于这个规律,可以这样求得一个可重数集 S 的"神秘数":
易知 x(\varnothing)=1 。考虑通过逐步在初始集合中插入数字来求得 x(S)
通过以上规律可以发现,只有满足 y\le x(S) y 才会对 x(S) 产生影响。

于是考虑将集合 S 中的数从小到大添加。
ans 为当前操作前的 x(S) 。(第一次操作时 ans=1
那么对于每次操作,求出 tmp=\sum_{i\in[l, r],a_{i}\in\left[0,ans\right]}a_{i}

  • ans>tmp ,则说明新集合 S'=\left\{a_{i} | i\in[l, r],a_{i}\in\left[0,ans\right]\right\} 的"神秘数" x(S') 没有发生改变,并且不论再怎么加入都不会继续改变,即所求答案为当前 ans
  • ans\le tmp ,则说明新集合 S'=\left\{a_{i} | i\in[l, r],a_{i}\in\left[0,ans\right]\right\} 的"神秘数" x(S') 发生了改变,继续加入下一个值域区间直到 ans>tmp

用主席树维护区间 [l, r] 中的权值区间和即可。

时间复杂度 O\left(m\log{n}\right)

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
52
53
54
#include<cstdio>


inline int Max(const int&x,const int&y){return x>y?x:y;}

struct Input{
#define SIZE 98304
char BUF[SIZE],*S,*T;
Input():S(BUF),T(BUF){}
inline Input&operator>>(char&c){return(c=(S==T)&&(T=(S=BUF)+fread(BUF,1,SIZE,stdin),S==T)?EOF:*S++,*this);}
template<typename T>inline Input&operator>>(T&s){
s=0;char c;
while(*this>>c,c<48||c>57);
while(s=s*10+c-48,*this>>c,c>47&&c<58);
return*this;
}
#undef SIZE
}input;

int a[100001];
int root[100001];
struct Node{
int sum,lson,rson;
Node():sum(0),lson(0),rson(0){}
}node[4000000];
int cnt;
#define sum(o) node[o].sum
#define ls(o) node[o].lson
#define rs(o) node[o].rson
inline void Insert(int&Pre,int&Suc,const int&L,const int&R,const int&pos){
if(sum(Suc=++cnt)=sum(Pre)+pos,L==R)return;
int Mid=(L+R)>>1;
if(pos<=Mid)rs(Suc)=rs(Pre),Insert(ls(Pre),ls(Suc),L,Mid,pos);
else ls(Suc)=ls(Pre),Insert(rs(Pre),rs(Suc),Mid+1,R,pos);
}
inline int Query(int&Pre,int&Suc,const int&L,const int&R,const int&pos){
if(R<=pos)return sum(Suc)-sum(Pre);
int Mid=(L+R)>>1;
if(pos<=Mid)return Query(ls(Pre),ls(Suc),L,Mid,pos);
return sum(ls(Suc))-sum(ls(Pre))+Query(rs(Pre),rs(Suc),Mid+1,R,pos);
}

int main(){
int n,Len=0;input>>n;
for(int i=1;i<=n;++i)input>>a[i],Len=Max(Len,a[i]);
for(int i=1;i<=n;++i)Insert(root[i-1],root[i],1,Len,a[i]);
int m;
for(input>>m;m;--m){
int L,R;input>>L>>R;
int ans=1,tmp;
while((tmp=Query(root[L-1],root[R],1,Len,ans))>=ans)ans=tmp+1;
printf("%d\n",ans);
}return 0;
}