浅谈分块

更优体验请移步CSDN

前言

例题思路分析及代码

首先还是分块的基本操作，每个块长度为\(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(n\sqrt{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\n",mx);
		}
	}
	return 0;
}

小结

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

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

祝大家新年快乐！！！