P4587 [FJOI2016]神秘数
一道主席树的模板题
我们先考虑暴力的做法，对于区间[l,r]，我们先把里面的a[i]进行升序排序。设当前可以表示的数为[1,mx]，对于要插入的数a[i]，有两种可能：
- \(a_i<=mx+1，可以表示的数的范围变为[1,mx+a_i]\)
- \(a_i>mx+1，无法表示mx+1，停止加入\)
然后对暴力做法进行优化。
设已经加入了的数字的范围为[1,mx]，可以表示的数字的范围为[1,pos];
首先可以知道，新加入的数的值肯定在[1,pos+1]里面，而小于mx的数已经被加入了，所以我们要加入值在[mx+1,pos+1]范围内的数。把值在[mx+1,pos+1]中的数的和记为sum，如果sum=0，则无法加入，输出pos+1；如果sum!=0，mx=pos+1，pos+=sum；
点击查看代码
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
const int N=1e5+5;
int n,m,tot,a[N],maxn,rt[N];
struct ww{
int val,ls,rs;
}tr[N<<5];
void insert(int &p,int pre,int l,int r,int x){
p=++tot;
tr[p]=tr[pre];tr[p].val+=x;
if(l>=r)return ;
int mid=(l+r)>>1;
if(x<=mid){
insert(tr[p].ls,tr[pre].ls,l,mid,x);
}
else{
insert(tr[p].rs,tr[pre].rs,mid+1,r,x);
}
}
int query(int p,int q,int l,int r,int x,int y){
if(tr[p].val==tr[q].val)return 0;
if(x<=l&&r<=y)return tr[q].val-tr[p].val;
int mid=(l+r)>>1,res=0;
if(x<=mid)res+=query(tr[p].ls,tr[q].ls,l,mid,x,y);
if(y>mid)res+=query(tr[p].rs,tr[q].rs,mid+1,r,x,y);
return res;
}
int main(){
n=read();
for(int i=1;i<=n;i++){
a[i]=read();
maxn=max(maxn,a[i]);
}
for(int i=1;i<=n;i++){
insert(rt[i],rt[i-1],1,maxn,a[i]);
}
m=read();int x,y;
for(int i=1;i<=m;i++){
x=read(),y=read();
int mx=0,pos=0;
while(1){
int sum=query(rt[x-1],rt[y],1,maxn,mx+1,pos+1);
if(!sum)break;
mx=pos+1;pos+=sum;
}
printf("%d\n",pos+1);
}
return 0;
}