分塊（一）

2022 年 11 月 10 日
筆記

分塊（一）

優雅的暴力~~

一、一些題目

基本思想：

將原序列劃分成 \(\sqrt n\) 個塊，記錄每一個元素對應其所在塊的編號，統計每個塊的信息。

（至於為什麼是 \(\sqrt n\)，下面會講到~~）

這裡，我們用 \(id\) 表示每個元素對應塊的編號，每一塊的長度為 \(len\)，具體如下：

當 \(i\in[1,len]\) 時，\(id[i]=1\)；

當 \(i\in[len+1,2\times len]\) 時，\(id[i]=2\)；

……

當 \(i\in[(len-1)\times len+1,n]\) 時，\(id[i]=n/len+1\)。

scanf("%d",&n);
len=sqrt(n);
for(int i=1;i<=n;i++)
{
    scanf("%d",&a[i]);
    id[i]=(i-1)/len+1; 
}

Tips: 關於 \(id[i]\) 的計算

i-1 是為了保證第一個塊有 \(len\) 個元素，而不是 \(len-1\) 個；
+1 是為了讓第一個塊的編號為 \(1\)，而不是 \(0\)。

對於每一個區間操作，分為如下兩種情況：

左右端點在同一個塊中，枚舉整個區間暴力求解
左右端點在不同的塊中：

① 對於能完全包含在內的塊，我們稱為完整塊，直接利用這個塊預處理的信息，\(O(1)\) 得到答案；

② 對於區間兩端不能涵蓋的整塊，我們稱為不完整塊，暴力枚舉求解即可。

兩個操作的時間複雜度最優為 \(O(\sqrt n)\)。

有一張圖，或許能幫助你理解：

關於 \(\sqrt n\) 的小證明：

需要一點高中數學知識：~~（真的只有一點，不是億點）~~

基本不等式：\(\cfrac {a+b} 2 \geq \sqrt {ab}\)，當且僅當 \(a=b\) 時，等號成立。

左右端點在同一個塊中，暴力枚舉整個塊，複雜度最壞為 \(O(len)\)；
左右端點不在同一個塊中，答案由三部分組成：以 \(l\) 開偷的不完整塊、中間幾個完整塊、以 \(r\) 結尾的不完整塊。

① 對於完整塊，時間複雜度為 \(O(\cfrac n {len})\)；

② 對於不完整塊，時間複雜度為 \(O(len)\)

故最壞複雜度的和為 \(O(\cfrac n {len} + len)\)，由基本不等式可得：

\(\cfrac n {len} + len \geq 2\sqrt{\cfrac n {len} \times len} = 2 \sqrt n\)，當且僅當 \(\cfrac n {len} = len\)，即 \(len=\sqrt n\) 時，等號成立。

也就是單次操作的時間複雜最優，為 \(O(\sqrt n)\)，此時塊長也為 \(\sqrt n\)。

既然基本思想已經知道了，那就來 「億」點點 例題實踐一下吧：

Example1: 數列分塊入門1 LibreOJ #6277

給出一個長為 \(n\) 的數列，以及 \(n\) 個操作，操作涉及區間加法，單點查值。

區間增加

我們可以對於每一個塊，按照分塊的基本思想進行累加即可：

對於 完整塊，利用數組 \(b\) 存儲對於塊整體加的值，不必對於每一個 \(a[i]\) 做加法；
對於 不完整塊 或 左右端點在同一個塊中，暴力枚舉，對 \(a[i]\) 做加法即可。

void add(int l,int r,int v)
{
    int lid=id[l],rid=id[r]; // 左右兩端點對於塊的編號
    if(lid==rid) // 左右端點在同一個塊中
    {
        for(int i=l;i<=r;i++) // 暴力加
            a[i]+=v;
        return;
    }
    for(int i=l;id[i]==lid;i++) // 以l開頭的不完整塊，暴力加
        a[i]+=v;
    for(int i=lid+1;i<rid;i++) // 完整塊，直接改變b的值
        b[i]+=v;
    for(int i=r;id[i]==rid;i--) // 以r結尾的不完整塊，暴力加
        a[i]+=v;
}

Tips:

對於完整塊的操作，for 中的 \(i\) 表示塊的編號，而不是元素的編號；
若 \(a\) 的下標為 \(i\)，則 \(b\) 的下標為 \(id[i]\)。

單點查詢

直接輸出本身的值 \(a[i]\) 與該元素所在塊的 \(b[id[i]]\)。

int ask(int l,int r)
{
	return a[r]+b[id[r]];
}

Example2: 數列分塊入門2 LibreOJ #6278

給出一個長為 \(n\) 的數列，以及 \(n\) 個操作，操作涉及區間加法，詢問區間內小於某個值 \(x\) 的元素個數。

相較於上一題，多了區間查詢。

區間查詢

看到 小於 \(x\) 的個數，直接想到二分

這道題中，我們可以 用 vector 存儲每一個塊所有元素的值，方便進行二分查找。

對於 完整塊，二分對應塊的全部元素，統計個數；
對於 不完整塊 或 左右端點在同一個塊中，暴力枚舉，統計 \(a[i]<v\) 的個數。

int clac(int x,int v) // 手寫二分需要此函數
{
    int l=0,r=vec[x].size();
    while(l+1<r)
    {
        int mid=l+r>>1;
        if(vec[x][mid]+b[x]<v) l=mid; // 別忘記加b數組的值
        else r=mid;
    }
    if(vec[x][l]+b[x]<v) return l+1; //vector從0開始存儲，數組從1開始存儲，+1保證下標對應
    else if(vec[x][r]+b[x]<v) return r+1;
    else return 0;  
}

int ask(int l,int r,int v)
{
    int lid=id[l],rid=id[r],res=0;
    if(lid==rid)
    {
        for(int i=l;i<=r;i++)
            if(a[i]+b[id[i]]<v) res++;
        return res;
    }
    for(int i=l;id[i]==lid;i++)
        if(a[i]+b[id[i]]<v) res++;
    for(int i=lid+1;i<rid;i++)
        res+=clac(i,v); // 手寫二分，下面為STL
//      res+=lower_bound(vec[i].begin(),vec[i].end(),v-b[i])-vec[i].begin();
    for(int i=r;id[i]==rid;i--)
        if(a[i]+b[id[i]]<v) res++;
    return res;
}

區間增加

由於塊用 vector 存了起來，所以每一次按照正常單點增加的造作之後，更新一下對應 vector。

void change(int x)
{
    vec[x].clear();
    int l=(x-1)*len+1,r=min(x*len,n);
    for(int i=l;i<=r;i++)
        vec[x].push_back(a[i]);
    sort(vec[x].begin(),vec[x].end());
}

void add(int l,int r,int v)
{
    int lid=id[l],rid=id[r];
    if(lid==rid)
    {
        for(int i=l;i<=r;i++)
        a[i]+=v;
        change(lid); 
        return;
    }
    
    for(int i=l;id[i]==lid;i++)
    a[i]+=v;
    change(lid);
    
    for(int i=lid+1;i<rid;i++)
        b[i]+=v;
    
    for(int i=r;id[i]==rid;i--)
        a[i]+=v;
    change(rid);
}

初始化

其實也沒有什麼變化，多存一個 vector 即可。

scanf("%d",&n);
len=sqrt(n);
for(int i=1;i<=n;i++)
{
    scanf("%d",&a[i]);
    id[i]=(i-1)/len+1;
    vec[id[i]].push_back(a[i]);
}

Example3: 數列分塊入門3 LibreOJ #6279

給出一個長為 \(n\) 的數列，以及 \(n\) 個操作，操作涉及區間加法，詢問區間內小於某個值 \(x\) 的前驅（比其小的最大元素）。

區間增加和上題一樣，區間查詢的時候，將二分答案的返回值更改為當前元素的值即可。

int get(int x,int v)
{
    int l=0,r=vec[x].size();
    while(l+1<r)
    {
        int mid=l+r>>1;
        if(vec[x][mid]+b[x]<v) l=mid;
        else r=mid;
    }
    if(vec[x][l]+b[x]<v) return vec[x][l]+b[x];
    else if(vec[x][r]+b[x]<v) return vec[x][r]+b[x];
    else return -1; // 當前塊中沒有<v的數，返回-1
}

int ask(int l,int r,int v)
{
    int lid=id[l],rid=id[r],ans=-1;
    if(lid==rid)
    {
        for(int i=l;i<=r;i++)
            if(a[i]+b[lid]<v) ans=max(ans,a[i]+b[lid]);
        return ans;
    } 
    for(int i=l;id[i]==lid;i++)
        if(a[i]+b[lid]<v) ans=max(ans,a[i]+b[lid]);
    for(int i=lid+1;i<rid;i++)
        ans=max(ans,get(i,v));
    for(int i=r;id[i]==rid;i--)
        if(a[i]+b[rid]<v) ans=max(ans,a[i]+b[rid]);
    return ans; 
}

Example4: 數列分塊入門4 LibreOJ #6280

給出一個長為 \(n\) 的數列，以及 \(n\) 個操作，操作涉及區間加法，區間求和。

在這道題中，我們再引用一個 數組 \(s\) ，\(s[i]\) 表示第 \(i\) 個塊的數值和。

因此在預處理的時候，需要更新一下數組 \(s\)：

scanf("%d",&n);
len=sqrt(n);
for(int i=1;i<=n;i++)
{
    scanf("%d",&a[i]);
    id[i]=(i-1)/len+1;
    s[id[i]]+=a[i];
}

區間增加

注意在增加的時候及時更改數組 \(s\) 的值。

void add(int l,int r,int v)
{
    int lid=id[l],rid=id[r];
    if(lid==rid)
    {
        for(int i=l;i<=r;i++)
        a[i]+=v,s[lid]+=v;
        return;
    } 
    for(int i=l;id[i]==lid;i++)
    a[i]+=v,s[lid]+=v;
    for(int i=lid+1;i<rid;i++)
        b[i]+=v,s[i]+=(LL)v*len; // 一個塊有len個元素，每個元素增加v。共增加v*len
    for(int i=r;id[i]==rid;i--)
        a[i]+=v,s[rid]+=v;
}

區間求和

對於 完整塊，直接返回數組 \(s\) 的值即可；
對於 不完整塊 或 左右端點在同一個塊中，暴力枚舉每一個點，累加每一個點的值。

LL ask(int l,int r,int p)
{
    LL res=0;
    int lid=id[l],rid=id[r];
    if(lid==rid)
    {
        for(int i=l;i<=r;i++)
            res=(LL)(res+a[i]+b[lid])%p;
        return res;
    }
    for(int i=l;id[i]==lid;i++)
        res=(LL)(res+a[i]+b[lid])%p;
    for(int i=lid+1;i<rid;i++)
        res=(LL)(res+s[i])%p;
    for(int i=r;id[i]==rid;i--)
        res=(LL)(res+a[i]+b[rid])%p;
    return res;
}

Example5: 數列分塊入門5 LibreOJ #6281

給出一個長為 \(n\) 的數列 \(a_1 ,\ldots, a_n\)，以及 \(n\) 個操作，操作涉及區間開方，區間求和。

區間開方

我們知道，開方操作能使數值快速減小。

故可以引用 數組 \(tag\) 用來標記每一個塊的所有元素是否全部變為 \(1\)，

如果全都變為 \(1\) 了，之後再進行開方操作就可以跳過，優化時間複雜度。

由於本題仍需區間求和，開方的時候不方便直接更改數組 \(s\) 的值，

因此我們可以在更改 \(a[i]\) 的時候，先減去 \(a[i]\)，再將開方過後的值加到數組\(s\) 中。

void change(int l,int r)
{
    int lid=id[l],rid=id[r];
    if(lid==rid)
    {
        for(int i=l;i<=r;i++)
        {
            if(tag[lid]) break; // 該塊全部為1.開方操作沒有任何作用，直接跳過
            s[lid]-=a[i]; // 先減去原本元素的值
            a[i]=sqrt(a[i]);
            s[lid]+=a[i]; // 加上開方之後該元素的值
        }
        return;
    }
    for(int i=l;id[i]==lid;i++)
    {
        if(tag[lid]) break;
        s[lid]-=a[i];
        a[i]=sqrt(a[i]);
        s[lid]+=a[i];
    }
    for(int i=lid+1;i<rid;i++)
    {
        if(tag[i]) continue; // 注意這裡不能break！！！
        tag[i]=true; s[i]=0;
        for(int j=(i-1)*len+1;j<=min(i*len,n);j++)
        {
            a[j]=sqrt(a[j]);
            s[i]+=a[j];
            if(a[j]>1) tag[i]=false; // 有一個元素>1，就為false；只有全部為1的時候，才是true
        }
    }
    for(int i=r;id[i]==rid;i--)
    {
        if(tag[rid]) break;
        s[rid]-=a[i];
        a[i]=sqrt(a[i]);
        s[rid]+=a[i];
    }
}

區間求和

由於沒有增加操作，也就不必統計數組 \(b\)。

int ask(int l,int r)
{
    int lid=id[l],rid=id[r],res=0;
    if(lid==rid)
    {
        for(int i=l;i<=r;i++)
            res+=a[i];
        return res;
    }
    for(int i=l;id[i]==lid;i++)
        res+=a[i];
    for(int i=lid+1;i<rid;i++)
        res+=s[i];
    for(int i=r;id[i]==rid;i--)
        res+=a[i];
    return res; 
}

Example6: 數列分塊入門6 LibreOJ #6282

給出一個長為 \(n\) 的數列，以及 \(n\) 個操作，操作涉及單點插入，單點詢問，數據隨機生成。

單點插入

對於單點插入，顯然之前用的分塊方法不太可行了。

這時，我們可以利用 vector 可以插入元素的特性，將每一個塊都存到一個堆中。

對於每一個插入操作，找到插入位置對應的塊以及在塊中的位置即可。

typedef pair<int,int> PII;

PII get(int x) // 找到插入位置對應的塊以及位置
{
    int cnt=0,i; // cnt表示前面的塊共有多少個元素，i表示此時在第幾個塊
    for(i=1;cnt+vec[i].size()<x;i++) // 只要這個塊仍然到達不了位置x
        cnt+=vec[i].size(); // 加上這個塊的長度
    return {i,x-cnt}; // x-cnt就是位置x，是第i個塊的第幾個元素
}

void add(int x,int v)
{
    PII t=get(x);
    vec[t.first].insert(vec[t.first].begin()+t.second-1,v); 
    // 由於要在x前面增加新元素v，故要-1
}

單點查詢

有了插入的基礎，查詢就非常容易了。

還是利用 \(get\) 函數找到對應的塊以及在塊中的位置即可。

int ask(int x)
{
    PII t=get(x);
    return vec[t.first][t.second-1];
}

初始化

由於塊都存到了 vector 中，就不需要數組 \(id\) 記錄每一個元素對應塊的編號了。

scanf("%d",&n);
len=sqrt(n);
for(int i=1;i<=n;i++)
{
    int x,y;
    scanf("%d",&x);
    y=(i-1)/len+1;
    vec[y].push_back(x);
}

Example7: 數列分塊入門7 LibreOJ #6283

給出一個長為 n 的數列，以及 n 個操作，操作涉及區間乘法，區間加法，單點詢問。

利用 線段樹延遲標記 的思想~~（既然都學分塊了，就一定會線段樹吧(～￣▽￣)～）~~

用 \(add\_tag[i]\) 表示第 \(i\) 個塊整體增加的值，\(mul\_tag[i]\) 表示第 \(i\) 個塊整體乘的值

每次對 不完整塊 進行處理時，將標記下傳給元素本身，在進行操作即可。

由於加法和乘法混合進行，為了保證下傳標記次數不變，

我們可以讓每一次進行乘法操作時，同時將 \(add\_tag\) 的值也進行乘法運算。

void spread(int x)
{
    int l=(x-1)*len+1,r=min(x*len,n);
    for(int i=l;i<=r;i++)
        a[i]=Add(Pow(a[i],mul_tag[x]),add_tag[x]);
        // 每次乘法進行處理之後，返回給元素的值就要先乘後加了，因為加的值以及乘過了
    
    // 下傳操作完成之後，清空所有標記數組
    add_tag[x]=0; // 加法初值為0
    mul_tag[x]=1; // 乘法初值為1
}

Tips: Add 與 Pow 函數：在函數中進行 \(\bmod\) 運算，防止代碼中部分運算忘記 \(\bmod\)，導致最終結果錯誤。

inline int Add(int a,int b)
{
    return a+b>=Mod?a+b-Mod:a+b;
}

inline int Pow(int a,int b)
{
    return (LL)a*b%Mod;
}

區間加法

void add(int l,int r,int v)
{
    int lid=id[l],rid=id[r];
    if(lid==rid)
    {
        spread(lid);
        for(int i=l;i<=r;i++)
            a[i]=Add(a[i],v);
        return; 
    }
    
    spread(lid);
    for(int i=l;id[i]==lid;i++)
        a[i]=Add(a[i],v);
    
    for(int i=lid+1;i<rid;i++)
        add_tag[i]=Add(add_tag[i],v);
    
    spread(rid);
    for(int i=r;id[i]==rid;i--)
        a[i]=Add(a[i],v);
}

區間乘法

void mul(int l,int r,int v)
{
    int lid=id[l],rid=id[r];
    if(lid==rid)
    {
        spread(lid);
        for(int i=l;i<=r;i++)
            a[i]=Pow(a[i],v);
        return; 
    }
    
    spread(lid);
    for(int i=l;id[i]==lid;i++)
        a[i]=Pow(a[i],v);
    
    for(int i=lid+1;i<rid;i++)
    {
        mul_tag[i]=Pow(mul_tag[i],v);
        add_tag[i]=Pow(add_tag[i],v); // 不要忘了同時更新add_tag的值
    }
    
    spread(rid);
    for(int i=r;id[i]==rid;i--)
        a[i]=Pow(a[i],v);
}

單點查詢

要先下傳標記哦，否則結果會錯誤。

int ask(int x)
{
    spread(id[x]);
    return a[x]; 
}

Tips: 別忘了把 \(mul\_tag\) 的值都設為 \(1\)。

for(int i=1;i<=id[n];i++) // 用id[n]，而不是len，有可能有1的誤差
    mul_tag[i]=1;

Example8: 數列分塊入門8 LibreOJ #6284

給出一個長為 \(n\) 的數列，以及 \(n\) 個操作，

操作涉及區間詢問等於一個數 \(c\) 的元素，並將這個區間的所有元素改為 \(c\)。

如果一個塊中所有的元素都為同一個值，就不必再遍歷每一個數了。

利用上述思想進行優化分塊即可。

用 \(tag[i]\) 表示第 \(i\) 個塊元素的值是否都一樣，\(b[i]\) 表示第 \(i\) 塊集體更改的值。

void spread(int x)
{
    if(tag[x]) // 如果這個塊元素的值都一樣，將每個元素的值更新一下
    {
        int l=(x-1)*len+1,r=min(x*len,n);
        for(int i=l;i<=r;i++)
            a[i]=b[x];
    }
}

int solve(int l,int r,int v)
{
    int lid=id[l],rid=id[r],cnt=0;
    if(lid==rid)
    {
        spread(lid); // 下傳這個塊的值
        for(int i=l;i<=r;i++)
        {
            if(a[i]==v) cnt++; // 如果值為v，統計個數+1
            else a[i]=v; // 否則將這個元素的值改為v
        }
        tag[lid]=false; // 這個塊的元素值不同了，因為只有一部分元素的值進行多了更改
        return cnt;
    }
    
    spread(lid);
    for(int i=l;id[i]==lid;i++)
    {
        if(a[i]==v) cnt++;
        else a[i]=v;
    }
    tag[lid]=false;
    
    for(int i=lid+1;i<rid;i++)
    {
        if(tag[i]) // 如果這個塊的元素值相同
        {
            if(b[i]==v) cnt+=sze[i]; // 如果這個塊的值為v，答案加上這個塊的長度
                else b[i]=v; // 否則這個塊的值改為v
        }
        else // 元素值不同只能進行暴力更改
        {
            int ll=(i-1)*len+1,rr=min(i*len,n);
            for(int j=ll;j<=rr;j++)
                if(a[j]==v) cnt++;
            // 查詢之後這個塊的值就統一更改為v了，更新標記
            tag[i]=true; 
            b[i]=v;
        }
    }
    
    spread(rid);
    for(int i=r;id[i]==rid;i--)
    {
        if(a[i]==v) cnt++;
        else a[i]=v;
    }
    tag[rid]=false;
    
    return cnt;
}

Tips: 用數組 \(sze\) 表示每一個塊的長度，調用更方便。

for(int i=1;i<=id[n];i++)
{
    int l=(i-1)*len+1,r=min(i*len,n);
    sze[i]=r-l+1; // 由於最後一個塊不一定為整塊，故不能直接等於塊長len
}

Example9: 數列分塊入門9 LibreOJ #6285

給出一個長為 \(n\) 的數列，以及 \(n\) 個操作，操作涉及詢問區間的最小眾數。

最後一道例題了，開心嗎(oﾟvﾟ)ノ~~（這是最難的一道例題了）~~

由於不會進行更改元素的值，我們可以預處理出每一塊的區間眾數，與分塊思想照應。

這裡我們用 pair<int,int> 來存儲數組 \(f\)。

\(f[i][j].first\) 表示 \(i\sim j\) 的塊中，出現次數最多的的值，次數為多少。

\(f[i][j].second\) 表示 \(i\sim j\) 的塊中，出現次數最多的值，最小為多少。（因為詢問最小眾數）

for(int i=1;i<=id[n];i++)
{
    int max_cnt=0,min_val=0,cnt[N];
    memset(cnt,0,sizeof cnt); // 記得清空cnt

    int l=(i-1)*len+1;
    for(int j=l;j<=n;j++) // 要一直枚舉到n哦~
    {
        cnt[a[j]]++;
        if(max_cnt<cnt[a[j]] || (max_cnt==cnt[a[j]]&&min_val>a[j]))
        // 找到出現次數最多的，值最小的那個數
            max_cnt=cnt[a[j]],min_val=a[j];
        f[i][id[j]]={max_cnt,min_val};
    } 
}

因為本題元素值較大，不能作為數組下標，需要離散化。

scanf("%d",&n);
len=80; // len=sqrt(n) 會超時，不清楚為什麼 ＞︿＜
for(int i=1;i<=n;i++)
{
    scanf("%d",&a[i]);
    id[i]=(i-1)/len+1;
    c[i]=a[i]; // 用c[i]進行離散化
}

// STL離散化
sort(c+1,c+1+n);
int cn=unique(c+1,c+1+n)-(c+1);

for(int i=1;i<=n;i++)
{
    int t=lower_bound(c+1,c+1+cn,a[i])-(c+1);
    // 在c中找到第一個大於等於a[i]的位置
    // 由於c中元素值和a中是相同的，也就是找到離散化之後a[i]的位置
    b[t]=a[i]; // b[a[i]]的值為沒有離散化時a[i]的值
    a[i]=t; // 離散化之後第i個數的位置，也就是離散化之後的值
    vec[a[i]].push_back(i); // 用vec存值為a[i]元素的位置
}

之後進行分塊處理就行了。

int solve(int l,int r)
{
    int lid=id[l],rid=id[r];
    // 直接統計整塊的信息
    int max_cnt=f[lid+1][rid-1].first;
    int min_val=f[lid+1][rid-1].second;
    
    if(lid==rid)
    {
        for(int i=l;i<=r;i++)
        {
            auto& t=vec[a[i]];
            int cnt=upper_bound(t.begin(),t.end(),r)-lower_bound(t.begin(),t.end(),l);
            // 找到>r的位置和>=l的位置，兩者相減就是l~r中值為a[i]的個數
            if(max_cnt<cnt || (max_cnt==cnt&&min_val>a[i]))
                max_cnt=cnt,min_val=a[i];
        }
        return min_val;
    }
    
    for(int i=l;id[i]==lid;i++)
    {
        auto& t=vec[a[i]];
        int cnt=upper_bound(t.begin(),t.end(),r)-lower_bound(t.begin(),t.end(),l);
        if(max_cnt<cnt || (max_cnt==cnt&&min_val>a[i]))
            max_cnt=cnt,min_val=a[i];
    }
    
    for(int i=r;id[i]==rid;i--)
    {
        auto& t=vec[a[i]];
        int cnt=upper_bound(t.begin(),t.end(),r)-lower_bound(t.begin(),t.end(),l);
        if(max_cnt<cnt || (max_cnt==cnt&&min_val>a[i]))
            max_cnt=cnt,min_val=a[i];
    }
    
    return min_val;
}

在最後輸出的時候，應輸出原數值，而不是離散化之後的。

for(int i=1;i<=n;i++)
{
    int l,r;
    scanf("%d%d",&l,&r);
    printf("%d\n",b[solve(l,r)]);
}

Exercise1: 蒲公英 Luogu P4168 [Violet]

在鄉下的小路旁種着許多蒲公英，而我們的問題正是與這些蒲公英有關。

為了簡化起見，我們把所有的蒲公英看成一個長度為 \(n\) 的序列 \(\{a_1,a_2..a_n\}\)，

其中 \(a_i\) 為一個正整數，表示第 \(i\) 棵蒲公英的種類編號。

而每次詢問一個區間 \([l, r]\)，你需要回答區間里出現次數最多的是哪種蒲公英，

如果有若干種蒲公英出現次數相同，則輸出種類編號最小的那個。

注意，你的算法必須是在線的。

簡化題意：和 Example9 一模一樣。

在輸出的時候根據輸出要求進行在線操作即可。

int x=0;
for(int i=1;i<=m;i++)
{
    int l,r;
    scanf("%d%d",&l,&r);
    l=(l+x-1)%n+1,r=(r+x-1)%n+1;
    if(l>r) swap(l,r);
    int ans=solve(l,r);
    printf("%d\n",b[ans]);
    x=b[ans];
}

Exercise2: 作詩 Luogu P4315

SHY 找來一篇長度為 \(n\) 的文章，閱讀 \(m\) 次，

每次只閱讀其中連續的一段 \([l,r]\)，從這一段中選出一些漢字構成詩。

因為 SHY 喜歡對偶，所以 SHY 規定最後選出的每個漢字都必須在 \([l,r]\) 里出現了正偶數次。

而且 SHY 認為選出的漢字的種類數越多越好。

問題簡述：

給定 \(n\) 個不大於 \(c\) 的正整數 \(a_1 \dots a_n\) 和 \(m\) 組詢問，每次問 \([l,r]\) 中有多少個數出現正偶數次。

不難發現，和上題的題型非常相似，因此只是統計內容變了。

因此我們根據題意，更改一下 \(f\) 數組的含義即可。

\(sum[i][j]\) 表示前 \(i\) 個塊中漢字為 \(j\) 的個數。

\(cnt[i][j]\) 表示 \(i\sim j\) 的塊中，根據題意的結果為多少。

for(int i=2;i<=id[n];i++)
    for(int j=1;j<=c;j++)
        sum[i][j]+=sum[i-1][j];

for(int i=1;i<=id[n];i++)
{
    int res=0,l=(i-1)*len+1;
    for(int j=l;j<=n;j++)
    {
        cnt[a[j]]++;
        if(cnt[a[j]]%2==0 && cnt[a[j]]) res++; // 為偶數，數量+1
        else if(cnt[a[j]]>2) res--; // 由偶數又變成了奇數，數量-1
        f[i][id[j]]=res;
    }
    
    // 清空cnt數組
    for(int j=l;j<=n;j++)
        cnt[a[j]]--;
}

之後和上題一樣按照分塊的思想進行處理即可。

int solve(int l,int r)
{
    int lid=id[l],rid=id[r];
    int res=f[lid+1][rid-1];
    
    if(lid==rid)
    {
        for(int i=l;i<=r;i++)
        {
            cnt[a[i]]++;
            if(cnt[a[i]]%2==0 && cnt[a[i]]) res++;
            else if(cnt[a[i]]>2) res--; 
        }
        
        for(int i=l;i<=r;i++)
            cnt[a[i]]--;
        return res;
    } 
    
    for(int i=l;id[i]==lid;i++)
    {
        cnt[a[i]]++;
        int t=cnt[a[i]]+sum[rid-1][a[i]]-sum[lid][a[i]];
        // 記得加上 lid+1~rid-1 之間的塊中相同漢字的數量
        // 為了後續清空數組耗時短，不再累加到cnt數組中
        if(t%2==0 && t) res++;
        else if(t>2) res--;
    }
    
    for(int i=r;id[i]==rid;i--)
    {
        cnt[a[i]]++;
        int t=cnt[a[i]]+sum[rid-1][a[i]]-sum[lid][a[i]];
        if(t%2==0 && t) res++;
        else if(t>2) res--;
    }
    
    for(int i=l;id[i]==lid;i++)
        cnt[a[i]]--;
    for(int i=r;id[i]==rid;i--)
        cnt[a[i]]--;
    return res;
}

二、一些想法

分塊的各種操作不像樹狀數組或者線段樹那樣，基本操作的寫法不變

它會根據查詢內容的不同寫法發生很大變化，同時 vector 似乎發揮了很大作用
還有一些題，先不寫了，這些基本的板子題先寫出來，然後去寫莫隊啦༼ つ ◕_◕ ༽つ

其他題有時間了再寫，到時候再寫下一個分塊的博客吧
這篇博客只寫了半天，和上篇單調隊列相比，時間少了好多

可能是這篇是題都寫完了才寫的博客，上一個是一邊學一邊寫

也可能是越寫越快吧(o゜▽゜)o☆

分塊（一）

分塊（一）

一、一些題目

基本思想：

關於 \(\sqrt n\) 的小證明：

Example1: 數列分塊入門1 LibreOJ #6277

Example2: 數列分塊入門2 LibreOJ #6278

Example3: 數列分塊入門3 LibreOJ #6279

Example4: 數列分塊入門4 LibreOJ #6280

Example5: 數列分塊入門5 LibreOJ #6281

Example6: 數列分塊入門6 LibreOJ #6282

Example7: 數列分塊入門7 LibreOJ #6283

Example8: 數列分塊入門8 LibreOJ #6284

Example9: 數列分塊入門9 LibreOJ #6285

Exercise1: 蒲公英 Luogu P4168 [Violet]

Exercise2: 作詩 Luogu P4315

二、一些想法

VirMach 便宜 VPS

QNews

分塊（一）

分塊（一）

一、一些題目

基本思想：

關於 \(\sqrt n\) 的小證明：

Example1: 數列分塊入門1 LibreOJ #6277

Example2: 數列分塊入門2 LibreOJ #6278

Example3: 數列分塊入門3 LibreOJ #6279

Example4: 數列分塊入門4 LibreOJ #6280

Example5: 數列分塊入門5 LibreOJ #6281

Example6: 數列分塊入門6 LibreOJ #6282

Example7: 數列分塊入門7 LibreOJ #6283

Example8: 數列分塊入門8 LibreOJ #6284

Example9: 數列分塊入門9 LibreOJ #6285

Exercise1: 蒲公英 Luogu P4168 [Violet]

Exercise2: 作詩 Luogu P4315

二、一些想法

分享此文：

Related Posts

Debian 11 「bullseye」 安裝筆記

k8s設置pod運行完自動刪除

詞向量word2vec（圖學習參考資料）

又拍雲之 Keepalived 高可用部署

VirMach 便宜 VPS

QNews

熱門搜尋

Debian 11 「bullseye」安裝筆記