【补】分块学习笔记

YDMaYi · 2025-02-08 19:13:14 · 个人记录

什么是分块

既然叫分块，那么就是把某个东西分成若干块来操作，以达到简化操作或优化效率的目的。

同时，分块十分好写，而且是一种非常美丽的数据结构（因为十分暴力）。

以线段树 1 为例，这是它的分块做法：

维护一个数组，对它进行分块，每块长度为 S（一般定义成 \sqrt n），那么很显然分成 \left\lceil\dfrac{n}{S}\right\rceil（块长取 \sqrt n 就有 \sqrt n 块）块。这些块支持区间查询和区间修改。类似维护线段树的操作，每块维护一个 tag 表示区间共同加上的数，和一个块内和 sum，可用于整块查询或整块修改。

查询操作：查询的区间可以看成覆盖了若干大块和一堆散点（称为散块）。大块直接用 sum 代替，散块直接暴力查询。

修改操作：类似地，修改整块直接改 tag，修改散块直接在原数组上改就好了。

code：

#include<bits/stdc++.h>

#define int long long

namespace IO {
    inline int read() {
        int ret = 0, f = 1;char ch = getchar();
        while (ch < '0' || ch > '9') {
            if (ch == '-') f = -f;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9') {
            ret = (ret << 1) + (ret << 3) + (ch ^ 48);
            ch = getchar();
        }
        return ret * f;
    }
    void write(int x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}

using namespace std;
using namespace IO;

const int maxn = 1e5 + 5;
/*
a 原数组
tag 整块标记
sum 整块和
f f[i]表示第i个数属于第几个块
L/R 每个块的左/右端点编号
*/
int a[maxn], tag[maxn], sum[maxn], f[maxn], L[maxn], R[maxn];
int n, m, len;

int query(int l, int r) {
    int fr = f[l], to = f[r], ans = 0;
    if (fr == to) {//注意特判同块
        for (int i = l;i <= r;i++) ans += a[i] + tag[i];
        return ans;
    }
    for (int i = fr + 1;i < to;i++) ans += sum[i];
    for (int i = l;i <= R[fr];i++) ans += a[i] + tag[fr];//别漏tag
    for (int i = L[to];i <= r;i++) ans += a[i] + tag[to];//别漏tag
    return ans;
}

void update(int l, int r, int k) {
    int fr = f[l], to = f[r];
    if (fr == to) {//注意特判同块
        for (int i = l;i <= r;i++) a[i] += k, sum[fr] += k;     
        return;
    }
    for (int i = fr + 1;i < to;i++) tag[i] += k, sum[i] += k * (R[i] - L[i] + 1);//tag!!
    for (int i = l;i <= R[fr];i++) a[i] += k, sum[fr] += k;//sum别忘
    for (int i = L[to];i <= r;i++) a[i] += k, sum[to] += k;//sum别忘
    return;
}

void init() {
    len = sqrt(n);
    for (int i = 1;i <= len;i++) {
        L[i] = (i - 1) * len + 1;
        R[i] = i * len;
        for (int j = L[i];j <= R[i];j++) {
            f[j] = i;
            sum[i] += a[j];
        }
    }
    if (R[len] != n) {//整除不了就作最后一块
        len++;
        L[len] = R[len - 1] + 1;
        R[len] = n;
        for (int i = L[len];i <= R[len];i++) {
            f[i] = len;
            sum[len] += a[i];
        }
    }
}

signed main() {
    n = read(), m = read();
    for (int i = 1;i <= n;i++) a[i] = read();

    init();

    while (m--) {
        int op = read(), x = read(), y = read(), k;
        if (op == 1) {
            k = read();
            update(x, y, k);
        }
        else write(query(x, y)), puts("");
    }

    return 0;
}

P2801 教主的魔法

传送门 <- 一道分块入门

求区间不大于 C 的数的个数，可以引进一个数组 b，初始时等于原数组，将每个块内的数进行排序，使得每个块内的数有序。于是查询时就可以对每个块内二分，找第一个大于等于 C 的数，从而计算出块内大于等于 C 的数的个数。

几个注意点：

1.整块修改的时候对相对顺序不改变，所以不用重新排序，改散块时要对块内重排。

2.二分可以用 upper_bound 或 lower_bound 代替。

3.整块重排的时候要把整块复制下来，因为相对顺序变了。

code：

#include<bits/stdc++.h>

#define int long long

namespace IO {
    inline int read() {
        int ret = 0, f = 1;char ch = getchar();
        while (ch < '0' || ch > '9') {
            if (ch == '-') f = -f;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9') {
            ret = (ret << 1) + (ret << 3) + (ch ^ 48);
            ch = getchar();
        }
        return ret * f;
    }
    void write(int x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}

using namespace IO;
using namespace std;

const int maxn = 1e6 + 5;
#define INF 2147483647

int n, m;
int a[maxn], b[maxn], L[maxn], R[maxn], lazy[maxn], num[maxn];

void init() {
    int x = sqrt(n);
    for (int i = 1;i <= x;i++) {
        L[i] = (i - 1) * x + 1;
        R[i] = i * x;
        for (int j = L[i];j <= R[i];j++) num[j] = i;
        sort(b + L[i], b + R[i] + 1);
    }
    if (R[x] != n) {
        x++;
        L[x] = R[x - 1] + 1;
        R[x] = n;
        for (int i = L[x];i <= R[x];i++) num[i] = x;
        sort(b + L[x], b + R[x] + 1);
    }
    return;
}

void update(int l, int r, int x) {
    int lk = num[l], rk = num[r];

    if (lk == rk) {
        for (int i = l;i <= r;i++) a[i] += x;
        for (int i = L[lk];i <= R[lk];i++) b[i] = a[i];
        sort(b + L[lk], b + R[rk] + 1);
        return;
    }

    for (int i = l;i <= R[lk];i++) a[i] += x;
    for (int i = L[lk];i <= R[lk];i++) b[i] = a[i];

    for (int i = lk + 1;i < rk;i++) lazy[i] += x;

    for (int i = L[rk];i <= r;i++) a[i] += x;
    for (int i = L[rk];i <= R[rk];i++) b[i] = a[i];

    sort(b + L[lk], b + R[lk] + 1);
    sort(b + L[rk], b + R[rk] + 1);

    return;
}

int query(int l, int r, int k) {
    int lk = num[l], rk = num[r], cnt = 0;

    if (lk == rk) {
        for (int i = l;i <= r;i++) cnt += (a[i] + lazy[lk]) >= k;
        return cnt;
    }

    for (int i = lk + 1;i < rk;i++) {
        int le = L[i], ri = R[i], mid;
        while (le <= ri) {
            mid = le + ri >> 1; 
            if (b[mid] + lazy[i] < k) le = mid + 1;
            else ri = mid - 1;
        }
        cnt += R[i] - le + 1;
    }

    for (int i = l;i <= R[lk];i++) cnt += (a[i] + lazy[lk]) >= k;

    for (int i = L[rk];i <= r;i++) cnt += (a[i] + lazy[rk]) >= k;

    return cnt;     
}

signed main() {
    n = read(), m = read();
    for (int i = 1;i <= n;i++) a[i] = read(), b[i] = a[i];

    init();

    while (m--) {
        char op;cin >> op;
        int l = read(), r = read(), k = read();

        if (op == 'A') write(query(l, r, k)), puts("");
        else update(l, r, k);
    }

    return 0;
}

P5356 [Ynoi Easy Round 2017] 由乃打扑克

求区间第 k 大，首先想到二分答案，二分区间第 k 大的值 x。然后和教主的魔法一样二分统计比 x 大的数的个数，从而找到区间第 k 大值。

总得来说就是分块，然后二分套二分。

然而发现似乎 T 了一些点？需要一些卡常。考虑用两个函数求出区间里的最大值和最小值，以缩小第一个二分的上下界。然后就能过了。

code：

#include<bits/stdc++.h>

#define int long long

namespace IO {
    inline int read() {
        int ret = 0, f = 1;char ch = getchar();
        while (ch < '0' || ch > '9') {
            if (ch == '-') f = -f;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9') {
            ret = (ret << 1) + (ret << 3) + (ch ^ 48);
            ch = getchar();
        }
        return ret * f;
    }
    void write(int x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}

using namespace IO;
using namespace std;

const int maxn = 1e5 + 5;
#define INF 2147483647

int n, m;
int a[maxn], b[maxn], L[maxn], R[maxn], lazy[maxn], num[maxn];

void init() {
    int x = sqrt(n);
    for (int i = 1;i <= x;i++) {
        L[i] = (i - 1) * x + 1;
        R[i] = i * x;
        for (int j = L[i];j <= R[i];j++) num[j] = i;
        sort(b + L[i], b + R[i] + 1);
    }
    if (R[x] != n) {
        x++;
        L[x] = R[x - 1] + 1;
        R[x] = n;
        for (int i = L[x];i <= R[x];i++) num[i] = x;
        sort(b + L[x], b + R[x] + 1);
    }
    return;
}

void update(int l, int r, int x) {
    int lk = num[l], rk = num[r];

    if (lk == rk) {
        for (int i = l;i <= r;i++) a[i] += x;
        for (int i = L[lk];i <= R[lk];i++) b[i] = a[i];
        sort(b + L[lk], b + R[rk] + 1);
        return;
    }

    for (int i = l;i <= R[lk];i++) a[i] += x;
    for (int i = L[lk];i <= R[lk];i++) b[i] = a[i];

    for (int i = lk + 1;i < rk;i++) lazy[i] += x;

    for (int i = L[rk];i <= r;i++) a[i] += x;
    for (int i = L[rk];i <= R[rk];i++) b[i] = a[i];

    sort(b + L[lk], b + R[lk] + 1);
    sort(b + L[rk], b + R[rk] + 1);

    return;
}

int check(int l, int r, int x) {
    int lk = num[l], rk = num[r];
    int cnt = 0;

    if (lk == rk) {
        for (int i = l;i <= r;i++) if (a[i] + lazy[lk] <= x) cnt++;
        return cnt;
    }

    for (int i = l;i <= R[lk];i++) if (a[i] + lazy[lk] <= x) cnt++;

    for (int i = lk + 1;i < rk;i++) {
        if (b[L[i]] + lazy[i] > x) continue;
        if (b[R[i]] + lazy[i] <= x) {
            cnt += R[i] - L[i] + 1;
            continue;
        }

        int left = L[i], right = R[i], mid; 
        while (left < right) {
            mid = (left + right >> 1) + 1;
            if (b[mid] + lazy[i] <= x) left = mid;  
            else right = mid - 1;
        }
        if (b[left] + lazy[i] <= x) cnt += left - L[i] + 1;
    }

    for (int i = L[rk];i <= r;i++) if (a[i] + lazy[rk] <= x) cnt++;

    return cnt;
}

int getmin(int l, int r) {
    int ans = INF, lk = num[l], rk = num[r];

    if (lk == rk) {
        for (int i = l;i <= r;i++) ans = min(ans, a[i] + lazy[lk]);
        return ans;
    }

    for (int i = l;i <= R[lk];i++) ans = min(ans, a[i] + lazy[lk]);

    for (int i = lk + 1;i < rk;i++) ans = min(ans, b[L[i]] + lazy[i]);

    for (int i = L[rk];i <= r;i++) ans = min(ans, a[i] + lazy[rk]);

    return ans;
}

int getmax(int l, int r) {
    int ans = -INF, lk = num[l], rk = num[r];

    if (lk == rk) {
        for (int i = l;i <= r;i++) ans = max(ans, a[i] + lazy[lk]);
        return ans;
    }

    for (int i = l;i <= R[lk];i++) ans = max(ans, a[i] + lazy[lk]);

    for (int i = lk + 1;i < rk;i++) ans = max(ans, b[R[i]] + lazy[i]);

    for (int i = L[rk];i <= r;i++) ans = max(ans, a[i] + lazy[rk]);

    return ans;
}

int query(int l, int r, int k) {
    if (k < 1 || k > r - l + 1) return -1;

    int lef = getmin(l, r), rig = getmax(l, r), ans = -1, mid;

    while (lef <= rig) {
        mid = lef + rig >> 1;
        if (check(l, r, mid) < k) lef = mid + 1;    
        else rig = mid - 1, ans = mid;
    }

    return ans;     
}

signed main() {
    n = read(), m = read();
    for (int i = 1;i <= n;i++) a[i] = read(), b[i] = a[i];

    init();

    while (m--) {
        int op = read(), l = read(), r = read(), k = read();

        if (op == 1) write(query(l, r, k)), puts("");
        else update(l, r, k);
    }

    return 0;
}