HUAS 1483 mex(离线+线段树)

实在是太弱了。。。。

考虑离线，从mex[l,r]向mex[l,r+1]转移，显然是没啥东西可以记录的。。。

从mex[l,r]向mex[l+1,r]转移，记x=mex[l,r],如果[l+1,r]不出现a[l]的话，那么mex[l+1,r]=min(mex[l,r],a[l]).

有了这个性质的话，就可以考虑离线了。先预处理一遍to[]和mex[]，to[i]表示i的后面下一个出现a[i]的数组下标，mex[i]表示mex[1,i]。

把询问按左端点升序排序，对于当前的左端点为1的排序，可以直接输出它的mex值。

当左端点向右移一位的时候，mex[2,j]=min(mex[1,j],a[1]).(j<to[1]).

如果暴力修改的话还是会超时的。

很幸运mex数组是单调非递减的。那么我们可以用线段树把区间[2,j]上的值取个min。用tag思想的话很容易做到logn。

# include <cstdio>

# include <cstring>

# include <cstdlib>

# include <iostream>

# include <vector>

# include <queue>

# include <stack>

# include <map>

# include <set>

# include <cmath>

# include <algorithm>

using namespace std;

# define lowbit(x) ((x)&(-x))

# define pi 3.1415926535

# define eps 1e-

# define MOD

# define INF

# define mem(a,b) memset(a,b,sizeof(a))

# define FOR(i,a,n) for(int i=a; i<=n; ++i)

# define FO(i,a,n) for(int i=a; i<n; ++i)

# define bug puts("H");

# define lch p<<,l,mid

# define rch p<<|,mid+,r

# define mp make_pair

# define pb push_back

typedef pair<int,int> PII;

typedef vector<int> VI;

# pragma comment(linker, "/STACK:1024000000,1024000000")

typedef long long LL;

int Scan() {

    int res=, flag=;

    char ch;

    if((ch=getchar())=='-') flag=;

    else if(ch>=''&&ch<='') res=ch-'';

    while((ch=getchar())>=''&&ch<='')  res=res*+(ch-'');

    return flag?-res:res;

}

void Out(int a) {

    if(a<) {putchar('-'); a=-a;}

    if(a>=) Out(a/);

    putchar(a%+'');

}

const int N=;

//Code begin...

struct Node{int l, r, id;}node[N];

int seg[N<<], a[N], mex[N], vis[N], to[N], now, tag[N<<], ans[N], res;

bool comp(Node a, Node b){return a.l<b.l;}

void init(int p, int l, int r){

    if (l<r) {

        int mid=(l+r)>>;

        init(lch); init(rch); return ;

    }

    seg[p]=mex[l];

}

void push_down(int p, int l, int r){

    if (tag[p]==-) return ;

    if (l==r) seg[p]=min(seg[p],tag[p]);

    else {

        tag[p<<]=(tag[p<<]==-?tag[p]:min(tag[p],tag[p<<]));

        tag[p<<|]=(tag[p<<|]==-?tag[p]:min(tag[p],tag[p<<|]));

    }

    tag[p]=-;

}

void update(int p, int l, int r, int L, int R, int val){

    if (L>r||R<l) return ;

    push_down(p,l,r);

    if (L<=l&&R>=r) tag[p]=val;

    else {

        int mid=(l+r)>>;

        update(lch,L,R,val); update(rch,L,R,val);

    }

}

void query(int p, int l, int r, int L){

    if (L>r||L<l) return ;

    push_down(p,l,r);

    if (L==r&&L==l) res=seg[p];

    else {

        int mid=(l+r)>>;

        query(lch,L); query(rch,L);

    }

}

int main ()

{

    int n, q;

    mem(tag,-);

    n=Scan(); q=Scan();

    FOR(i,,n) {

        a[i]=Scan();

        if (vis[a[i]]) to[vis[a[i]]]=i;

        vis[a[i]]=i;

        while (vis[now]) ++now;

        mex[i]=now;

    }

    FOR(i,,n) if (!to[i]) to[i]=n+;

    FOR(i,,q) node[i].l=Scan(), node[i].r=Scan(), node[i].id=i;

    sort(node+,node+q+,comp);

    now=;

    init(,,n);

    FOR(i,,q) {

        while (now!=node[i].l) {

            if (now+<=to[now]-) update(,,n,now+,to[now]-,a[now]);

            ++now;

        }

        query(,,n,node[i].r);

        ans[node[i].id]=res;

    }

    FOR(i,,q) printf("%d\n",ans[i]);

    return ;

}