[bzoj3585]mex

题目大意

求区间mex

主席树

我们建立主席树，对于第r棵线段树每一个位置i存储的是数字i出现的最右端。
那么对于区间询问l~r，就是找到第r棵线段树的最大前缀区间，满足区间内每个数的最右出现位置都不小于l。
这个很容易，我们只需要维护区间最小值，询问时如果左区间的区间最小值小于l说明mex在左区间否则mex在右区间。
于是复杂度降为n log n。

#include<cstdio>
#include<algorithm>
#include<set>
#define fo(i,a,b) for(i=a;i<=b;i++)
using namespace std;
const int maxn=200000+10,maxd=100000000;
int a[maxn],tree[maxn*30],left[maxn*30],right[maxn*30],root[maxn];
int i,j,k,l,t,n,m,tot,ans;
void insert(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) insert(left[x],left[y],l,mid,a,b);else insert(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);
    fo(i,1,n){
        scanf("%d",&a[i]);
        insert(root[i],root[i-1],0,maxd,a[i],i);
    }
    while (m--){
        scanf("%d%d",&j,&k);
        ans=query(root[k],0,maxd,j);
        printf("%d\n",ans);
    }
}


莫队算法

如果你想练莫队这题可以直接上莫队哦！
弄一个桶，然后就可以维护mex了。可以证明mex的移动所造成的时间上限等同于曼哈顿距离和。
复杂度带根号，我并没有打这种算法。