NBUT1457 Sona 莫队算法-白红宇

NBUT1457 Sona 莫队算法

阅读量：5142 次

发布时间：2019-06-13

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

由于10^9很大，所以先离散化一下，把给你的这一段数哈希时间复杂度O(nlogn)

然后就是分块莫队已知[L,R],由于事先的离散化，可以在O(1)的的时间更新[l+1,r],[l,r+1],[l-1,r],[l,r-1]时间复杂度O(n*sqrt(n))；

代码如下，速度并不是很快（我比较喜欢手动的去重,unique一直没怎么用过）

/*96655 's source code for BMemory: 3744 KB        Time: 2968 MSLanguage: G++        Result: Accepted*/#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #include
               
                using namespace std;typedef long long LL;const int maxn=100005;map
                
                 mp;int a[maxn],pos[maxn],b[maxn];LL sum;struct node{ int l,r,id; LL ans;} res[maxn];bool cmp1(node a,node b){ if(pos[a.l]==pos[b.l])return a.r
                 
                  res[i].r; --r) change(r,-1); for(; l
                  
                   res[i].l; --l) change(l-1,1); res[i].ans=sum; } sort(res+1,res+q+1,cmp2); for(int i=1; i<=q; ++i) printf("%I64d\n",res[i].ans); } return 0;}

View Code

转载于:https://www.cnblogs.com/shuguangzw/p/5046787.html

你可能感兴趣的文章