BZOJ 3585: mex(分块+莫队)

##解题思路
　　首先直接莫队是能被卡的，时间复杂度不对。就考虑按照值域先进行分块再进行莫队，然后统计答案的时候就暴力扫所有的块，直到一个块内元素不满，再暴力扫这个块就行了，时间复杂度O(msqrt(n))

##代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

const int N=200005;

const int SIZ=600;

inline int rd(){

    int x=0,f=1;char ch=getchar();

    while(!isdigit(ch)) f=ch=='-'?0:1,ch=getchar();

    while(isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();

    return f?x:-x;

}

int n,m,a[N],bl[N],siz,l[SIZ],r[SIZ],cnt[N],sum[SIZ],ans[N],num;

struct Query{

    int ql,qr,id;

    friend bool operator<(const Query A,const Query B){

        if(A.ql/siz!=B.ql/siz) return A.ql<B.ql;

        if((A.ql/siz)&1) return A.qr>B.qr;

        return A.qr<B.qr;

    }

}q[N];

inline void del(int x){

    if(a[x]>n) return;

    cnt[a[x]]--;if(!cnt[a[x]]) sum[bl[a[x]]]--;

}

inline void add(int x){

    if(a[x]>n) return ;

    if(!cnt[a[x]]) sum[bl[a[x]]]++;cnt[a[x]]++;

}

inline int query(){

    if(!cnt[0]) return 0;int pos=-1;

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

        if(sum[i]!=r[i]-l[i]+1) {pos=i;break;}

    if(pos==-1) return n+1;

    for(int i=l[pos];i<=r[pos];i++)

        if(!cnt[i]) return i;

}

int main(){

    n=rd(),m=rd();siz=sqrt(n)+1;num=n/siz+(n%siz!=0);

    for(int i=1;i<=n;i++) a[i]=rd(),bl[i]=(i-1)/siz+1;

    for(int i=1;i<=num;i++) l[i]=(i-1)*siz+1,r[i]=i*siz;r[num]=n;

    for(int i=1;i<=m;i++) q[i].ql=rd(),q[i].qr=rd(),q[i].id=i;

    sort(q+1,q+1+m);int L=1,R=0;

    for(int i=1;i<=m;i++){

        while(L<q[i].ql) {del(L);L++;}

        while(L>q[i].ql) {L--;add(L);}

        while(R<q[i].qr) {R++;add(R);}

        while(R>q[i].qr) {del(R);R--;}

        ans[q[i].id]=query();

    }

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

    return 0;

}

巴特西

BZOJ 3585: mex(分块+莫队)

最新文章

热门文章