AC日记——Rmq Problem bzoj 3339

3339

思路；

　　恶心；

代码：

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define maxn 200005

struct TreeNodeType {

    int l,r,dis,mid,flag;

    bool if_;

};

struct TreeNodeType tree[maxn<<];

struct QueryType {

    int l,r,id;

};

struct QueryType qu[maxn];

int n,m,ai[maxn],sg[maxn],ans[maxn],Next[maxn],last[maxn];

int num[maxn];

inline void in(int &now)

{

    char Cget=getchar();now=;

    while(Cget>''||Cget<'') Cget=getchar();

    while(Cget>=''&&Cget<='')

    {

        now=now*+Cget-'';

        Cget=getchar();

    }

}

void tree_build(int now,int l,int r)

{

    tree[now].l=l,tree[now].r=r;

    if(l==r) { tree[now].dis=sg[l];return; }

    tree[now].mid=l+r>>;

    tree_build(now<<,l,tree[now].mid);

    tree_build(now<<|,tree[now].mid+,r);

    tree[now].dis=min(tree[now<<].dis,tree[now<<|].dis);

}

void tree_down(int now)

{

    tree[now<<].dis=min(tree[now<<].dis,tree[now].flag);

    tree[now<<|].dis=min(tree[now<<|].dis,tree[now].flag);

    if(tree[now<<].if_) tree[now<<].flag=min(tree[now<<].flag,tree[now].flag);

    else tree[now<<].flag=tree[now].flag,tree[now<<].if_=true;

    if(tree[now<<|].if_) tree[now<<|].flag=min(tree[now<<|].flag,tree[now].flag);

    else tree[now<<|].flag=tree[now].flag,tree[now<<|].if_=true;

    tree[now].if_=false;return ;

}

void tree_change(int now,int l,int r,int x)

{

    if(tree[now].l==l&&tree[now].r==r)

    {

        tree[now].dis=min(tree[now].dis,x);

        if(tree[now].if_) tree[now].flag=min(tree[now].flag,x);

        else tree[now].flag=x,tree[now].if_=true;

        return ;

    }

    if(tree[now].if_) tree_down(now);

    if(r<=tree[now].mid) tree_change(now<<,l,r,x);

    else if(l>tree[now].mid) tree_change(now<<|,l,r,x);

    else tree_change(now<<,l,tree[now].mid,x),tree_change(now<<|,tree[now].mid+,r,x);

    tree[now].dis=min(tree[now<<].dis,tree[now<<|].dis);

}

int tree_query(int now,int to)

{

    if(tree[now].l==tree[now].r) return tree[now].dis;

    if(tree[now].if_) tree_down(now);

    if(to<=tree[now].mid) return tree_query(now<<,to);

    else return tree_query(now<<|,to);

}

bool cmp(QueryType aa,QueryType bb)

{

    return aa.l<bb.l;

}

int main()

{

    freopen("mex.in","r",stdin);

    freopen("mex.out","w",stdout);

    in(n),in(m);int now=;

    for(int i=;i<=n;i++) in(ai[i]);

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

    {

        num[ai[i]]++;

        while(num[now]) now++;

        sg[i]=now;

        if(last[ai[i]]) Next[last[ai[i]]]=i;

        last[ai[i]]=i;

    }

    sg[n+]=now;tree_build(,,n);

    for(int i=;i<=n;i++) if(!Next[i]) Next[i]=n+;

    for(int i=;i<=m;i++) in(qu[i].l),in(qu[i].r),qu[i].id=i;

    sort(qu+,qu+m+,cmp),now=;

    for(int no=;no<=m;no++)

    {

        while(now<qu[no].l) tree_change(,now,Next[now]-,ai[now]),now++;

        ans[qu[no].id]=tree_query(,qu[no].r);

    }

    for(int i=;i<=m;i++) printf("%d\n",ans[i]);

    return ;

}