「FJOI2016」神秘数 解题报告

「FJOI2016」神秘数

这题不sb，我挺sb的...

我连不带区间的都不会哇

考虑给你一个整数集，如何求这个神秘数

这有点像一个01背包，复杂度和值域有关。但是你发现01背包可以求出更多的东西，就是每个值是否可以被表示，而这个问题有点像问你一个单点的是否可以被表示，这是它的特殊性。

我们把这个整数集排序后，假设当前表示的区间是([1,x])，这时候在线加入(a)

如果(ale x)，显然值域变成([1,x+a])，否则答案假设(x+1)

考虑如何优化这个过程，我们可不可以一次加入很多个数字呢？

如果当前的区间是([1,x])，然后之前加的一个值是(las)，那么值域在([las+1,a+1])的值都是可以加入的，那么我们不妨一起把它们加入，并把(x)变成它们的和+1

这时候下一个要加入的值的值域至少是(2*las)，所以操作次数是(log)的

然后我们发现支持一个区间中某个值域的数的和，直接主席树就可以了

复杂度(O(nlog nlog sum a))

---

Code:

#include <cstdio>
#include <cctype>
template <class T>
void read(T &x)
{
	x=0;char c=getchar();
	while(!isdigit(c)) c=getchar();
	while(isdigit(c)) x=x*10+c-'0',c=getchar();
}
const int N=1e5+10;
const int inf=1e9;
int a[N],n,m;
int ch[N*90][2],sum[N*90],root[N],tot;
#define ls ch[now][0]
#define rs ch[now][1]
#define ols ch[las][0]
#define ors ch[las][1]
#define koito_yuu 233
void change(int las,int &now,int l,int r,int p)
{
	now=++tot;
	if(l==r){sum[now]=sum[las]+p;return;}
	int mid=l+r>>1;
	if(p<=mid) change(ols,ls,l,mid,p),rs=ors;
	else ls=ols,change(ors,rs,mid+1,r,p);
	sum[now]=sum[ls]+sum[rs];
}
int query(int now,int las,int l,int r,int p)
{
	if(r<=p) return sum[now]-sum[las];
	int mid=l+r>>1;
	if(p<=mid) return query(ls,ols,l,mid,p);
	else return sum[ls]-sum[ols]+query(rs,ors,mid+1,r,p);
}
int main()
{
	read(n);
	for(int i=1;i<=n;i++) read(a[i]),change(root[i-1],root[i],1,inf,a[i]);
	read(m);
	for(int l,r,ans,i=1;i<=m;i++)
	{
		read(l),read(r),ans=1;
		while(koito_yuu)
		{
			int sum=query(root[r],root[l-1],1,inf,ans);
			if(sum<ans) break;
			else ans=sum+1;
		}
		printf("%d
",ans);
	}
	return 0;
}

---

2019.3.12