大鸽子 llmmkk 正在补8.3号咕掉的题
时隔两个月，再看到这道题，我又是一脸懵，这种思维的培养太重要了
链接：
P4587
题意：
给出 \(n\) 个点的序列，\(m\) 次询问区间神秘数。
神秘数定义为最小的不能被序列的子集的和表示的正整数。
如序列 \(\{1,1,4,1,13\}\) 的神秘数是 \(8\)。
分析：
这题重点在神秘数的求法，先考虑暴力求法，由于定义是序列子集，那么首先考虑将该区间排序，可能会得到一些有用的性质。
假设当前能够表示的区间是 \([1,sum]\)，对于当前的数 \(x\) 。
- \(x>sum+1\)，那么答案就是 \(sum+1\)。
\(x\leq sum+1\)，那么能够表示的区间将会变成 \([1,sum+x]\)，继续考虑下一个数。
仔细想一下会发现这个暴力很对。
然后考虑优化，暴力是一个一个判断并处理的，我们考虑一次性处理多个 \(x\)。于是正解就是：
假设当前能够表示的区间是 \([1,sum]\)，记区间内所有小于等于 \(sum\) 的 \(x\) 之和为 \(res\)。
- \(res+1>sum\)，那么将 \(sum\) 更新为 \(res+1\)
\(res+1\leq sum\) ，那么答案就是 \(sum+1\)
仔细想想这个东西，发现它成功做到了上面的优化，同时它的正确性也很对。因为这个做法实在太难以言传了，所以可以再参考一下这篇
时间复杂度分析：假如当前的神秘数为 \(s1\)，下一个神秘数是 \(s2\)，再下一个是 \(s3\)，那么从 \(s2\) 到 \(s3\) 相比从 \(s1\) 到 \(s2\) 多出来的 \(x\) 一定是大于 \(s1\) 的，所以 \(ans\) 是成倍增长的，于是这个做法的复杂度就是 \(O(\log\sum a)\)
算法：
于是我们需要一个东西能够维护区间内某个值域的数值之和。可以在每个位置维护一个从 \(1\) 到当前位置的权值线段树，拉到主席树上，然后两个区间查询相减就可以做到。
主席树 \(O(n\log n)\)，上面的算法 \(O(\log\sum a)\)，所以总复杂度 \(O(n\log n\log\sum a)\)。
代码：
#include <bits/stdc++.h>
using namespace std;
#define in read()
inline int read(){
int p=0,f=1;
char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){p=p*10+c-'0';c=getchar();}
return p*f;
}
const int N=1e5+5;
int n,m;
int a[N],q[N],qn,w[N];
int bin(int key){
int l=1,r=qn,mid;
while(l<r){
mid=(l+r+1)>>1;
if(q[mid]<=key)l=mid;
else r=mid-1;
}
return l;
}
int rt[N];
int tot,sum[N<<5],lc[N<<5],rc[N<<5];
int newnode(){
++tot;
sum[tot]=lc[tot]=rc[tot]=0;
return tot;
}
void pushup(int p){
sum[p]=sum[lc[p]]+sum[rc[p]];
}
int fi_built(int l,int r){
int p=newnode();
if(l==r){return p;}
int mid=(l+r)>>1;
lc[p]=fi_built(l,mid);
rc[p]=fi_built(mid+1,r);
return p;
}
int built(int l,int r,int pre,int x,int d){
int now=newnode(),mid=(l+r)>>1;
sum[now]=sum[pre],lc[now]=lc[pre],rc[now]=rc[pre];
if(l==r){sum[now]+=d*q[l];return now;}
if(x<=mid)lc[now]=built(l,mid,lc[now],x,d);
else rc[now]=built(mid+1,r,rc[now],x,d);
pushup(now);
return now;
}
int query(int l,int r,int p,int ql,int qr){
if(ql>qr)return 0;
if(l>=ql&&r<=qr)return sum[p];
int mid=(l+r)>>1,res=0;
if(ql<=mid)res+=query(l,mid,lc[p],ql,qr);
if(qr>mid)res+=query(mid+1,r,rc[p],ql,qr);
return res;
}
signed main(){
n=in;
for(int i=1;i<=n;i++)
a[i]=in,q[i]=a[i];
sort(q+1,q+1+n);
qn=unique(q+1,q+1+n)-(q+1);
rt[0]=fi_built(1,n);
for(int i=1;i<=n;i++)
rt[i]=built(1,n,rt[i-1],bin(a[i]),1);
m=in;
for(int i=1;i<=m;i++){
int l=in,r=in;
int ans=1,tans=bin(ans);
int que=query(1,n,rt[r],1,tans)-query(1,n,rt[l-1],1,tans);
while(que+1>ans){
ans=que+1;
tans=bin(ans);
que=query(1,n,rt[r],1,tans)-query(1,n,rt[l-1],1,tans);
}
cout<<ans<<'\n';
}
return 0;
}