分块算法

分块算法，是一种十分巧妙的算法，将优美与暴力融为一体，可以解决很多的题目

例题

弹飞绵羊（BZOJ）
洛谷的

题目大意就是有一个链状的弹簧装置，每个装置能将在上面的物体向后弹一定距离直至出界，每次询问从一个位置出发弹飞次数或修改某位置弹飞距离

这道题原本是LCT入门题，接下来我们将会看到分块是如何简洁地处理这道题目的

分块

什么是分块？
分块将所有数据分为若干个块，维护块内信息，使得块内的查询是\(O(1)\)的，而总的询问就可以看做若干个块询问的总和

为了使时间复杂度均摊，我们将块的大小设为\(O(\sqrt{n})\)
这样一来每次查询最多遍历\(O(\sqrt{n})\)个块，每个块是\(O(1)\)，总的就是\(O(\sqrt{n})\)
对于修改，由于我们维护的是块内信息，对于单个块的修改是\(O(\sqrt{n})\)的，若一次修改横跨若干个块，只需将完全覆盖的块打标记即可，每次最多需要修改两个块
总复杂度\(O(q\sqrt{n})\)

题解

对于这道题，我们将弹簧分块，对于每个弹簧维护其step[i]表示其弹几次出块，nxt[i]表示弹出块后到达的位置
对于每次查询，我们统计step[i]，块间转移
对于每次修改，暴力在块内修改step[]和nxt[]即可

总的来说，分块算法是一种优雅的暴力，在代码复杂度和时间复杂度上，有一个很好的平衡

代码【比LCT短多了】：

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define BUG(s,n) for (int i = 1; i <= (n); i++) cout<<s[i]<<' '; puts("");
using namespace std;
const int maxn = 200005,maxm = 100005,INF = 1000000000;
inline int read(){
    int out = 0,flag = 1; char c = getchar();
    while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}
    while (c >= 48 && c <= 57) {out = (out << 3) + (out << 1) + c - '0'; c = getchar();}
    return out * flag;
}
int n,m,T;
int K[maxn],step[maxn],nxt[maxn],b[maxn];
void query(int u){
    int ans = 0;
    while (u){
        ans += step[u];
        u = nxt[u];
    }
    printf("%d\n",ans);
}
void modify(int u,int k){
    K[u] = k;
    for (int i = u; b[i] == b[u] && i; i--){
        if (i + K[i] > n) step[i] = 1,nxt[i] = 0;
        else if (b[i] != b[i + K[i]]) step[i] = 1,nxt[i] = i + K[i];
        else step[i] = step[i + K[i]] + 1,nxt[i] = nxt[i + K[i]];
    }
}
int main(){
    n = read();  T = (int)sqrt(n);
    for (int i = 1; i <= n; i++) K[i] = read(),b[i] = i / T;
    for (int i = n; i; i--){
        if (i + K[i] > n) step[i] = 1,nxt[i] = 0;
        else if (b[i] != b[i + K[i]]) step[i] = 1,nxt[i] = i + K[i];
        else step[i] = step[i + K[i]] + 1,nxt[i] = nxt[i + K[i]];
    }
    m = read(); int opt,u;
    while (m--){
        opt = read(); u = read() + 1;
        if (opt & 1) query(u);
        else modify(u,read());
    }
    return 0;
}