分块

sccc_ · 2025-08-01 17:31:11 · 个人记录

分块

分块是一种思想，名为分块思想。

顾名思义，把一个东西分成一些块来解决问题。通常为预处理每个块再修改或查询。

通常，我们把它长度定为 len = \sqrt{n}，一共有 num = n \div len 段。

预处理

定义 L_i 为第 i 段的左端点，R_i 为第 i 段的右端点。则第 i 段的左端点为 (i - 1) \times len + 1，右端点为 i \times len。pos_i 为第 i 个数属于第 pos_i 个块。

注意：在最后一段长度不足 len，即多为最后几个剩余的元素多开了一个块时，R_{num} > n，需要特殊判断。

修改

对于一段区间 [l,r]，会有一些完整的块（可能没有）与两段散块分别分布在 [l,R_{pos_l}] 与 [L_{pos_r},r]（可能没有）。

对于散块，我们直接暴力处理。

其余的完整的块，我们对他进行懒标记，等查询时再对其进行操作。

注意：当 pos_l = pos_r 时，证明两端在一个段中，只需要暴力处理就行。

查询

依然按照上面的原理，找出散块和完整的块。

对于散块，依然暴力，还要加上懒标记乘上散块的长度。

其余的完整的块，直接获取块的值再加上懒标记乘上完整块的长度即可。

注意：当 pos_l = pos_r 时，证明两端在一个段中，只需要暴力处理就行。

U522567 ١١(❛ᴗ❛)【分块】-区间修改，单点查询（数据需要加强）

单点查询就更简单了，答案就是数组当前点的值加上当前点所在块的懒标记。

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 5e4 + 10;

int n, m, L[N], R[N], pos[N], lazy[N], sum[N], a[N];

void init() {
    int len = sqrt(n);
    int num = n / len;
    if (n % len != 0) {
        num++;
    }
    for (int i = 1; i <= num; i++) {
        L[i] = (i - 1) * len + 1;
        R[i] = i * len;
    }
    if (R[num] > n) {
        R[num] = n;
    }
    for (int i = 1; i <= num; i++) {
        for (int j = L[i]; j <= R[i]; j++) {
            pos[j] = i;
            sum[i] += a[j];
        }
    }
}

void change(int l, int r, int val) {
    int p = pos[l], q = pos[r];
    if (p == q) {
        for (int i = l; i <= r; i++) {
            a[i] += val;
        }
        sum[p] += (r - l + 1) * val;
    } else {
        for (int i = l; i <= R[p]; i++) {
            a[i] += val;
        }
        sum[p] += (R[p] - l + 1) * val;
        for (int i = L[q]; i <= r; i++) {
            a[i] += val;
        }
        sum[q] += (r - L[q] + 1) * val;
        for (int i = p + 1; i <= q - 1; i++) {
            lazy[i] += val;
        }
    }
}

int query(int x) {
    int p = pos[x], q = pos[x], ans = 0;
//  if (p == q) {
        ans += a[x];
        ans += lazy[p] * 1;
//  } else {
//      for (int i = l; i <= R[p]; i++) {
//          ans += a[i];
//      }
//      ans += (R[p] - l + 1) * lazy[p];
//      for (int i = L[q]; i <= r; i++) {
//          ans += a[i];
//      }
//      ans += (r - L[q] + 1) * lazy[q];
//      for (int i = p + 1; i <= q - 1; i++) {
//          ans += sum[i] * lazy[i] * (R[i] - L[i] + 1);
//      }
//  }
    return ans;
}

signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    init();
    while (n--) {
        int op, l, r, c;
        cin >> op >> l >> r >> c;
        if (!op) {
            change(l, r, c);
        } else {
            cout << query(r) << '\n';
        }
    }
    return 0;
} 

U522568 ١١(❛ᴗ❛)【分块】-区间修改，区间查询

只需要最后模 c + 1 即可。

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 5e4 + 10;

int n, m, L[N], R[N], pos[N], lazy[N], sum[N], a[N];

void init() {
    int len = sqrt(n);
    int num = n / len;
    if (n % len != 0) {
        num++;
    }
    for (int i = 1; i <= num; i++) {
        L[i] = (i - 1) * len + 1;
        R[i] = i * len;
    }
    if (R[num] > n) {
        R[num] = n;
    }
    for (int i = 1; i <= num; i++) {
        for (int j = L[i]; j <= R[i]; j++) {
            pos[j] = i;
            sum[i] += a[j];
        }
    }
}

void change(int l, int r, int val) {
    int p = pos[l], q = pos[r];
    if (p == q) {
        for (int i = l; i <= r; i++) {
            a[i] += val;
        }
        sum[p] += (r - l + 1) * val;
    } else {
        for (int i = l; i <= R[p]; i++) {
            a[i] += val;
        }
        sum[p] += (R[p] - l + 1) * val;
        for (int i = L[q]; i <= r; i++) {
            a[i] += val;
        }
        sum[q] += (r - L[q] + 1) * val;
        for (int i = p + 1; i <= q - 1; i++) {
            lazy[i] += val;
        }
    }
}

int query(int l, int r) {
    int p = pos[l], q = pos[r], ans = 0;
    if (p == q) {
        for (int i = l; i <= r; i++) {
            ans += a[i];
        }
        ans += lazy[p] * (r - l + 1);
    } else {
        for (int i = l; i <= R[p]; i++) {
            ans += a[i];
        }
        ans += (R[p] - l + 1) * lazy[p];
        for (int i = L[q]; i <= r; i++) {
            ans += a[i];
        }
        ans += (r - L[q] + 1) * lazy[q];
        for (int i = p + 1; i <= q - 1; i++) {
            ans += sum[i] + lazy[i] * (R[i] - L[i] + 1);
        }
    }
    return ans;
}

signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    init();
    while (n--) {
        int op, l, r, c;
        cin >> op >> l >> r >> c;
        if (!op) {
            change(l, r, c);
        } else {
            cout << query(l, r) % (c + 1) << '\n';
        }
    }
    return 0;
} 

P2357 守墓人

建议降黄。

相当于单点修改，单点查询，区间查询，区间修改。

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 2e5 + 10;

int n, m, L[N], R[N], pos[N], lazy[N], sum[N], a[N];

void init() {
    int len = sqrt(n);
    int num = n / len;
    if (n % len != 0) {
        num++;
    }
    for (int i = 1; i <= num; i++) {
        L[i] = (i - 1) * len + 1;
        R[i] = i * len;
    }
    if (R[num] > n) {
        R[num] = n;
    }
    for (int i = 1; i <= num; i++) {
        for (int j = L[i]; j <= R[i]; j++) {
            pos[j] = i;
            sum[i] += a[j];
        }
    }
}

void change(int l, int r, int val) {
    int p = pos[l], q = pos[r];
    if (p == q) {
        for (int i = l; i <= r; i++) {
            a[i] += val;
        }
        sum[p] += (r - l + 1) * val;
    } else {
        for (int i = l; i <= R[p]; i++) {
            a[i] += val;
        }
        sum[p] += (R[p] - l + 1) * val;
        for (int i = L[q]; i <= r; i++) {
            a[i] += val;
        }
        sum[q] += (r - L[q] + 1) * val;
        for (int i = p + 1; i <= q - 1; i++) {
            lazy[i] += val;
        }
    }
}

int query(int l, int r) {
    int p = pos[l], q = pos[r], ans = 0;
    if (p == q) {
        for (int i = l; i <= r; i++) {
            ans += a[i];
        }
        ans += lazy[p] * (r - l + 1);
    } else {
        for (int i = l; i <= R[p]; i++) {
            ans += a[i];
        }
        ans += (R[p] - l + 1) * lazy[p];
        for (int i = L[q]; i <= r; i++) {
            ans += a[i];
        }
        ans += (r - L[q] + 1) * lazy[q];
        for (int i = p + 1; i <= q - 1; i++) {
            ans += sum[i] + lazy[i] * (R[i] - L[i] + 1);
        }
    }
    return ans;
}

signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    init();
    while (m--) {
        int op;
        cin >> op;
        if (op == 1) {
            int l, r, k;
            cin >> l >> r >> k;
            change(l, r, k);
        } else if (op == 2) {
            int k;
            cin >> k;
            a[1] += k;
        } else if (op == 3) {
            int k;
            cin >> k;
            a[1] -= k;
        } else if (op == 4) {
            int l, r;
            cin >> l >> r;
            cout << query(l, r) << '\n';
        } else {
            cout << a[1] << '\n';
        }
    }
    return 0;
} 

U522569 ١١(❛ᴗ❛)【分块】-区间修改，区间小值查询

对块里的数进行排序。修改时，散块暴力，其余的懒标记，且对其重新排序。查询时，散块暴力，其余的，因为有懒标记，所以实际要找的数是 k - lazy_i，再 lower_bound 即可。

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;

int n, m, L[N], R[N], pos[N], lazy[N], sum[N], a[N];
vector<int> G[N];

void init() {
    int len = sqrt(n);
    int num = n / len;
    if (n % len != 0) {
        num++;
    }
    for (int i = 1; i <= num; i++) {
        L[i] = (i - 1) * len + 1;
        R[i] = i * len;
    }
    R[num] = n;
    for (int i = 1; i <= num; i++) {
        for (int j = L[i]; j <= R[i]; j++) {
            pos[j] = i;
            G[i].push_back(a[j]);
        }
        sort(G[i].begin(), G[i].end());
    }
}

void EA(int l, int r, int k) {
    int p = pos[l];
    for (int i = l; i <= r; i++) {
        a[i] += k;
    }
    G[p].clear();
    for (int i = L[p]; i <= R[p]; i++) {
        G[p].push_back(a[i]);
    }
    sort (G[p].begin(), G[p].end());
}

void change(int l, int r, int val) {
    int p = pos[l], q = pos[r];
    if (p == q) {
        EA(l, r, val);
        return;
    }
    EA(l, R[p], val);
    EA(L[q], r, val);
    for (int i = p + 1; i <= q - 1; i++) {
        lazy[i] += val;
    }
}

int query(int l, int r, int k) {
    vector<int> v;
    for (int i = l; i <= r; i++) {
        v.push_back(a[i] + lazy[pos[l]]);
    }
    sort(v.begin(), v.end());
    return lower_bound(v.begin(), v.end(), k) - v.begin();
}

int ask(int l, int r, int k) {
    int p = pos[l], q = pos[r];
    if (p == q) {
        return query(l, r, k);
    }
    int ans = 0;
    ans += query(l, R[p], k) + query(L[q], r, k);
    for (int i = p + 1; i <= q - 1; i++) {
        ans += lower_bound(G[i].begin(), G[i].end(), k - lazy[i]) - G[i].begin();
    } 
    return ans;
}

signed main() {
    cin.tie(0), cout.tie(0)->sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    init();
    while (n--) {
        int op, l, r, k;
        cin >> op >> l >> r >> k;
        if (op == 0) {
            change(l, r, k);
        } else {
            cout << ask(l, r, k * k) << '\n';
        }
    }
    return 0;
}