传送门

然而是权限题

Solution

发现题目给出的一些规律，emm，如果我们新凑出来的一个数，那么后面一个数一定是\(sum+1\)。

于是就可以主席树随便维护了！

代码实现

#include
    
     using namespace std;inline int gi(){int x;scanf("%d",&x);return x;}const int N=100010;int rt[N],tot;int n,a[N];struct node{    int ls,rs,val;}t[N*200];void modify(int&x,int l,int r,int pos){    t[++tot]=t[x];    x=tot;    t[x].val+=pos;    if(l==r)return;    int mid=(l+r)>>1;    if(pos<=mid)modify(t[x].ls,l,mid,pos);    else modify(t[x].rs,mid+1,r,pos);}int query(int x,int y,int l,int r,int pos){    if(l==r)return t[y].val-t[x].val;    int mid=(l+r)>>1;    if(pos<=mid)return query(t[x].ls,t[y].ls,l,mid,pos);    else return query(t[x].rs,t[y].rs,mid+1,r,pos)+t[t[y].ls].val-t[t[x].ls].val;}int main(){    n=gi();    for(int i=1;i<=n;i++)a[i]=gi();    for(int i=1;i<=n;i++)    {        rt[i]=rt[i-1];        modify(rt[i],1,1e9,a[i]);    }    int m=gi();    while(m--)    {        int l=gi(),r=gi(),ans=0;        while(ans<1e9)        {            int sum=query(rt[l-1],rt[r],1,1e9,ans+1);            if(sum==ans)break;            ans=sum;        }        printf("%d\n",ans+1);    }    return 0;}