首页 > 其他分享 >分块

分块

时间:2024-07-24 16:33:56浏览次数:12  
标签:分块 int lin rin bl MAXN

分块

数列分块入门4

  1. 区间修改
  2. 区间查询

区间修改正常。但是区间查询有几个需要注意的点:

1.需要取模。(这里对喜欢疯狂取模的人提个醒:千万不要在 bl[l] = ... 那里取模啊,把块数给模了就完全错了,还有一些不能模的地方一定要看清楚!!!)

2.用懒标记算答案的时候一定要乘上 r-l+1 ,别单点查询写多了忘记基本操作了啊。

开始讲题

这是我的部分的第一个题目,所以会讲得细一点。

分块:
数列分块算法就是把一个数列分成 \(\sqrt n\) 个块,每次处理的时候整块的用懒标记 $ O(1)$ 的时间复杂度来更新,两边的可能存在的不是整块的分散的块可以在 \(O(2 \cdot \sqrt n)\) 的时间复杂度内完成。是很优的暴力。

下面分块来讲解 分块算法。


块状数组的建立

确定块长。

大多数情况下都是取 \(\sqrt n\)

确定块的左右端点

块左端点为上一个块右端点 +1,右端点即为当前块编号乘块长。

维护块内信息

比如所属区间和区间和等内容。

len=sqrt(n);//1. 块长
for(int i=1;i<=len;i++)
	L[i]=R[i-1]+1,R[i]=i*len;//2. 块端点
R[len]=n;
for(int i=1;i<=len;i++)
	for(int j=L[i];j<=R[i];j++)
		bel[j]=i;//3. 所属区间

初始化和之上所述基本没有变化。此时的块内信息需要维护区间和。

for(int i=1;i<=len;i++) //枚举块
	for(int j=L[i];j<=R[i];j++) //枚举块内的每一位
		bel[j]=i,sum[i]+=a[j]; //赋编号并统计块内和 

区间加的时候分情况讨论:在整块的和不在整块的。

1.要修改的在一个块里面

if(lin==rin) {
	for(int i=l;i<=r;i++)
		a[i]+=k,sum[lin]+=k;
	return;
}

2.要修改的不再一个块里面(一个块加上两边的不完整的块或者是好几个块):

for(int i=l;i<=R[lin];i++)//左边的零散块
	sum[lin]+=k,a[i]+=k;
for(int i=L[rin];i<=r;i++)//右边的零散块
	sum[rin]+=k,a[i]+=k;
for(int i=lin+1;i<rin;i++)//中间的整块
	tag[i]+=k;

ps:lin和rin是开始点在的块,rin是结束点在的块。

接下来考虑区间求和。

求和的代码基本和区间修改是一样的。

我们把不再一个整块的单独用 for 循环加上。我们把整块的用懒标记乘上块的大小即可。

int query(int l ,int r, int mod) {
    int lin = bl[l], rin = bl[r];
    int ans=0;
	if(lin==rin)
	{
		for(int i=l;i<=r;i++)
			ans=(ans+a[i]+tag[lin])%mod;
		return ans;
	}

	for(int i=l;i<=R[lin];i++)
		ans=(ans+a[i]+tag[lin])%mod;
	for(int i=L[rin];i<=r;i++)
		ans=(ans+a[i]+tag[rin])%mod;
	for(int i=lin+1;i<rin;i++)
		ans=(ans+sum[i] + tag[i]*(R[i] - L[i] + 1))%mod;

	return ans % mod;
}

由于和上面的基本一样,就不打注释了。

完整代码,注意文章一开始说的温馨提示:

#include <bits/stdc++.h>

#define int long long
#define MAXN 100005

using namespace std;

int n;
int len;
int a[MAXN];
int c;

int L[MAXN], R[MAXN];
int bl[MAXN];
int sum[MAXN];
int tag[MAXN];

void update(int l, int r, int val) {
    int lin = bl[l]; 
    int rin = bl[r];

    if (lin == rin) {
        for (int i = l; i <= r; ++i) {
            sum[lin] += val;
            a[i] += val;
        }
        return ;
    }
    for (int i = l; i <= R[lin]; ++i) {
        sum[lin] += val;
        a[i] += val;
    }
    for (int i = L[rin]; i <= r; ++i) {
        sum[rin] += val;
        a[i] += val;
    }
    for (int i = lin+1; i < rin; ++i) {
        tag[i] += val;
    }

    return ;
}

int query(int l ,int r, int mod) {
    int lin = bl[l], rin = bl[r];
    int ans=0;
	if(lin==rin)
	{
		for(int i=l;i<=r;i++)
			ans=(ans+a[i]+tag[lin])%mod;
		return ans;
	}

	for(int i=l;i<=R[lin];i++)
		ans=(ans+a[i]+tag[lin])%mod;
	for(int i=L[rin];i<=r;i++)
		ans=(ans+a[i]+tag[rin])%mod;
	for(int i=lin+1;i<rin;i++)
		ans=(ans+sum[i] + tag[i]*(R[i] - L[i] + 1))%mod;

	return ans % mod;
}

signed main() {
    cin >> n;
    len = sqrt(n);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    for (int i = 1; i <= len; ++i) {
        L[i] = (R[i - 1] + 1);
        R[i] = len * i; 
    }
    R[len] = n;

    for (int i = 1; i <= len; ++i) {
        for (int j = L[i]; j <= R[i]; ++j) {
            bl[j] = i;
            sum[i] += a[j];
        }
    }

    for (int i = 1; i <= n; ++i) {
        int opt, l ,r;
        cin >> opt >> l >> r >> c;
        if (opt == 0) {
            update(l, r, c);
        }
        if (opt == 1) {
            cout << query(l, r, c+ 1) % (c+1) << endl;
        }
    }
    return 0;
}

完结散花。给个赞吧!

标签:分块,int,lin,rin,bl,MAXN
From: https://www.cnblogs.com/blogs-for-Ruan-ji/p/18320788

相关文章

  • 使用 AES-GCM 分块加密文件
    我想编写一个生成器,以给定大小的块来加密文件并一一返回块。我还想验证有效负载,因此我为此选择了AES-GCM。为什么我要分块加密而不是一次性加密整个文件?我通过网络发送这些块,因此我不是加密整个(可能很大)文件,将其存储在其他地方,然后在进行网络传输时再次对其进行分块,而是加密......
  • 整除分块
    整除分块为什么放在\(9.\)这个板块捏?感觉前面很多地方都会浅浅涉及建议阅读数论函数基础章节,了解基本概念与先要知识又称数论分块,因其解决的问题与整除密切相关而得名,常用于求解形如\[\begin{aligned}\sum_{i=1}^n{f(i)g\left( \left\lfloor \df......
  • 分块入门
    基本思想把一个需要操作的序列分成若干块,分别处理,从而优化时间复杂度。容易证明块长为\(\sqrtn\)时复杂度最优。分块常规单次操作复杂度为\(\mathcal{O}(\sqrtn)\),一般可以当做\(\mathcal{O}(\log^2n)\)来计算复杂度。接下来给几道例题。T1给出一个长为\(n\)的数列......
  • 基于springboot+vue的分块下载文件解决思路
    目录基于fastdfs文件服务nginx+fastdfs启用slice,range进行下载。基于springboot的应用服务器转发nginx服务的文件请求服务。vue使用asyn和await进行请求和合并文件添加进度条一、fastdfs文件服务启动fastdfs服务命令:/usr/bin/fdfs_storaged/etc/fdfs/storage.confstart......
  • 【Python&RS】基于Python分块处理大型遥感影像的方法
    ​    RSer工作时不可避免会用到大型的遥感影像,由于分辨率过高、区域过大、波段信息过多等原因,都会导致数据非常的大。这个时候我们在进行一些简单的操作,如计算NDVI、二值化、分类等时,计算机的内存都会溢出。因此今天跟大家分享一下我平时分块的方法,中间如何计算就按照......
  • 断点续传:使用java对大文件进行分块与合并
    通常我们下载上传的视频文件比较大。虽然https协议没有规定上传文件大小的限制,但是网络的质量,电脑硬件的参差不齐可能会导致大文件快要上传完成的时候突然断网了要重新上传,非常影响用户体验。以此我们引入了断点续传的功能。什么是断点续传呢?就是我们在上传下载文件的时候,将一个......
  • 欧拉函数、整除分块和扩展欧几里得
    欧拉函数欧拉函数(写作\(\varphi(x)\)),表示\(i\in[1,x]且\gcd(i,x)=1\)的\(i\)的数量。乍一看好像很难求,但我们先考虑最简单的情况,即\(x\in\mathbb{P}\)(\(\mathbb{P}\)表示质数集)的情况。首先很容易看出\(\varphi(x)=x-1\),因为\(x\in\mathbb{P}\),所以\(\foralli......
  • 从 dfs 序求 lca 到虚树到树分块 学习笔记
    前言想象我在口胡三样我都不熟悉的东西并尝试称之为“学习笔记”。其实不过是我自己对于它的一点小理解,甚至可能是错误的!无所谓,口胡!口胡!口胡!口胡!口胡!一些备注\(dfn_u\)为点\(u\)的dfn序,\(nfd_i\)表示第\(i\)个dfs到的点是啥(前者的反数组)dfs序求lca这个很简单,想......
  • lxl分块糊做
    lxl分块糊做[Ynoi2017]由乃打扑克me想到了二分这个值+分块去找\(\leq\)这个数的数的数量,复杂度\(O(Q\log^2N\sqrtN)\),然后块内可能用\(multiset\)或者啥来维护tj更优的做法是块内维护一个排好序的序列,不过硬要说和\(multiset\)本质确实一样,但是这样常数和写法上会优的多C......
  • 从值域分块+莫队到二次离线莫队
    值域分块Q给定一个序列,实现单点修改\(O(1)\),以及区间查询\(O(\sqrtn)\)A考虑设\(block_i\)表示块\(i\)的和,那么修改便是\(O(1)\)全局查询时,整块调用\(block\),散块暴力即可\(O(\sqrtn)\)还有一些常见的例子,比如配合莫队代替主席树(区间mex)莫队二次离线普通莫队......