Luogu | P4137 [高2021级考试 19.5.4] RMQ Problem / mex | 数据结构 / 莫队 | 离线 / 线段树

Description

给定一个长度为 $N$ 的数列 $A$ ，数列的第 $i$ 个元素是 $A_i$（从$1$开始编号）。你需要回答 $q$ 个询问，每个询问的参数是一个二元组 $(l,r)$，表示查询 $mex({A[l],A[l+1],…,A[r]})$ 的值。

所谓 $mex$ ，就是 $SG$ 定理中那个函数，也就是 Mininum Exclusive 的缩写。对一个一个非负整数组成的集合 $S$ ，$mex(S)$ 的值等于最小的不属于集合 $S$ 的非负整数。

Input Format

第一行包含 $2$ 个空格分开的整数 $N,Q$ ，代表序列 $A$ 的长度和询问个数。

第二行包含 $N$ 个空格隔开的非负整数，第 $i$ 个整数表示 $A_i$ 的值。

接下来的 $Q$ 行 ，每行包含 $2$ 个空格分开的正整数 $l$ 和 $r$ ，表示一个查询参数。

Output Format

包含 $Q$ 行，每行一个正整数，表示对应询问的答案。

Input Sample

Sample 01

7 5
0 2 1 0 1 3 2
1 3
2 3
1 4
3 6
2 7

Output Sample

Sample 01

3
0
3
2
4

Data Range

$ 1 \le N,Q \le 2 \times 10^5 $，$ 0 \le A_i \le 10^9 $。

Solution

与前一道题类似，这里要用到离线 + 离散化。先将问题按照右端点排序。

使用 $l_i$ 维护值为 $i$ 的元素当前在最右边出现的位置。用线段树维护 $l_i$ （合并时取最小值），每次询问$(ql,qr)$则在树上查询一个满足 $i$ 最小并且 $l_i < ql$ 的元素。可以由集合线段树的 kth 操作修改而来。随着序列向右扫描的过程回答询问即可。

需要注意的一点是，在离散化的过程中，对于任意一个初始序列中的元素 $x$ ，需要将 $x-1$ 和 $x+1$ 都加入集合中（这样才能回答出“没有出现过的数字”）。当然，如果 $x=0$ 就不用添加 $x-1$ 了。

当然，也可以莫队 / 可持久化（不用离线）。如果你闲得慌，还可以动态开点（不用离散化）。

Code

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>

#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
#define swap(x,y) {int t=x; x=y,y=t;}
#define wipe(x,y) memset(x,y,sizeof(x))
#define dbgIn(x) freopen(x".in","r+",stdin)
#define rep(x,y,z) for(int x=y,I=z;x<=I;++x)
#define dbgOut(x) freopen(x".out","w+",stdout)
#define file(x) freopen(x".in","r+",stdin); freopen(x".out","w+",stdout)

#define LC lch[now]
#define RC rch[now]
#define mid ((L+R)>>1)

using std::sort;
using std::lower_bound;

inline void Read(int &x){
    x=0; char ch=0; while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return;
}

struct data{
    int ql,qr,id;
    friend bool operator < (data a,data b){
        if(a.qr==b.qr) return a.ql<b.ql;
        return a.qr<b.qr;
    }
}q[200005];

int root,node,N,Q,po,lim;
int src[200005],srt[600005],ans[200005],minv[1200005],lch[1200005],rch[1200005];

void upload(int now){
    minv[now]=min(minv[LC],minv[RC]); return;
}

void build(int &now,int L,int R){
    now=++node; if(L==R) return;
    build(LC,L,mid); build(RC,mid+1,R); return;
}

void modify(int now,int L,int R,int pos,int val){
    if(L==R){ minv[now]=val; return; }
    if(pos<=mid) modify(LC,L,mid,pos,val);
    else modify(RC,mid+1,R,pos,val); upload(now);
}

int query(int now,int L,int R,int K){
    if(L==R) return L;
    if(minv[LC]<K) return query(LC,L,mid,K);
    else return query(RC,mid+1,R,K);
}

int main(){
    Read(N); Read(Q);
    rep(i,1,N) { Read(src[i]); srt[i]=src[i]; }
    sort(srt+1,srt+1+N); po=N; srt[0]=-2;
    rep(i,1,N){ if(srt[i]==srt[i-1]) continue;
        if(srt[i]!=0)srt[++po]=srt[i]-1; srt[++po]=srt[i]+1;
    }sort(srt+1,srt+1+po); srt[++po]=0x7f7f7f7f;
    rep(i,1,po) if(srt[i]==srt[i-1]) srt[i-1]=0x7f7f7f7f;
    sort(srt+1,srt+1+po);
    build(root,1,lim=lower_bound(srt+1,srt+1+po,0x7f7f7f7f)-srt);
    rep(i,1,N) src[i]=lower_bound(srt+1,srt+1+lim,src[i])-srt;
    rep(i,1,Q) { Read(q[i].ql); Read(q[i].qr); q[i].id=i; }
    sort(q+1,q+1+Q); int j=1; rep(i,1,N){
        modify(root,1,lim,src[i],i);
        while(q[j].qr==i){
            ans[q[j].id]=srt[query(root,1,lim,q[j].ql)]; j++;
        }
    }rep(i,1,Q) printf("%d\n",ans[i]);
    return 0;
}