洛谷4137 mex题解 主席树

题目链接

虽然可以用离线算法水过去，但如果强制在线不就gg了。

所以要用在线算法。

首先，所有大于n的数其实可以忽略，因为mex的值不可能大于n

我们来设想一下，假设已经求出了从0到n中所有数在原序列中小于r时最后出现的位置，用k[i]来表示

那么显然mex（l,r）就是小于l的最小的k[j]中最小的下标，显然可以维护一下最小值，用二分来求。

然后建一颗主席数，root[i]表示此时考虑到了i，每次询问l,r时访问root[r]然后求一下就行了

复杂度时O(nlogn);

# include<iostream>

# include<cstdio>

# include<algorithm>

# include<cmath>

const int mn=200010;

const int inf = 100000000;

inline int min(int x,int y)

{

    return x>y ? y : x;

}

int c[mn],tree[mn*25],left[mn*25],right[mn*25],root[mn];

int j,k,t,n,m,tot,ans;

void add(int &x,int y,int l,int r,int a,int b){

    x=++tot;

    tree[x]=tree[y];

    left[x]=left[y];

    right[x]=right[y];

    if (l==r){

        tree[x]=b;

        return;

    }

    int mid=(l+r)/2;

    if (a<=mid)

    add(left[x],left[y],l,mid,a,b);

    else add(right[x],right[y],mid+1,r,a,b);

    tree[x]=min(tree[left[x]],tree[right[x]]);

}

int query(int x,int l,int r,int a){

    if (l==r) return l;

    int mid=(l+r)/2;

    if (tree[left[x]]>=a)

       return query(right[x],mid+1,r,a);

    else return query(left[x],l,mid,a);

}

int main(){

    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++){

        scanf("%d",&c[i]);

        add(root[i],root[i-1],0,inf,c[i],i);

    }

      while (m--){

        scanf("%d%d",&j,&k);

        ans=query(root[k],0,inf,j);

        printf("%d\n",ans);

      }

    return 0；
}