HUAS 1483 mex(莫队算法)-白红宇

HUAS 1483 mex(莫队算法)

阅读量：5138 次

发布时间：2019-06-13

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

考虑莫队算法，对于区间减小的情况，可以O(1)解决。对于区间增加的情况，可能需要O(n)解决。好在数据不卡莫队。

1200ms过了。

离线+线段树 760ms过了。

# include 
      
       # include 
       
        # include 
        
         # include 
         
          # include 
          
           # include 
           
            # include 
            
             # include 
             # include 
              
               # include 
               
                # include 
                
                 using namespace std;# define lowbit(x) ((x)&(-x))# define pi 3.1415926535# define eps 1e-9# define MOD 1000000009# define INF 1000000000# define mem(a,b) memset(a,b,sizeof(a))# define FOR(i,a,n) for(int i=a; i<=n; ++i)# define FO(i,a,n) for(int i=a; i
                 
                   PII;typedef vector
                  
                    VI;# pragma comment(linker, "/STACK:1024000000,1024000000")typedef long long LL;int Scan() { int res=0, flag=0; char ch; if((ch=getchar())=='-') flag=1; else if(ch>='0'&&ch<='9') res=ch-'0'; while((ch=getchar())>='0'&&ch<='9') res=res*10+(ch-'0'); return flag?-res:res;}void Out(int a) { if(a<0) {putchar('-'); a=-a;} if(a>=10) Out(a/10); putchar(a%10+'0');}const int N=200005;//Code begin...struct Node{ int l, r, l1, id;}node[N];int a[N], ans[N], unit, q, num[N];bool comp(Node a, Node b){ if (a.l1!=b.l1) return a.l1
                   
                    node[i].r) { --num[a[r]]; if (a[r]
                    
                     node[i].l) { --l; ++num[a[l]]; if (a[l]!=tmp) continue; for (int now=tmp+1; ; ++now) if (!num[now]) {tmp=now; break;} } ans[node[i].id]=tmp; }}int main (){ int n; n=Scan(); q=Scan(); unit=(int)sqrt(n); FOR(i,1,n) a[i]=Scan(); FOR(i,1,q) node[i].l=Scan(), node[i].r=Scan(), node[i].id=i, node[i].l1=node[i].l/unit; sort(node+1,node+q+1,comp); sol(); FOR(i,1,q) Out(ans[i]), putchar('\n'); return 0;}