程序地带

浅谈分块


更优体验请移步CSDN


前言

(NOIP)已过,训练难度瞬间变大。很多没有学过的知识点以各种方式出现在题目里。而本蒟蒻的脑子里只有那惨兮兮一点点的算法,于是本蒟蒻就开始走上恶补知识点的道路。


突然想起来很久很久之前有道用分块做的题目,当时听的云里雾里,然后同年级的某位大佬表示:分块很简单。今天又听到同学说起分块,就上OI-WIKI查了一下,没想到很快就理解然后敲题了……


何为分块

分块其实是一种思想,本质上跟暴力差不多,常用于处理区间问题。做法是将区间分成一个个小块,然后暴力维护,时间复杂度和分出来的块的个数及块的大小有关


结合例题讲解分块的具体操作


例题1

LOJ#6280.数列分块入门4


给出一个长为(n)的数列,以及(n)个操作


操作有两种情况,每次操作输入4个数(opt、l、r、c)


若(opt=0),表示将位于([l,r])的之间的数字都加(c)。


若(opt=1),表示询问位于([l,r])的所有数字的和(mod (c+1)) 。


(1le n le50000),保证答案在(long long)范围内


例题思路分析及代码

只要学过线段树,第一秒想到的基本都会是线段树,但是这题有一个很大的不同在于每次求值的时候会模一个非固定的数,那么如果要用线段树来做就需要在建树的时候不取模,求值的时候再取模,这样的话就有可能会导致线段树上的值超过(long long)甚至(unsigned long long)范围((\_\_int128)就不要多想了)


所以我们要抛弃线段树,去寻找另一种解决方案。而分块,就是解决这个问题的一个很好的办法


对于一个区间,我们把它分成若干个长度为(s)的块,最后一个块的长度可以不足(s),因为没有规定(s)必须是(n)的因数


一个区间(a)就可以分成


(underbrace{a_1,a_2ldots,a_s}_{b_1},underbrace{a_{s+1},ldots,a_{2s}}_{b_2},dots,underbrace{a_{(s-1) imes s+1},dots,a_n}_{b_{frac{n}{s}}})


其中(b_i)维护第(i)个块内的和,可以在读入的时候就记录好每个元素是哪个块,同时维护(b)数组


更改

分类讨论一下


如果(l,r)在同一块内,则直接暴力更改,时间复杂度(O(s))


如果不在,就可以分三部分:(1)以(l)开头的一个不完整块;(2)中间若干个完整块;(3)以(r)结尾的一个不完整块。其中(1)(3)部分可以暴力更改,(2)部分就直接更改(b_i),以及(x_i)。其中(x_i)表示整个区间加上了多少,时间复杂度(O(dfrac{n}{s}+s ))


查询

跟更改很像,也是要分类讨论


(l,r)在同一个块内就直接暴力统计,同时注意加上(x)数组,时间复杂度(O(s))


不在同一个块内也是分三部分,分法同更改部分,(1)(3)部分查询也是暴力,跟(l,r)同块一样,注意加上(x)数组。(2)部分直接加上中间完整块的(b)数组,这里就不用加上(x)数组。时间复杂度(O(dfrac{n}{s}+s))


时间复杂度分析

综合更改和查询,一次操作的时间复杂度就是(O(dfrac{n}{s}+s)),显然当(s)是(sqrt{n})的时候是最优的,那么一次操作的时间复杂度就是(O(sqrt{n})),总时间复杂度(O(nsqrt{n}))


Code
#include<cstdio>
#include<cmath>
#define ll long long
using namespace std;
int n,s,opt,l,r,x;
ll ans,a[50005],id[50005],b[50005],c[50005];
int read()
{
int res=0,fh=1;char ch=getchar();
while (ch<"0"||ch>"9") {if (ch=="-") fh=-1;ch=getchar();}
while (ch>="0"&&ch<="9") res=res*10+ch-"0",ch=getchar();
return res*fh;
}
int main()
{
n=read();
s=sqrt(n);
for (int i=1;i<=n;++i)
{
a[i]=read();
id[i]=(i-1)/s+1;
b[id[i]]+=a[i];
}
for (int i=1;i<=n;++i)
{
opt=read();l=read();r=read();x=read();
if (!opt)
{
if (id[l]==id[r])
{
for (int j=l;j<=r;++j)
a[j]+=x,b[id[l]]+=x;
}
else
{
for (int j=l;id[j]==id[l];++j)
a[j]+=x,b[id[l]]+=x;
for (int j=id[l]+1;j<id[r];++j)
c[j]+=x,b[j]+=s*x;
for (int j=r;id[j]==id[r];--j)
a[j]+=x,b[id[r]]+=x;
}
}
else
{
ans=0;
if (id[l]==id[r])
{
for (int j=l;j<=r;++j)
ans=(ans+a[j]+c[id[l]])%(x+1);
}
else
{
for (int j=l;id[j]==id[l];++j)
ans=(ans+a[j]+c[id[l]])%(x+1);
for (int j=id[l]+1;j<id[r];++j)
ans=(ans+b[j])%(x+1);
for (int j=r;id[r]==id[j];--j)
ans=(ans+a[j]+c[id[r]])%(x+1);
}
printf("%lld ",ans);
}
}
return 0;
}
例题2

在(N(1le Nle100000))个数(A_1dots A_n)组成的序列上进行(M(1le Mle100000))次操作,操作有两种:


(1)(1 L R C):表示把(A_L)到(A_R)增加(C)((|C|le10000));


(2)(2 L R):询问(A_L)到(A_R)之间的最大值。


其实这是线段树的模板题,放到这里来是想要体现分块在更改的时候的一个注意事项(其实是为了加字数)


例题思路分析及代码

首先还是分块的基本操作,每个块长度为(s),同时维护每个块内的最大值(b)数组


更改

注意到(C)的取值范围加了绝对值,就说明(C)可能是负数。那么如果修改区间内有最大值,就可能会影响最大值。所以说如果我们不是修改整个块,那么就需要重新统计更改后块的最大值


(l,r)同块的无需多言,直接暴力更改,同时重新维护块的最大值。时间复杂度(O(s))


(l,r)不同块的还是照样分成三部分,头和尾暴力更改,更新最大值,中间的块给整个区间加上(C),同时最大值可以直接加(C)(可以简单推理得到)。时间复杂度(O(dfrac{n}{s}+s))


查询

(l,r)同块直接暴力,记得加上给挂在整个块的值


(l,r)不同块也是分成三部分,中间部分直接与(b_i)进行比较,首尾暴力比较(不要漏掉挂在块上的值)


时间复杂度分析

(s)还是取(sqrt{n})最优,时间复杂度仍然是(O(nsqrt{n}))


Code
#include<cmath>
#include<cstdio>
#include<iostream>
#define ll long long
using namespace std;
int n,m,len,l,r,x,opt;
ll mx,a[100005],id[100005],b[100005],c[100005];
int read()
{
int res=0,fh=1;char ch=getchar();
while (ch<"0"||ch>"9") {if (ch=="-") fh=-1;ch=getchar();}
while (ch>="0"&&ch<="9") res=res*10+ch-"0",ch=getchar();
return res*fh;
}
int main()
{
freopen("max10.in","r",stdin);
freopen("max10.txt","w",stdout);
n=read();
len=sqrt(n);
for (int i=1;i<=n;++i)
{
a[i]=read();
id[i]=(i-1)/len+1;
b[id[i]]=max(b[id[i]],a[i]);
}
m=read();
while (m--)
{
opt=read();
if (opt==1)
{
l=read();r=read();x=read();
if (id[l]==id[r])
{
for (int i=l;i<=r;++i)
a[i]+=x;
b[id[l]]=-2147483647;
for (int i=(id[l]-1)*len+1;id[i]==id[l];++i)
b[id[l]]=max(b[id[i]],a[i]+c[id[i]]);
}
else
{
for (int i=l;id[i]==id[l];++i)
a[i]+=x;
for (int i=id[l]+1;i<id[r];++i)
c[i]+=x,b[i]+=x;
for (int i=r;id[i]==id[r];--i)
a[i]+=x;
b[id[l]]=b[id[r]]=-2147483647;
for (int i=(id[l]-1)*len+1;id[i]==id[l];++i)
b[id[l]]=max(b[id[i]],a[i]+c[id[i]]);
for (int i=(id[r]-1)*len+1;id[i]==id[r];++i)
b[id[r]]=max(b[id[i]],a[i]+c[id[i]]);
}
}
else
{
mx=-2147483647;
l=read();r=read();
if (id[l]==id[r])
{
for (int i=l;i<=r;++i)
mx=max(mx,a[i]+c[id[l]]);
}
else
{
for (int i=l;id[i]==id[l];++i)
mx=max(mx,a[i]+c[id[l]]);
for (int i=id[l]+1;i<id[r];++i)
mx=max(mx,b[i]);
for (int i=r;id[i]==id[r];--i)
mx=max(mx,a[i]+c[id[r]]);
}
printf("%lld ",mx);
}
}
return 0;
}
小结

分块其实是一种十分暴力的思想,旨在把区间分割开来,所以说在分块的时候,一定要合理控制块的大小及个数,并不是所有题目(s)都是取(sqrt{n})最优,要根据问题选择合适的(s)


另外分块也可以做一些奇奇怪怪的毒瘤题,例如吉司机线段树……


祝大家新年快乐!!!


版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://www.cnblogs.com/H-K-H/p/14279536.html

随机推荐

spring cloud 微服务 Feign

Feign介绍(1)Feign的音标美[feɪn]假装,装作,佯装(2)Feign是什么?Feign开源库ÿ...

weixin_46405661 阅读(133)

mysql over rank_mysql 实现查询排行榜

总结下mysql的排行榜查询,mysql8可以使用窗口函数,8以前就不行了。需求大概是一个游戏,用户可以玩多次,排名的时候取最高分排名首先搞点测...

Harvey Janson 阅读(820)

mysql over rank_MySQL分类排名问题

导读对数据库中的记录依据某个字段进行排序是一种常见需求,虽然简单的Orderby可以胜任,但如果想要输出具体的排名却难以直接实现。如果再考虑重复排名或者分类排名࿰...

weixin_39945523 阅读(344)

CSS面试题

CSS1.什么是CSS不是真正的编程语言,是样式表语言,允许有选择性的为HTML稳当的元素添加样式。2.CSS3新增特性颜色:新增RGBA,HS...

来摸鱼啊!!! 阅读(520)

【Java】时间戳不要用==去比较

不要觉得时分秒都一样就没事。这格式可不行:yyyy-MM-ddHH:mm:ss.S。所以你可以先format成yyyy-MM-ddHH:mm:ss再搞。...

winrh 阅读(556)

js异步执行原理

我们都知道js是一个单线程的语言,所以没办法同时执行俩个进程。所以我们就会用到异步。异步的形式有哪些那,es5的回调函数。es6的promis等异步的运行原理我们可以先看下...

青年嫌疑犯 阅读(170)

Hive原理及简单入门

文章目录Hive概述应用场景组件布署Hive和数据仓库比较Hive优点Hive缺点Hive功能架构Hive架构Hive存储分区桶倾斜数据正常数据分区和分桶的区别Hive托管表和外部表Hive基本操作H...

休斯顿凤梨 阅读(923)