天天看點
傳回

莫隊算法——暴力出奇迹

簡介：

莫隊這個算法是莫濤提出的。 用于處理一類不帶修改的區間查詢問題的離線 算法，其核心在于利用曼哈頓距離最小生成樹 算法對區間處理順序進行處理 。

——zrt課件

這個算法本質上其實是暴力，但是由于可以離線處理循環的順序，使得複雜度可以從n^2降到n^根号n甚至更低。

對于可以找到以下特點的題可以嘗試使用莫隊：

1.莫隊算法是離線處理一類區間不修改查詢類問 題的算法。就是如果你知道了 [ L,R] 的答案。你 可以在 O(1 ) 或 O( lgn ) 的 時間下得到 [ L,R

1] 和 [ L,R+1] 和 [ L1,R] 和 [ L+1,R] 的答案的話。就可 以使用莫隊算法 。 

2.需要預知所有的詢問

例題一：

小Z的襪子

小Z把這N隻襪子從1到N編号，然後從編号L到R(L 盡管小Z并不在意兩隻襪子是不是完整的一雙，甚至不在意兩隻襪子是否一左一右，他卻很在意襪子的顔色，畢竟穿兩隻不同色的襪子會很尴尬。

你的任務便是告訴小Z，他有多大的機率抽到兩隻顔色相同的襪子。當然，小Z希望這個機率盡量高，是以他可能會詢問多個(L,R)以友善自己選擇。

分析：

通過組合數學推理可以得知：

對于 L,R 的詢問。設其中顔色為 x,y,z ... 的 襪子 的個數為 a,b,c ...

那麼答案即為 (a*(a-1)/2+b*(b-1)/2+c*(c-1)/2....)/((R-L+1)*(R-L)/2 )

化簡得 :(a^2+b^2+c^2+...x^2-( a+b+c+d +.....))/((R-L+1)*(R-L ))

即： (a^2+b^2+c^2+...x^2-(R-L+1))/((R-L+1)*(R-L))

是以我們需要維護的是，從L到R這個區間中的每個襪子的種類數的平方和。

我們在移動L、R的時候，增加一個，sum+=cnt[x]×2.減少一個，sum=sum-cnt[x]×2+2 (sum是分子的總值。）

發現我們需要不斷移動L、R，是以我們必須将所有的詢問進行恰當的排序，使得L、R的移動次數盡可能小，才能降低時間複雜度。

首先要分塊處理。

必須分塊，如果單純的通過l相等，按r排序的方法，可能會在l移動一個機關，r就要從另一邊傳回來，實際很慢。

之後我們這樣排序：

struct node{
    int l,r;
    int hao;
    bool friend operator <(node a,node b)
    {
        if(id[a.l]==id[b.l])
        {
         if(id[a.l]&&1==1) return a.r<b.r;
         else return a.r>b.r;
        }
        return id[a.l]<id[b.l];
    }
}q[N];

先按照左端點所在塊排序，再按照右端點排序。要注意的是：if(id[a.l]&&1==1) return a.r<b.r; else return a.r>b.r;

左端點所在塊是奇數的時候，升序排列，否則降序排列，這樣可以在L增加到下一個塊的時候，r移動次數盡量小，最好情況下每次可以省n次，l最多跳n/unit次，可以省去n×n/unit次，當然絕大多數情況遠沒有這麼好。

本題大概可以省去一共180ms

最後直接分子分母求gcd化簡即可。

注意long long

詳見代碼：

#include<bits/stdc++.h>
#define ll long long
#define num ch-'0'
using namespace std;
const int N=100000+10;
ll kua;
void read(int &x)
{
    x=0;char ch;
    while(!isdigit(ch=getchar()));
    for(x=num;isdigit(ch=getchar());x=x*10+num);
}
int n,m;
int id[N];
struct node{
    int l,r;
    int hao;
    bool friend operator <(node a,node b)
    {
        if(id[a.l]==id[b.l])
        {
         if(id[a.l]&&1==1) return a.r<b.r;
         else return a.r>b.r;
        }
        return id[a.l]<id[b.l];
    }
}q[N];
ll ans[N][2];
int a[N];
ll cnt[N];
ll sum;
int L,R;
ll gcd(ll x,ll y)
{
    return y==0?x:gcd(y,x%y);
}
int main()
{
    read(n),read(m);
    kua=sqrt(n);
    for(int i=1;i<=n;i++) read(a[i]),id[i]=(i-1)/kua+1;
    for(int i=1;i<=m;i++) read(q[i].l),read(q[i].r),q[i].hao=i;
    sort(q+1,q+m+1);
    for(int i=1;i<=m;i++)
    {
        //cout<<i<<" : "<<q[i].l<<" "<<q[i].r<<" "<<" from "<<q[i].hao<<endl;
        if(i==1){
            L=q[i].l,R=q[i].r;
            sum=0;
            for(int j=q[i].l;j<=q[i].r;j++)
            {
                cnt[a[j]]++;
            }
            for(int j=1;j<=n;j++)
             if(cnt[j]) sum+=cnt[j]*cnt[j];
            sum=sum-(ll)(q[i].r-q[i].l+1);
            ans[q[i].hao][0]=sum;
            ans[q[i].hao][1]=((ll)q[i].r-q[i].l+1)*((ll)q[i].r-q[i].l);
        }
        else{//duo 1 : sum+ 2*cnt[a[j]]
             //shao 1: sum- 2*cnt[a[j]]+2
            if(R<q[i].r)
            {
                while(R<q[i].r)
                {
                    R++;
                    sum=sum+2*cnt[a[R]];
                    cnt[a[R]]++;
                }
            }
            else if(R>q[i].r)
            {
                while(R>q[i].r)
                {
                    sum=sum-2*cnt[a[R]]+2;
                    cnt[a[R]]--;
                    R--;
                }
            }
            if(L<q[i].l)
            {
                while(L<q[i].l)
                {
                    sum=sum-2*cnt[a[L]]+2;
                    cnt[a[L]]--;
                    L++;
                }
            }
            else if(L>q[i].l)
            {
                while(L>q[i].l)
                {
                    L--;
                    sum=sum+2*cnt[a[L]];
                    cnt[a[L]]++;
                }
            }
            ans[q[i].hao][0]=sum;
            ans[q[i].hao][1]=((ll)q[i].r-q[i].l+1)*((ll)q[i].r-q[i].l);
        }
        //cout<<" after "<<sum<<endl;
    }
    for(int i=1;i<=m;i++)
    {
        ll t1=ans[i][0],t2=ans[i][1];
        if(t1==0) t2=1;
        else{

            ll g=gcd(max(t1,t2),min(t1,t2));
            t1/=g;
            t2/=g;
        }
        printf("%lld",t1);
        printf("/");
        printf("%lld\n",t2);
    }
    return 0;
}

但是莫隊還可以處理一個更進階的題目種類。

帶修改的題也可以考慮做！！

這樣一個struct需要維護L,R,T三個，T為該詢問是在第幾次操作之後詢問的。可以看做是一個time

例題二：

數顔色

分析詳見友鍊(推薦）：莫隊算法——大米餅

排序：

struct node{
    int l,r,t;
    int hao;
    bool friend operator <(node a,node b)
    {
        if(id[a.l]==id[b.l])
        {
            if(id[a.r]==id[b.r]) 
            {   
              if(id[a.r]&1) return a.t<b.t;
              return a.t>b.t;
            }
            return a.r<b.r;
        }
        return a.l<b.l;
    }
}q[N];

代碼：

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
#define num ch-'0'
using namespace std;
const int N=100000+10;
void read(int &x)
{
    x=0;char ch;
    while(!isdigit(ch=getchar()));
    for(x=num;isdigit(ch=getchar());x=x*10+num);
}
int sum;
int n,m;
int a[N],b[N];
int cnt[1000000+10];
int id[N],len;
int ans[N];
int tim[N][3];

struct node{
    int l,r,t;
    int hao;
    bool friend operator <(node a,node b)
    {
        if(id[a.l]==id[b.l])
        {
            if(id[a.r]==id[b.r]) 
            {   
              if(id[a.r]&1) return a.t<b.t;
              return a.t>b.t;
            }
            return a.r<b.r;
        }
        return a.l<b.l;
    }
}q[N];
inline void add(int x)
{
    cnt[a[x]]++;
    sum+=(cnt[a[x]]==1);
}
inline void del(int x)
{
    cnt[a[x]]--;
    sum-=(cnt[a[x]]==0);
}
inline void add2(int ti,int l,int r,int k)//1->2 jia k
{
    if(l<=tim[ti][0]&&tim[ti][0]<=r)
    {   
        cnt[tim[ti][k]]++;
        sum+=(cnt[tim[ti][k]]==1);
    }
    a[tim[ti][0]]=tim[ti][k];
}
inline void del2(int ti,int l,int r,int k)//2->1 shan k
{
    if(l<=tim[ti][0]&&tim[ti][0]<=r)
    {   
        cnt[tim[ti][k]]--;
        sum-=(cnt[tim[ti][k]]==0);
    }
}

char que;
int has;
int tot;
int main()
{
    read(n);read(m);
    len=pow(n,0.666666);
    for(int i=1;i<=n;i++) read(a[i]),b[i]=a[i],id[i]=(i-1)/len+1;
    int x,y;
    has=0;
    for(int i=1;i<=m;i++)
    {
        scanf("%c",&que);
        if(que=='Q')
        {
            tot++;
            read(x);read(y);
            q[tot].l=x,q[tot].r=y;
            q[tot].t=has;
            q[tot].hao=tot;
        }
        else{
            has++;
            read(x);read(y);
            tim[has][0]=x;tim[has][2]=y;
            tim[has][1]=b[x];
            b[x]=y;
        }
    }
    sort(q+1,q+tot+1);
    int L,R,T=0;
    for(int i=1;i<=tot;i++)
    {
        if(i==1)
        {
            L=q[i].l,R=q[i].r;
            for(int j=q[i].l;j<=q[i].r;j++)
            {
                cnt[a[j]]++;
                sum+=(cnt[a[j]]==1);
            }
            while(T<q[i].t) ++T,del2(T,L,R,1),add2(T,L,R,2);
            ans[q[i].hao]=sum;
        }
        else{
            while(T<q[i].t) ++T,del2(T,L,R,1),add2(T,L,R,2);
            while(T>q[i].t) del2(T,L,R,2),add2(T,L,R,1),T--;
            while(L<q[i].l) del(L++);
            while(L>q[i].l) add(--L);
            while(R<q[i].r) add(++R);
            while(R>q[i].r) del(R--);
            ans[q[i].hao]=sum;
        }
    }

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

莫隊算法——暴力出奇迹。

在做題實在沒有思路的時候，不要忘了莫隊。

upda：2019.3.24:

更新：

1.[學習筆記]樹上莫隊

2.還有復原莫隊：說白了就是棧序撤銷

這樣友善維護最大值莫隊算法——從入門到黑題 - WAMonster - 部落格園

莫隊算法——暴力出奇迹

 3.一般序列莫隊，block=n/sqrt(m)最優

mblock+(n/block)*n最小

均值不等式

4.帶修莫隊最好這樣排：

l，r都分塊

l塊相同，r塊相同，t按照(l塊+r塊)的奇偶性升序降序排

如果r塊不同，按照l塊的奇偶性升序降序排

大概長這樣：

莫隊算法——暴力出奇迹
莫隊 模拟 算法 i++ #include
上一篇: 極簡 Node.js 入門 - 4.2 初識 stream
下一篇: HDU 5799 This world need more Zhu (樹上莫隊)

繼續閱讀