何為分塊

優雅的暴力

思維難度低下，代碼難度低下，非常優秀的一種算法（？）。
實現方法主要是塊與塊之間 \(O(1)*\sqrt{n}\) 查詢，邊角 \(O(\sqrt{n})\) 暴力查詢。
總復雜度 \(O(\sqrt{n})\)。

代碼實現

首先需要塊的大小 \(block\) ，和每個下標歸屬于哪個塊 \(belong[i]\) 。
如果需要塊內有序，可以使用 \(std::vector\) 。

區間修改對于整塊使用lazy標記的思想，邊邊角角還是\(O(\sqrt{n})\)暴力。

查詢同理。

例題（一）：教主的魔法

可以說，這是分塊最最經典的一道題了。
因為似乎沒有其他做法？

鏈接：教主的魔法

分好塊，用 \(std::vector<int> vc[maxn]\) 維護區間的高矮關系。
用 \(std::lower_bound\) 進行查詢。

修改就打標記。

#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>

const int maxn=1e6+5;

class Divid_Block {

    private:

        int n,q,delta[maxn],a[maxn];
        int block,belong[maxn],num;
        std::vector<int> vc[maxn];

        void update(int x) {
            vc[x].clear();
            for(int i=(x-1)*block+1;i<=x*block;i++)
                vc[x].push_back(a[i]);
            std::sort(vc[x].begin(),vc[x].end());
        }

        void modify(int l,int r,int c) {
            for(int i=l;i<=std::min(r,belong[l]*block);i++)
                a[i]+=c;
            update(belong[l]);
            if(belong[l]!=belong[r]) {
                for(int i=(belong[r]-1)*block+1;i<=r;i++)
                    a[i]+=c;
                update(belong[r]);	
            }
            for(int i=belong[l]+1;i<belong[r];i++)
                delta[i]+=c;
        }

        int query(int l,int r,int c) {
            int ans=0;
            for(int i=l;i<=std::min(r,belong[l]*block);i++)
                if(a[i]+delta[belong[l]]>=c) ++ans;
            if(belong[l]!=belong[r])
                for(int i=(belong[r]-1)*block+1;i<=r;i++)
                    if(a[i]+delta[belong[r]]>=c) ++ans;
            for(int i=belong[l]+1;i<belong[r];i++)
                ans+=block-(std::lower_bound(vc[i].begin(),vc[i].end(),c-delta[i])-vc[i].begin());
            return ans;
        }

    public:

        int work() {
            scanf("%d%d",&n,&q);
            block=sqrt((n+2)/3);
            for(int i=1;i<=n;i++) {
                scanf("%d",a+i);
                belong[i]=(i-1)/block+1;
                vc[belong[i]].push_back(a[i]);
                if(i%block==1) ++num;
            }
            for(int i=1;i<=num;i++) std::sort(vc[i].begin(),vc[i].end());
            while(q--) {
                char opt=getchar();
                while(opt!='A' && opt!='M') opt=getchar();
                int lf,rg,c;scanf("%d%d%d",&lf,&rg,&c);
                if(opt=='A') printf("%d\n",query(lf,rg,c));
                else modify(lf,rg,c);
            }
            return 0;
        }
}T;

int main() {return T.work();}

例題（二）：彈飛綿羊

其實，只要你沒學過CT，這道題還是很有希望做出來的。
記錄兩個信息：
\(tim[i]\) 和 \(whe[i]\) 表示：需要跳幾次才能出這個塊，出了這個塊會到哪個點上。

每一次修改彈力系數，最多只會影響本塊內會跳到這個點上的彈簧。

所以每一次修改就重構塊。

于是就歡樂的解決了這道題。

（至今還沒寫對LCT的我就靠這個安慰自己）

#include<bits/stdc++.h>

const int maxn=2e5+5;

class Divid_Block {
    private:

        int a[maxn];
        int belong[maxn],whe[maxn],tim[maxn];
        int block,n,m;

        inline int read() {
            int x;char ch;while(!isdigit(ch=getchar()));
            for(x=ch-'0';isdigit(ch=getchar());x=x*10+ch-'0');
            return x;
        }

        void build() {
            block=sqrt((n+2)/3);
            for(int i=1;i<=n;i++)
                belong[i]=(i-1)/block+1;
            belong[n+1]=belong[n]+1;
            for(int i=n;i;i--) {
                whe[i]=i+a[i];
                int r=block*belong[i]>n?n:block*belong[i];
                if(whe[i]>r) tim[i]=1;
                else tim[i]=tim[whe[i]]+1,whe[i]=whe[whe[i]];
            }
            return ;
        }

        void modify(int pos,int val) {
            a[pos]=val;
            for(int i=block*belong[pos];i>=block*(belong[pos]-1);i--) {
                whe[i]=i+a[i];
                if(whe[i]>block*belong[pos]) tim[i]=1;
                else tim[i]=tim[whe[i]]+1,whe[i]=whe[whe[i]];
            }
        }

        int query(int pos) {
            int ans=0;
            while(pos<=n) ans+=tim[pos],pos=whe[pos];
            return ans;
        }

    public:

        int work() {
            n=read();
            for(int i=1;i<=n;i++) a[i]=read();
            build();
            m=read();
            while(m--) {
                int opt=read(),pos=read();
                ++pos;
                if(opt-1) {
                    int k=read();
                    modify(pos,k);
                }
                else printf("%d\n",query(pos));
            }
            return 0;
        }
}T;

int main() {return T.work();}

注意事項

關于塊的大小，可以參見初中dalao的博客（我的分塊他教的）

關于分塊最優塊大小的思考

還有他寫的那個上了洛咕日報的博客：

淺談基礎根號算法——分塊

lhy %%% 這個 \((A+C)/2\) 在我們機房里天天吊虐我。

分塊適用范圍很廣，基本僅次于 \(n^{2}\) 暴力。

走投無路時可以考慮哦。