一道好冷门的好题啊，算是对于一个小结论和数据结构的一点考验吧
首先看完题目我们发现要从这个神秘数的性质入手，我们观察or手玩可得：
- 如果有\(x\)个\(1\)，那么\([1,x]\)都是可以表示出来的
- 如果我此时加入的数\(y>x\)，那么这个数无法被表示，因此便为答案
- 如果我此时加入的数\(y\le x\)，那么这个数可以被表示，并且可以表示的区间变成了\([1,x+y]\)
重复以上过程，肯定可以得出答案
但这样对于每一次询问都要进行一次排序，时间复杂度为\(O(nm\ logn)\)，肯定跑不过去的。我们换一种想法，假设我此时已经表示出了\([1,x]\)，那么我统计一下在区间\([l,r]\)中所有小于等于\(x+1\)的数的和\(s\)
若\(s\ge x+1\)，说明此时必定还存在更大的组合方案，于是可以表示的区间变为\([1,s]\)
再考虑上述的核心过程：统计一段区间内小于等于某个数的数的和
直接主席树即可，把值域线段树的点权改为数的和即可，查询的时候还是分左右子树查找
由于查询之后每次的答案扩大至少一倍，因此总复杂度\(O(m\ log^2n)\)
CODE
#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
const int N=100005;
struct President_tree
{
int ch[2],sum;
}node[N*20];
int n,m,q,rt[N],a[N],b[N],tot,l,r;
inline char tc(void)
{
static char fl[100000],*A=fl,*B=fl;
return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}
inline void read(int &x)
{
x=0; char ch; while (!isdigit(ch=tc()));
while (x=(x<<3)+(x<<1)+ch-'0',isdigit(ch=tc()));
}
inline void write(int x)
{
if (x>9) write(x/10);
putchar(x%10+'0');
}
inline int find(int x)
{
int l=1,r=m,mid,res;
while (l<=r)
{
mid=l+r>>1;
if (b[mid]<=x) res=mid,l=mid+1; else r=mid-1;
}
return res;
}
inline void build(int &now,int l,int r)
{
if (!now) now=++tot; if (l==r) return; int mid=l+r>>1;
build(node[now].ch[0],l,mid); build(node[now].ch[1],mid+1,r);
}
inline int insert(int lst,int l,int r,int id,int x)
{
int now=++tot; node[now]=node[lst]; node[now].sum+=x;
if (l==r) return now; int mid=l+r>>1;
if (id<=mid) node[now].ch[0]=insert(node[lst].ch[0],l,mid,id,x);
else node[now].ch[1]=insert(node[lst].ch[1],mid+1,r,id,x); return now;
}
inline int query(int lst,int now,int l,int r,int beg,int end)
{
int mid=l+r>>1,res=0;
if (l>=beg&&r<=end) return node[now].sum-node[lst].sum;
if (beg<=mid) res+=query(node[lst].ch[0],node[now].ch[0],l,mid,beg,end);
if (end>mid) res+=query(node[lst].ch[1],node[now].ch[1],mid+1,r,beg,end);
return res;
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
register int i; read(n);
for (i=1;i<=n;++i)
read(a[i]),b[i]=a[i]; read(q);
sort(b+1,b+n+1); m=unique(b+1,b+n+1)-b-1; build(rt[0],1,m);
for (i=1;i<=n;++i)
{
int x=find(a[i]);
rt[i]=insert(rt[i-1],1,m,x,a[i]);
}
for (i=1;i<=q;++i)
{
read(l); read(r); int ans=1;
for (;;)
{
int x=find(ans),s=query(rt[l-1],rt[r],1,m,1,x);
if (s>=ans) ans=s+1; else break;
}
write(ans); putchar('\n');
}
return 0;
}