区间MEX ||| 题解

zxf1127 · 2025-07-19 23:21:53 · 个人记录

P4137 Rmq Problem / mex

友链

思路

说白了就是查找[l,r]中没有出现的最小值

发现记录数x最后一次出现的位置pos[x]

如果pos[x]<=l,那么[l,r]没有出现x

那么考虑在权值线段树二分查找

code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int tree[N*4],a[N];
int ls(int x) {return x*2;}
int rs(int x) {return x*2+1;}
void push_up(int x)
{
    tree[x]=min(tree[ls(x)],tree[rs(x)]);
    return ;
}
void rework(int l,int r,int x,int lx,int rx,int d)
{
    if(l<=lx&&rx<=r)
    {
        tree[x]=d;
        return;
    }
    int mid=(lx+rx)>>1;
    if(l<=mid) rework(l,r,ls(x),lx,mid,d);
    if(mid+1<=r) rework(l,r,rs(x),mid+1,rx,d);
    push_up(x);
    return ;
}
int data(int p,int x,int lx,int rx)
{
    if(lx==rx)return lx;
    int mid=(lx+rx)>>1;
    if(tree[ls(x)]<p)
    {
        return data(p,ls(x),lx,mid);
    }
    else return data(p,rs(x),mid+1,rx);
}
int ans[N];
struct no{
int id,l;
};
vector<no> q[N];
signed main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    int cur=0;
    for(int i=1;i<=m;i++)
    {
        int aa,bb;
        cin>>aa>>bb;
        q[bb].push_back((no){++cur,aa});
    }
    for(int i=1;i<=n;i++)
    {
        rework(a[i],a[i],1,0,2e5,i);
        for(int j=0;j<q[i].size();j++) ans[q[i][j].id]=data(q[i][j].l,1,0,2e5);
    }
    for(int i=1;i<=m;i++) cout<<ans[i]<<endl;
    return 0;
}