2025.5.24 分块

wangzilong913 · 2025-05-24 11:21:54 · 个人记录

114514年没有写总结了，正好今天把蓝书上0x44的例题写完，来久违的写一篇吧。绝对不是集训还有40分钟没事干

分块

一、基本思想

分块思想是将原数据分割为若干小块（通常是 \sqrt{n} ），然后再在每一小块进行一系列预处理，从而通过比较暴力的算法取得更优的时间复杂度。（即空间换时间）。

二、模板&优劣

以AcWing243,洛谷P3372,为例，与树状数组，线段树进行比较

分块思路

题意是很明确的，需要我们做区间加与区间求和。

首先我们可以很轻松地想到暴力做法。第一种操作就循环l~r跑一遍，第二种操作就用前缀和。（显然会超时）

那我们思考一下，将二者融合，同时引入分块。

我们先将数列分成长度不超过\lfloor \sqrt{n} \rfloor的段，预处理处每一段的区间和sum，其中sum[i]表示第i段的和。

对于区间加操作C l r d,我们可以看成两种情况，

1. 若l与r同时在第i块，直接暴力的把a[l]到a[r]加上d。同时，sum[i] 加上d\times(r-l+1).

2. 否则l与r分别在第p块与第q块。对于第p+1块到第q-1块，他们是完整的。令add[p+1]到add[q-1]均加d（add[i]表示第i块额外加的值）。对于开头结尾不足一块的，就像情况1一样暴力更新。

对于区间和操作Q l r，我们同样分两种情况，

1. 在同一块，答案为(a[l]+a[l+1]+...+a[r])+(r-l+1)\times add[i]

2. 在不同块，首先对于第p+1块到第q-1块的完整块，答案加等于sum[i]+add[i]\times len[i]（len[i]为第i段的长度）。然后将开头、结尾不足整块的朴素的累加起来。

这种分块算法对于整段的修改用标记add记录，对于不足一段的修改采取朴素算法。因为段数与段长均为O(\sqrt N)，所以时间复杂度为O((N+Q)\times \sqrt N)，还是很优秀的。

Ac 代码

分块

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5+5;
int n,m;
int a[N];
int n_fk;
int L[N],R[N],b[N],sum[N],lazy[N];
void init(){
    n_fk = sqrt(n);
    for(int i = 1;i <= n_fk;i++){
        L[i] = n_fk*(i-1)+1;
        R[i] = n_fk*i;
    }
    if(R[n_fk] < n){
        L[n_fk+1] = R[n_fk] + 1;
        R[n_fk+1] = n;
        n_fk++;
    }
    for(int i = 1;i <= n_fk;i++){
        for(int j = L[i];j <= R[i];j++){
            b[j] = i;
            sum[i] += a[j];
        }
    }
}
void change(int l,int r,int d){
    int ll = b[l],rr = b[r];
    if(ll == rr){
        for(int i = l;i <= r;i++) a[i]+= d;
        sum[ll] += d*(r-l+1);
    }
    else{
        for(int i = ll + 1;i < rr;i++) lazy[i] += d;
        for(int i = l;i <= R[ll];i++) a[i] += d;
        sum[ll] += d*(R[ll]-l+1);
        for(int i = r;i >= L[rr];i--) a[i] += d;
        sum[rr] += d*(r-L[rr]+1); 
    }
}
int ask(int l,int r){
    int ll = b[l],rr = b[r];
    int res = 0;
    if(ll == rr){
        for(int i = l;i <= r;i++) res += a[i];
        res += lazy[ll] * (r-l+1);
    }
    else{
        for(int i = ll + 1;i < rr;i++) res += sum[i] + lazy[i] * (R[i]-L[i]+1);
        for(int i = l;i <= R[ll];i++) res += a[i];
        res += lazy[ll]*(R[ll]-l+1);
        for(int i = r;i >= L[rr];i--) res += a[i];
        res += lazy[rr]*(r-L[rr]+1); 
    }
    return res;
}
signed main(){
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i = 1;i <= n;i++) cin>>a[i];
    init();
    while(m--){
        char order;
        int l,r,d;
        cin>>order;
        if(order == 'C'){
            cin>>l>>r>>d;
            change(l,r,d);
        }
        else{
            cin>>l>>r;
            cout<<ask(l,r)<<'\n';
        }
    }
    return 0;
}

树状数组

#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int N = 1e5+5;
int n,m;
int a[N],sum[N];
int tree[2][N];
int lowbit(int x){
    return x & -x;
}
void add(int k,int x,int d){
    for(int i = x;i <= n;i += lowbit(i)) tree[k][i] += d;
}
int qsum(int k,int x){
    int res = 0;
    for(int i = x;i > 0;i -= lowbit(i)) res += tree[k][i];
    return res;
}

signed main(){
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i = 1;i <= n;i++){
        cin>>a[i];
        sum[i] = sum[i-1] + a[i];
    }
    while(m--){
        char order;
        cin>>order;
        if(order == 'C'){
            int l,r,d;
            cin>>l>>r>>d;
            add(0,l,d);
            add(0,r+1,-d);
            add(1,l,l*d);
            add(1,r+1,-(r+1)*d);
        }
        else{
            int l,r;
            cin>>l>>r;
            cout<<(sum[r]+(r+1)*qsum(0,r)-qsum(1,r)) - (sum[l-1]+(l-1+1)*qsum(0,l-1)-qsum(1,l-1))<<'\n';
        }
    }
    return 0;
}

线段树

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5+5;
int n,m;
int a[N];
struct Tree{
    int sum,l,r;
    int lazy;
}t[4*N];
void push_up(int u){
    t[u].sum = t[u<<1].sum + t[u<<1|1].sum;
}
void push_down(int u){
    if(t[u].lazy != 0){
        t[u<<1].lazy += t[u].lazy;
        t[u<<1|1].lazy += t[u].lazy;
        t[u<<1].sum += t[u].lazy * (t[u<<1].r - t[u<<1].l + 1);
        t[u<<1|1].sum += t[u].lazy * (t[u<<1|1].r - t[u<<1|1].l + 1);
        t[u].lazy = 0;
    }
}
void build(int u,int l,int r){
    t[u].l = l;
    t[u].r = r;
    if(l == r) t[u].sum = a[l];
    else{
        int mid = l+r >> 1;
        build(u<<1,l,mid);
        build(u<<1|1,mid+1,r);
        push_up(u);
    }
}
void change(int u,int l,int r,int k){
    if(l <= t[u].l && r >= t[u].r){
        t[u].sum += k * (t[u].r - t[u].l + 1);
        t[u].lazy += k;
    }
    else{
        push_down(u);
        int mid = t[u].l + t[u].r >> 1;
        if(l <= mid) change(u<<1,l,r,k);
        if(r > mid) change(u<<1|1,l,r,k);
        t[u].sum = t[u<<1].sum + t[u<<1|1].sum;
    }
}
int ask(int u,int l,int r){
    if(l <= t[u].l && r >= t[u].r) return t[u].sum;
    push_down(u);
    int ans = 0;
    int mid = t[u].l + t[u].r >> 1;
    if(l <= mid) ans += ask(u<<1,l,r);
    if(r > mid) ans += ask(u<<1|1,l,r);
    return ans;
}
signed main(){
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i = 1;i <= n;i++) cin>>a[i];
    build(1,1,n);
    while(m--){
        char order;
        int x,y,k;
        cin>>order;
        if(order == 'C'){
            cin>>x>>y>>k;
            change(1,x,y,k);
        }
        else{
            cin>>x>>y;
            cout<<ask(1,x,y)<<'\n';
        }
    }
    return 0;
}

比较

蒲公英

传送门 to 洛谷

传送门 to AcWing

思路

1. 输入处理与离散化：
   • 读取输入数据，包括蒲公英的数量n和查询次数m，以及蒲公英的种类编号。
   • 对蒲公英的种类编号进行离散化处理，将不同的种类编号映射到连续的整数范围，以减少内存和计算的复杂度。
2. 分块预处理：
   • 计算块的大小blen和块的总数bl。
   • 预处理每个块内每个种类的出现次数，存储在二维数组s中。
   • 预处理每个块区间内的众数，存储在二维数组f中。
3. 查询处理：
   • 对于每个查询，计算实际的查询区间l和r，并处理边界情况。
   • 如果查询区间跨越的块数较少(rb-lb <= 1)，则直接暴力统计区间内每个种类的出现次数，找出众数。 -如果查询区间跨越的块数较多，则分为左零散部分、中间整块部分和右零散部分，分别统计出现次数，合并结果后确定最终的众数。
4. 结果输出：
   • 每次查询后，将结果转换回原始的蒲公英种类编号，并输出。

Ac代码

#include <bits/stdc++.h>
using namespace std;

// 定义常量，N为蒲公英数量的上限，T为块数的上限
const int N = 4e4 + 5;
const int T = 205;

// 声明变量
int n, m, len;
int a[N], b[N]; // a存储蒲公英的种类，b用于离散化处理
int blen, bl; // blen为块的大小，bl为块的数量
int s[T][N], f[T][T]; // s[i][j]表示前i块中第j种蒲公英的总数，f[i][j]表示第i块到第j块的众数
int t[N]; // 临时统计频率的数组

// 自定义快速读取整数函数
int read() {
    int x = 0, p = 1;
    char ch = getchar();
    // 读取符号
    while (ch < '0' || ch > '9') {
        if (ch == '-') p = -1;
        ch = getchar();
    }
    // 读取数字
    while ('0' <= ch && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * p;
}

// 计算块的起始位置
int L(int x) {
    return (x - 1) * blen + 1;
}

// 计算块的结束位置
int R(int x) {
    return min(blen * x, n);
}

// 初始化块和预处理数据
void init() {
    blen = int(sqrt(n)); // 块的大小为n的平方根
    bl = (n - 1) / blen + 1; // 计算块的数量
    // 预处理每个块的频率信息
    for (int i = 1; i <= bl; i++) {
        for (int j = L(i); j <= R(i); j++) {
            s[i][a[j]]++; // 统计当前块中每个种类的蒲公英数量
        }
        // 累加前一块的频率
        for (int j = 1; j <= len; j++) {
            s[i][j] += s[i - 1][j];
        }
    }
    // 预处理块之间的众数信息
    for (int i = 1; i <= bl; i++) {
        for (int j = i; j <= bl; j++) {
            int zs = f[i][j - 1]; // 初始众数为前一块的众数
            // 遍历当前块中的每个元素，更新众数
            for (int k = L(j); k <= R(j); k++) {
                // 比较当前元素的频率与当前众数的频率
                if (s[j][a[k]] - s[i - 1][a[k]] > s[j][zs] - s[i - 1][zs] || 
                    (s[j][a[k]] - s[i - 1][a[k]] == s[j][zs] - s[i - 1][zs] && a[k] < zs)) {
                    zs = a[k];
                }
            }
            f[i][j] = zs; // 记录当前块的众数
        }
    }
}

// 确定某个位置属于哪个块
int find_block(int x) {
    return (x - 1) / blen + 1;
}

int main() {
    // 读取输入
    n = read();
    m = read();
    for (int i = 1; i <= n; i++) {
        b[i] = a[i] = read(); // 读取蒲公英的种类，同时复制到b数组
    }
    // 离散化处理，将a数组中的值映射到连续的整数
    stable_sort(b + 1, b + 1 + n);
    len = unique(b + 1, b + 1 + n) - b - 1;
    for (int i = 1; i <= n; i++) {
        a[i] = lower_bound(b + 1, b + 1 + len, a[i]) - b;
    }
    init(); // 初始化块和预处理数据
    int x = 0; // 上次查询的结果，初始为0
    while (m--) { // 处理每个查询
        int l, r;
        // 计算实际的l和r
        l = ((read() + x - 1) % n) + 1;
        r = ((read() + x - 1) % n) + 1;
        if (l > r) swap(l, r); // 确保l <= r
        int lb = find_block(l); // l所在的块
        int rb = find_block(r); // r所在的块
        int res = 0; // 结果，初始化为0
        if (rb - lb <= 1) { // 如果区间在同一个块或相邻块
            // 直接遍历区间统计频率
            for (int i = l; i <= r; i++) {
                t[a[i]]++;
            }
            // 找出出现次数最多的元素
            for (int i = l; i <= r; i++) {
                if (t[a[i]] > t[res] || (t[a[i]] == t[res] && a[i] < res)) {
                    res = a[i];
                }
            }
            // 清空临时数组
            for (int i = l; i <= r; i++) {
                t[a[i]] = 0;
            }
        } else { // 区间跨多个块
            // 处理前缀块和后缀块
            for (int i = l; i <= R(lb); i++) {
                t[a[i]]++;
            }
            for (int i = L(rb); i <= r; i++) {
                t[a[i]]++;
            }
            // 中间块的众数
            res = f[lb + 1][rb - 1];
            // 比较前缀块中的元素
            for (int i = l; i <= R(lb); i++) {
                int x = t[a[i]] + s[rb - 1][a[i]] - s[lb][a[i]];
                int y = t[res] + s[rb - 1][res] - s[lb][res];
                if (x > y || (x == y && a[i] < res)) {
                    res = a[i];
                }
            }
            // 比较后缀块中的元素
            for (int i = L(rb); i <= r; i++) {
                int x = t[a[i]] + s[rb - 1][a[i]] - s[lb][a[i]];
                int y = t[res] + s[rb - 1][res] - s[lb][res];
                if (x > y || (x == y && a[i] < res)) {
                    res = a[i];
                }
            }
            // 清空临时数组
            for (int i = l; i <= R(lb); i++) {
                t[a[i]] = 0;
            }
            for (int i = L(rb); i <= r; i++) {
                t[a[i]] = 0;
            }
        }
        x = b[res]; // 将结果转换回原始的蒲公英种类编号
        printf("%d\n", x); // 输出结果
    }
    return 0;
}