分块——优雅的暴力

前言:

  首先,我们来考虑这样一个模型:有一段连续的序列a[1]~a[n],然后现在我们需要执行几类操作:

出题人:  求出其中一段区间的和

智商180的某宝宝:哎呀,你怎么这么傻,直接记录这个序列的前缀和不就得了?

分块——优雅的暴力

  记录a[1]~a[i]的和为sum[i],然后显然有sum[i+1]=sum[i]+a[i+1],我们要求a[l]~a[r]就直接sum[r]-sum[l-1]呗。

出题人:区间加上某个值

由于某宝宝是大佬,两分钟后:我会一种叫线段树的东西(一种树形结构,可以维护区间求和和单点修改的优秀数据结构)!!!

分块——优雅的暴力

出题人:查询一段区间上有多少个数<k (k>0且给定)    

某宝宝:分块——优雅的暴力

出题人:对了,忘了告诉你了,k每次都不一样,还有,极其的多。另外,为了防止装*不让写平衡树(另一种能干很多事情的优秀数据结构)+线段树,占用空间不能超过****Mb

某宝宝:分块——优雅的暴力


下面就分享一个菜鸟也能懂得算法:分块

分块,顾名思义,就是把一段序列分成一小块一小块得来处理,维护。

我们把一段当成一个整体,只记录维护整体的有关信息,就是分块。

首先,对于前言说得那道题,很朴素的做法就是:

  1.从询问区间的l到r扫过去,每回加上扫到的值,即$ans=\sum^{r}_{i=l} a[i]$ 

  2.直接把$a[i]$重新赋值不就得了 a[i]=newa[i];

  3.从询问区间的l到r扫过去,每回遇到<k的位置,答案+1

分块——优雅的暴力

没错,这种做法很傻是不是?

但是,分块就是在这个基础上暴力优化的!!!

假设我们总共的序列长度为n,然后我们把它切成$\sqrt{n}$块,然后把每一块里的东西当成一个整体来看,

现在解释几个本文用到的术语:

完整块:被操作区间完全覆盖的块

不完整块:操作区间不完全覆盖的块

然后我们先看看怎么得出答案:

  1.对于完整的块,我们希望有个东西能直接找出这整个块的和,于是每个块要维护这个块的所有元素的和。   

    .对于不完整块,因为元素比较少(最多有  总数n /  块数 = $\sqrt{n}$ 个) 这时候当n=1000000的时候最多有1000个,对比一下,我们可以直接暴力扫这个小块统计答案,

    .小技巧:如果这个不完整块被覆盖的长度>块维护的长度的一半,何不用这个块的和-没有被覆盖的元素的值呢?

  2.这里,我们换种思路,记录一个lazy   标记(为什么用lazy,因为我很懒),表示整个块被加上过多少了,

    .对于完整块,我们直接lazy+=加上的数x,块内的和ans+=x*元素个数(因为每个元素都被加上了x)

    .对于不完整块,直接暴力修改就好了,顺便可以把lazy标记清了。

  3.哎呀,这个有点难度啊,

    .要在每个完整块内寻找小于一个值的元素数,

     显然我们不得不要求块内元素是有序的,这样就能用二分(快速在一个有序的序列里查询的一个算法),对块内查询。

    .不完整的块暴力就好

    .这样的话需要提前对每块里面的元素做一遍排序就好.

    .但是当有修改的话,因为整个块同时加上(减去)一个数,每个数的相对大小是不会变的,但是如果是不完全块就会改变,这样的话,还是因为元素个数小,重新新排一下不就得了?


然后,这道题就用了一种看似高大上的方法做完了……比之前傻傻的暴力是不是好看很多呢?

分块——优雅的暴力

在很多地方,我们可以运用到分块的思想,化零为整,把维护每个数的值变成维护一些整体的值,

一个很常见的例子就是:为什么班主任要给班里分组?因为他可不想收作业或者回执的时候一个一个收啊qwq交给组长然后组长在交给老师多好啊qwq

这样,我们就不用一个一个的找了qwq

分块——优雅的暴力

然后就讲完基础了。

稍稍进阶:

其实,每一块可以维护的不止上面说的那几种东西,我们可以维护当前区间最大公约数是多少,最大异或和是多少……

客观的来说,分块是可以维护很多的,只要想出来怎么预处理,对于有修改的模型怎么维护,统计答案的时候怎么累加就行。

希望对大家有所帮助。

上一篇:poj2891:Strange Way to Express Integers


下一篇:浅谈 cxx rope