分块学习笔记

小 SX 是个大垃圾和大鸽子，所以 19 年 12 月份学的拖到了 1 月写学习笔记（）

Part -1 引子

我们不难发现，树状数组的时间复杂度是 (O(log_2 n)) 的，但是它能干的东西真的好少好少/kk
线段树也是 (O(log_2 n)) 的，虽然它可以支持所有满足结合律的问题，尽管它的常数大了不少。
但是——

求 ([l,r]) 这个区间内有多少个小于 (k) 的数。

这个线段树怎么做！/baojin
于是，分块横空出世，以 (O(sqrt{n})) 的时间复杂度和基本完全可以维护所有 RMQ 问题的以及超好写的代码拯救了 RMQ！（误

Part 1 分块是啥？好吃吗？能吃吗？

~~分块能吃，还很好吃~~
分块是一种十分无比特别暴力的鬼畜数据结构，我们要把一个数列分割成若干个块，然后对于每个块近似暴力一样乱搞维护。
在学习分块之前。首先你要了解几个基本的名词：

名称	代码名字	定义
块长	(len)	每一个块的长度，通常是 (O(sqrt{n}))
不完整块		一个不完整的块（这不等于没说吗）
完整块		一个完整的块（还是没说）

值得一提的是，尽管有的时候 (n) 无法整除 (len)，也就是说有一个块的长度不是 (len)，但是为了方便起见，我们依旧把这个块当成完整块。
那么分块怎么维护呢？
大概都是一下几个步骤：

(l) 和 (r) 在一个区间吗？如果在，就暴力维护。
如果不在那就：
1. 暴力维护左半边的不完整块。
2. 对于完整快进行打标记等奇妙方法。
3. 暴力维护右半边的不完整块。

蛤？真么暴力！
没错，就这么暴力！
让我们在具体的题目中感受分块的优美吧~

Part 2.1 例题精讲——数列分块入门 1

简单点来说，这道题是区间修改和单点查询。
单点查询不难，这题的重点是区间修改。
我们都会线段树，我们都知道线段树有个 (lazy)，大大减少了线段树的时间复杂度。
(lazy) 是区间内我们要加的值。
那分块就可以仿照线段树的 (lazy)，作为这个完整块的值啊/cy
所以：

暴力维护左半边的不完整块。
对于完整块，我们将 (lazy_i) 加上 (v)。
暴力维护右半边的不完整块。

就这么暴力！就这么豪横！.jpg
提醒一句，单点查询的时候要加上这个 (lazy) 哦。

思路讲完了，下面讲一些关于分块写法的事情。
由于笔者是看着 OI-wiki 上的，所以用的是 OI-wiki 的码风。写分块的码风又很多，仅供参考

首先列一张表：

名称	含义	计算
(cl)	当前元素属于哪个块	((len-1)div i+1)
(kl)	块的左指针	((i-1) imes len+1)
(kr)	块的右指针	(i imes len)

这是维护他们的代码：

len=sqrt(n);
for(int p=1;p<=ceil(n*1.0/len);p++)
	kl[p]=(p-1)*len+1,kr[p]=p*len; 
for(int p=1;p<=n;p++)
{
	cin>>a[p];
	cl[p]=(p-1)/len+1;
}

很多分块（不是所有）可以用如下的方法来写，根本不需要多废口舌解释，以注释的形式出现。

int cll=cl[l],clr=cl[r];//获取 l 和 r 所在的块
if(cl[l]==cl[r])//在一个块，暴 力 维 护
{
	for(int p=l;p<=r;p++)
		……
	return ;
}
for(int p=l;p<=kr[cll];p++)……//左半边不完整块，暴 力 维 护
for(int p=cll+1;p<=clr-1;p++)……//完整块，通过玄学操作维护
for(int p=kl[clr];p<=r;p++)……//右半边不完整块，暴 力 维 护

那这题的两种操作也就不难写出来了：

void updata(int l,int r,int c)
{
	int cll=cl[l],clr=cl[r];
	if(cl[l]==cl[r])
	{
		for(int p=l;p<=r;p++)
			a[p]+=c;
		return ;
	}
	for(int p=l;p<=kr[cll];p++)a[p]+=c;
	for(int p=cll+1;p<=clr-1;p++)lazy[p]+=c;
	for(int p=kl[clr];p<=r;p++)a[p]+=c;
}
int ask(int A)
{
	if(lazy[cl[A]])return a[A]+lazy[cl[A]];
	else return a[A];
}

Part 2.2 例题精讲——数列分块入门 2

这是一道很有趣的题目。
我们要找小于 (c^2) 的数量，对于完整块显然可以采用二分达到 (log_2 n) 的复杂度。但如果要二分，就要排序。
但是原数组也是需要的，因为还有不完整块，需要用原数组来暴力，所以我们需要开两个数组：(a)（原数组）和 (cp)（排序数组）
每次修改，我们先在原数组上修改，然后复制到 (cp) 上，在 (cp) 上进行排序。

void updata(int l,int r,int c)
{
	int cll=cl[l],clr=cl[r];
	if(cl[l]==cl[r])
	{
		for(int p=l;p<=r;p++)
			a[p]+=c;
		for(int p=kl[cll];p<=kr[cll];p++)
			cp[p]=a[p];
		sort(cp+kl[cll],cp+kr[cll]+1);
		return ;
	}
	for(int p=l;p<=kr[cll];p++)a[p]+=c;//暴 力 修 改
	for(int p=kl[cll];p<=kr[cll];p++)cp[p]=a[p];//整块复制
	sort(cp+kl[cll],cp+kr[cll]+1);//整块排序
	for(int p=cll+1;p<=clr-1;p++)lazy[p]+=c;//整块修改，因为在全部都加上 c 后，大小关系不变，无需排序
	for(int p=kl[clr];p<=r;p++)a[p]+=c;//暴 力 修 改
	for(int p=kl[clr];p<=kr[clr];p++)cp[p]=a[p];//整块复制
	sort(cp+kl[clr],cp+kr[clr]+1);//整块排序
}

查找很类似。如果不完整，就用原数组暴力，如果完整就用复制数组二分。

int ask(int l,int r,int c)
{
	int cll=cl[l],clr=cl[r];
	int cnt=0;
	if(cll==clr)
	{
		for(int p=l;p<=r;p++)
			if(a[p]+lazy[cll]<c)cnt++;
		return cnt;
	}
	for(int p=l;p<=kr[cll];p++)
		if(a[p]+lazy[cll]<c)cnt++;
	for(int p=cll+1;p<=clr-1;p++)
		cnt+=lower_bound(cp+kl[p],cp+kr[p]+1,c-lazy[p])-(cp+kl[p]);
	for(int p=kl[clr];p<=r;p++)
		if(a[p]+lazy[clr]<c)cnt++;
	return cnt;
}

Part 2.3 数列分块入门 5

这道题很有意思很有意思。
乍一看这道题是道不可做题，因为开根号需要每个数字都知道。
但是我们都知道，开根号会迅速缩小一个数。
连 (2^{31}-1) 也仅仅需要五次根号就能缩小到 1！
我们都知道，当一个数的到了 (1) 或 (0)，无论怎么开根号都是 (1) 或 (0)。
那么如果这样，我们就可以对完整块进行一个标记，标记是否全是 (1) 或 (0)，如果是，就忽略开根号操作。

还有一个查询操作，我们该怎么办呢？
像修改操作一样，我们维护块和 (sum)，每次修改在 (sum) 上同步操作，然后查询完整块就直接用 (sum)。
然后这道题就迎刃而解啦~

void opt0(int l,int r)
{
	int cll=cl[l],clr=cl[r];
	if(cll==clr)
	{
		for(int p=l;p<=r;p++)
		{
			sum[cll]-=a[p];//这就是将 sum 变成新的 a[i] 和
			a[p]=sqrt(a[p]);
			sum[cll]+=a[p];
		}
		return ;
	}
	for(int p=l;p<=kr[cll];p++)
	{
		sum[cll]-=a[p];
		a[p]=sqrt(a[p]);
		sum[cll]+=a[p];
	}
	if(cll!=clr)
		for(int p=cll+1;p<=clr-1;p++)
		{
			if(vis[p])continue;
			vis[p]=1,sum[p]=0;//vis[p]=1 表示成立。因为是整块操作，sum[p]=0 更方便
			for(int i=kl[p];i<=kr[p];i++)
			{
				a[i]=sqrt(a[i]),sum[p]+=a[i];
				if(a[i]>1)vis[p]=0;//有个大于 1 的，就不成立了
			}
		}
	for(int p=kl[clr];p<=r;p++)
	{
		sum[clr]-=a[p];
		a[p]=sqrt(a[p]);
		sum[clr]+=a[p];
	}
}
int opt1(int l,int r)
{
	int cll=cl[l],clr=cl[r];
	if(cll==clr)
	{
		int s=0;
		for(int p=l;p<=r;p++)
			s+=a[p];
		return s;
	}
	int s=0;
	for(int p=l;p<=kr[cll];p++)s+=a[p];
	for(int p=cll+1;p<=clr-1;p++)s+=sum[p];
	for(int p=kl[clr];p<=r;p++)s+=a[p];
	return s;
}

由此可见，维护分块的方法繁多，但是万变不离其宗，总是通过维护整块降低复杂度。这样趋于暴力的写法也就说明了分块的简单容易写的特点和功能强大的特性。
分块真是个好东西_{麻麻再也不用担心我不稀饭写线段树惹}