[lg4587][FJOI2016]神秘数

这辈子都不会主席树啊我好菜啊

题意

有一个可重集,求最小的无法表示为这个可重集里某些元素之和的数。

思路

神秘数是最小的数,满足小于它的数的和小于它。

主席树维护,每次找比它小的数的和并更新。

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
inline int getint()
{
int r = 0,s = 1;char c = getchar();for(;!isdigit(c);c = getchar()) if(c == '-') s = 0;
for(;isdigit(c);c = getchar()) r = (((r << 2) + r) << 1) + (c ^ '0');return s ? r : -r;
}
const int N = 100010,M = 5000500;
struct FotileTree
{
int root[N],lc[M],rc[M],sum[M],sz;
FotileTree(){sz = 0;}
inline void insert(int &x,int y,int l,int r,int p)
{
x = ++sz;lc[x] = lc[y];rc[x] = rc[y];sum[x] = sum[y] + p;
if(l == r) return;
int mid = (l + r) >> 1;
if(p <= mid) insert(lc[x],lc[y],l,mid,p);
else insert(rc[x],rc[y],mid + 1,r,p);
}
inline int query(int x,int y,int l,int r,int L,int R)
{
if(l == L && r == R) return sum[x] - sum[y];
int mid = (l + r) >> 1;
if(R <= mid) return query(lc[x],lc[y],l,mid,L,R);
if(L > mid) return query(rc[x],rc[y],mid + 1,r,L,R);
return query(lc[x],lc[y],l,mid,L,mid) + query(rc[x],rc[y],mid + 1,r,mid + 1,R);
}
}PT;
int a[N],n,m,q;
int main()
{
n = getint();for(int i = 1;i <= n;i++) if(m < (a[i] = getint())) m = a[i];
for(int i = 1;i <= n;i++) PT.insert(PT.root[i],PT.root[i - 1],1,m,a[i]);
q = getint();while(q--)
{
int ans = 1,l = getint(),r = getint();
for(int tmp;;ans = tmp + 1)
{
tmp = PT.query(PT.root[r],PT.root[l - 1],1,m,1,std::min(ans,m));
if(ans > tmp) break;
}
printf("%d\n",ans);
}
return 0;
}