主席樹
題目傳送門
神題。。。滾去看題解了。。。
假設我們現在可以表示 [1,n] 中的數,那麼對于一個新加的數x,有以下兩種情況:
1: x<=n+1 ,這時我們可以表示出 [1,n+x] 中的所有數字,答案變為 n+x+1
2: x>n+1 ,這時 n+1 這個數必定不能被表示。此時答案即為 n+1
那麼我們在詢問的時候,先假設 ans=1 ,每次計算這個區間中所有小于等于 ans 的值 ret ,如果 ret<ans ,說明接下來這個數一定是大于 ans 的,即 ans 不能被表示,此時輸出答案。否則更新 ans=ret+1 。
代碼:
#include<cctype>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100000
using namespace std;
struct tree{
int ls,rs,sum;
}t[N<<];
int n,m,nd,num,rt[N+],a[N+];
inline char readc(){
static char buf[],*l=buf,*r=buf;
if (l==r) r=(l=buf)+fread(buf,,,stdin);
if (l==r) return EOF; return *l++;
}
inline int _read(){
int x=,f=; char ch=readc();
while (!isdigit(ch)) { if (ch=='-') f=-; ch=readc(); }
while (isdigit(ch)) x=x*+ch-,ch=readc();
return x*f;
}
inline void _write(int x){
if(x<) putchar('-'),x=-x;
if(x>) _write(x/); putchar(x%+'0');
}
void build(int &x,int fa,int l,int r,int p){
t[x=++nd].sum=t[fa].sum+p;
if (l==r) return; int mid=l+r>>;
t[x].ls=t[fa].ls,t[x].rs=t[fa].rs;
if (p<=mid) build(t[x].ls,t[fa].ls,l,mid,p);
else build(t[x].rs,t[fa].rs,mid+,r,p);
}
int srch(int p,int q,int l,int r,int k){
if (k>=r) return t[q].sum-t[p].sum;
int mid=l+r>>,lp=t[p].ls,lq=t[q].ls;
if (mid>=k) return srch(lp,lq,l,mid,k);
return t[lq].sum-t[lp].sum+srch(t[p].rs,t[q].rs,mid+,r,k);
}
int main(){
n=_read();
for (int i=;i<=n;i++)//∑a[i]<=1e9,懶得離散了
build(rt[i],rt[i-],,,_read());
for (m=_read();m;m--){
int l=_read(),r=_read(),ans=;
while (){
int ret=srch(rt[l-],rt[r],,,ans);
if (ret<ans) break; ans=ret+;
}
_write(ans),putchar('\n');
}
return ;
}