bzoj3339 rmq problem (range mex query)

时间：2022-08-25 04:30:25

给一个长度为n的数列a，q个询问，每次询问一段区间的mex。（没有出现过的最小非负整数）

1<=n,q<=200000，0<=ai<=200000。

题解1 莫队

我们将权值分成根号块，记录每个权值的出现次数和每块内有多少权值出现过。

修改和询问就直接暴力做就行。

修改O(1)，询问O(sqrt(n))，加在一起还是O((n+q)sqrt(n+q))。

#include <iostream>

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

#include <algorithm>

using namespace std;

#define SZ 666666

int n,q,a[SZ],ts[SZ],tc[SZ],gg,bk,anss[SZ];

void edt(int p,int x)

{

    tc[p/gg]-=(bool)ts[p];

    ts[p]=x;

    tc[p/gg]+=(bool)ts[p];

}

struct query {int l,r,id;} qs[SZ];

bool operator < (query a,query b)

{

    int ap=a.l/bk, bp=b.l/bk;

    if(ap==bp) return a.r<b.r;

    return ap<bp;

}

void add(int p) {edt(p,ts[p]+1);}

void del(int p) {edt(p,ts[p]-1);}

#define gc getchar()

int g_i()

{

    int tmp=0; bool fu=0; char s;

    while(s=gc,s!='-'&&(s<'0'||s>'9')) ;

    if(s=='-') fu=1; else tmp=s-'0';

    while(s=gc,s>='0'&&s<='9') tmp=tmp*10+s-'0';

    if(fu) return -tmp; else return tmp;

}

#define gi g_i()

#define pob

#define pc(x) putchar(x)

namespace ib {char b[100];}

inline void pint(int x)

{

    if(x==0) {pc(48); return;}

    if(x<0) {pc('-'); x=-x;}

    char *s=ib::b;

    while(x) *(++s)=x%10, x/=10;

    while(s!=ib::b) pc((*(s--))+48);

}

int main()

{

    n=gi, q=gi;

    for(int i=1;i<=n;i++) a[i]=gi;

    gg=sqrt(200000);

    bk=min(int(sqrt(n)+1),n);

    for(int i=1;i<=q;i++) qs[i].id=i, qs[i].l=gi, qs[i].r=gi;

    sort(qs+1,qs+1+q);

    int cl=1,cr=0;

    for(int i=1;i<=q;i++)

    {

        int l=qs[i].l,r=qs[i].r;

        while(cr<r) add(a[++cr]);

        while(cr>r) del(a[cr--]);

        while(cl>l) add(a[--cl]);

        while(cl<l) del(a[cl++]);

        int nof=0;

        for(int j=0;;j++)

        {

            if(tc[j]!=gg) {nof=j; break;}

        }

        for(int j=nof*gg;;j++)

        {

            if(!ts[j]) {anss[qs[i].id]=j; break;}

        }

    }

    for(int i=1;i<=q;i++) {pint(anss[i]); pc(10);}

}

题解2 线段树

我们这么考虑，从小到大加入所有权值。如果有一个权值正好没有经过，这个权值就可以作为答案，就可以退出了。

现在我们考虑对于一个权值，所有不包括它的区间都可以以它作为答案，那么我们就把同样是这个权值的搞出来，那么这个序列就会被搞成几段，那么每一段内的询问都可以更新答案。

那么我们就二维线段树即可。我tm才不想写

相关文章