BZOJ 3585: mex【莫队+树状数组】-白红宇

BZOJ 3585: mex【莫队+树状数组】

阅读量：5071 次

发布时间：2019-06-12

本文共 1073 字，大约阅读时间需要 3 分钟。

3585: mex

【题目描述】

【题解】

其实和BZOJ3339一模一样，当Ai>n时这个Ai对答案没有影响，这是肯定的，那么读入时处理一下就可以了。

代码如下

#pragma GCC optimize(2)#include
    
     #include
     
      #include
      
       #include
       
        #define MAXN 200005using namespace std;int n,q,K,tot,a[MAXN],f[MAXN],hsh[MAXN],Ans[MAXN];struct xcw{    int L,R,id;    bool operator <(const xcw b)const{
   return (L/K
        
         >1;L<=R;mid=(R+L)>>1) if(mid==get(mid)) L=mid+1;else Ret=mid,R=mid-1;    return Ret;}int main(){    #ifndef ONLINE_JUDGE    freopen("prob.in","r",stdin);    freopen("prob.out","w",stdout);    #endif    n=read(),q=read();K=sqrt(n);    for(int i=1;i<=n;i++) a[i]=read()+1,a[i]=(a[i]>200001?200002:a[i]),tot=max(a[i],tot);    for(int i=1;i<=q;i++) Q[i]=(xcw){read(),read(),i};    sort(Q+1,Q+1+q);    int L=1,R=0;    for(int i=1;i<=q;i++){        while(L
         
          <=n) Del(L++); while(L>Q[i].L&&L>2) Add(--L); while(R
          
           
            Q[i].R&&R>0) Del(R--); Ans[Q[i].id]=Fnd()-1; } for(int i=1;i<=q;i++) printf("%d\n",Ans[i]); return 0;}