bzoj 4299 FRBSUM

Posted on | Views:

主席树.

考虑如何计算一个集合的 $\text{Forbidden Sum}​$ .

将集合内的数从小到大排序,依次加入.若当前可以表示出 $[0,s]$ 内的所有数,再加入一个数 $x$ .

若 $x\le s+1$ ,则可以表示出 $[0,s+x]$ 内的所有数.若 $x> s+1$ ,则 $s+1$ 无法被表示出,答案为 $s+1$ .

实际做的时候可以换一种思路,将枚举 $x$ 变为不断更新 $s$ .

初始令 $s=1​$ ,每次在区间 $[l,r]​$ 内询问所有 $\le s​$ 的数之和,即上面分析的前缀和.若询问到的 $x<s​$ ,则答案为 $s​$ .

否则令 $s=x+1$ ,继续询问.

询问一段区间内 $\le s​$ 的所有数之和可以用主席树实现.

考虑时间复杂度,若每次都 $x\ge s$ ,每次询问 $s$ 至少翻一倍,所以在主席树上查询了 $O(\log \sum a_i)$ 次.

总时间复杂度为 $O(m\cdot \log \max a_i\cdot \log \sum a_i)$ .

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
67
68
69
70
71
72
73
74
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=1e5+10;
struct PreSegtree
{
	int idx;
	struct node
	{
		int ls,rs;
		int sum;
		node(){ls=rs=sum=0;}
	}Tree[MAXN*30];
	PreSegtree(){idx=0;}
#define root Tree[o]
	void ins(int &o,int pre,int l,int r,int pos,int c)
	{
		o=++idx;
		root=Tree[pre];
		root.sum+=c;
		if(l==r)
			return;
		int mid=(l+r)>>1;
		if(pos<=mid)
			ins(root.ls,Tree[pre].ls,l,mid,pos,c);
		else
			ins(root.rs,Tree[pre].rs,mid+1,r,pos,c);
	}
	int query(int o,int l,int r,int val)// \le val
	{
		if(l>val)
			return 0;
		if(r<=val)
			return root.sum;
		int mid=(l+r)>>1;
		return query(root.ls,l,mid,val)+query(root.rs,mid+1,r,val);
	}
}T;
int n,m,a[MAXN],mx=0,rt[MAXN];
int main()
{
	n=read();
	for(int i=1;i<=n;++i)
		mx=max(mx,a[i]=read());
	for(int i=1;i<=n;++i)
		T.ins(rt[i],rt[i-1],1,mx,a[i],a[i]);
	m=read();
	for(int i=1;i<=m;++i)
	{
		int L=read(),R=read();
		for(int s=1,x;;s=x+1)
		{
			x=T.query(rt[R],1,mx,s)-T.query(rt[L-1],1,mx,s);
			if(x<s)
			{
				printf("%d\n",s);
				break;
			}
		}
	}
	return 0;
}