BZOJ 2038 小Z的袜子(莫队算法)-白红宇

BZOJ 2038 小Z的袜子(莫队算法)

阅读量：5025 次

发布时间：2019-06-12

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

莫队算法

如果我们已知[l,r]的答案，能在O(1)时间得到[l+1,r]的答案以及[l,r-1]的答案，即可使用莫队算法。时间复杂度为O(n^1.5)。如果只能在logn的时间移动区间，则时间复杂度是O(n^1.5*log n)。

其实就是找一个数据结构支持插入、删除时维护当前答案。

这道题的话我们很容易用数组来实现，做到O(1)的从[l,r]转移到[l,r+1]与[l+1,r]。

那么莫队算法怎么做呢？以下都是在转移为O(1)的基础下讨论的时间复杂度。另外由于n与m同阶，就统一写n。

如果已知[l,r]的答案，要求[l’,r’]的答案，我们很容易通过|l – l’|+|r – r’|次转移内求得。

将n个数分成sqrt(n)块。

按区间排序，以左端点所在块内为第一关键字，右端点为第二关键字，进行排序，也就是以(pos [l]，r)排序

然后按这个排序直接暴力，复杂度分析是这样的：

1、i与i+1在同一块内，r单调递增，所以r是O(n)的。由于有n^0.5块,所以这一部分时间复杂度是n^1.5。

2、i与i+1跨越一块，r最多变化n，由于有n^0.5块，所以这一部分时间复杂度是n^1.5

3、i与i+1在同一块内时l变化不超过n^0.5，跨越一块也不会超过n^0.5，忽略*2。由于有m次询问（和n同级），所以时间复杂度是n^1.5

于是就是O(n^1.5)了

# 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=50005;//Code begin...struct Query{ int L, R, id;}node[N];LL gcd(LL a, LL b){ return b==0?a:gcd(b,a%b);}struct Ans{ LL a, b; void reduce(){LL d=gcd(a,b); a/=d; b/=d;}}ans[N];int a[N], num[N], n, m, unit;bool comp(Query a, Query b){ if (a.L/unit!=b.L/unit) return a.L/unit
                   
                    node[i].R) { temp-=(LL)num[a[R]]*num[a[R]]; --num[a[R]]; temp+=(LL)num[a[R]]*num[a[R]]; --R; } while (L
                    
                     node[i].L) { --L; temp-=(LL)num[a[L]]*num[a[L]]; ++num[a[L]]; temp+=(LL)num[a[L]]*num[a[L]]; } ans[node[i].id].a=temp-(R-L+1); ans[node[i].id].b=(LL)(R-L+1)*(R-L); ans[node[i].id].reduce(); }}int main (){ scanf("%d%d",&n,&m); FOR(i,1,n) scanf("%d",a+i); FO(i,0,m) scanf("%d%d",&node[i].L,&node[i].R), node[i].id=i; unit=(int)sqrt(n); sort(node,node+m,comp); work(); FO(i,0,m) printf("%lld/%lld\n",ans[i].a,ans[i].b); return 0;}

View Code

转载于:https://www.cnblogs.com/lishiyao/p/6639390.html

你可能感兴趣的文章