自动搬运

查看原文

来自洛谷，原作者为

	Tritium 四十三年，望中猶記，烽火揚州路。

搬运于2025-08-24 22:12:38，当前版本为作者最后更新于2019-12-16 11:03:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

为数不多的二维分块的题目。（我做题太少了QwQ）

本题二维分块的做法就是对行和列分别一维分块，然后将一维数组改为二维数组即可维护二维分块。基本上是裸的。

上一篇题解关于二维分块的讲解复杂度可能有一些问题。这里再分析一波：

++++++++ ++
++++++++ ++
         ++
++ ..... ++
++ ..... ++
++ ..... ++
++ 
++ ++++++++
++ ++++++++

首先点代表中间整块，+代表零散块。我们是这样维护边角料中间块的对吧？

设块的大小为$S$,边长为$N$.那么中间的整块的个数为$O((\frac{N}{S})^2)$个。

周围四个长条,长为$O(N)$,宽为$O(S)$,所以维护边角料长条时间复杂度$O(NS)$.

除去预处理,总复杂度$O(Q(NS+(\frac{N}{S})^2))$.

对于复杂度来说,我们只关心最大的那一项.而在$S>0$的时候,$NS$是一个增函数,$(\frac{N}{S})^2$是一个减函数.所以会有一个$s_0$使得两者相等,并且$s_0$无论变小还是变大,其值$max\{ NS,(\frac{N}{S})^2\}$都会变大.

所以,当$NS=(\frac{N}{S})^2$时,复杂度最小.此时$S=N^{\frac{1}{3}}$.

总复杂度$O(N^{\frac{4}{3}})$.$\because N=1000,\therefore \text{运算量}\to10^7$.可过.

#include <cstdio>
#include <cmath>
const int S=1003;
int n,m,q,a[S][S],bl[S],add[200][200],_=0,nn,mx[200][200],fr[S],ed[S];
long long s[200][200],f[S][S];
inline void read(int &s)
{
	s=0;char t=1,c=getchar();
	while (c!='-' && (c<'0' || c>'9')) c=getchar();
	if (c=='-') c=getchar(),t=-1;
	while (c>='0' && c<='9') s=(s<<1)+(s<<3)+(c^48),c=getchar();
	s*=t;
}
inline long long ma(long long a,long long b){return a>b?a:b;}
inline void mma(int &a,int b){a=a>b?a:b;}
inline void modify(int u,int x,int y,int xx,int yy)
{
	if (bl[x]==bl[xx] || bl[y]==bl[yy] )
	{
		for (int i=x;i<=xx;++i)
			for (int j=y;j<=yy;++j)
			{
				a[i][j]+=u;
				s[bl[i]][bl[j]]+=u;
				mma(mx[bl[i]][bl[j]],a[i][j]);
			}
		return;
	}
	for (int i=bl[x]+1;i<bl[xx];++i)
		for (int j=bl[y]+1;j<bl[yy];++j)
			add[i][j]+=u;
	for (int i=ed[bl[x]];i>=x;--i)
		for (int j=fr[bl[yy]]-1;j>=y;--j)
		{
			a[i][j]+=u;
			s[bl[i]][bl[j]]+=u;
			mma(mx[bl[i]][bl[j]],a[i][j]);
		}
	for (int i=fr[bl[xx]];i<=xx;++i)
		for (int j=ed[bl[y]]+1;j<=yy;++j)
		{
			a[i][j]+=u;
			s[bl[i]][bl[j]]+=u;
			mma(mx[bl[i]][bl[j]],a[i][j]);
		}
	for (int i=ed[bl[x]]+1;i<=xx;++i)
		for (int j=ed[bl[y]];j>=y;--j)
		{
			a[i][j]+=u;
			s[bl[i]][bl[j]]+=u;
			mma(mx[bl[i]][bl[j]],a[i][j]);
		}
	for (int i=fr[bl[xx]]-1;i>=x;--i)
		for (int j=fr[bl[yy]];j<=yy;++j)
		{
			a[i][j]+=u;
			s[bl[i]][bl[j]]+=u;
			mma(mx[bl[i]][bl[j]],a[i][j]);
		}
}
inline int calmx(int x,int y,int xx,int yy)
{
	int s=0;
	if (bl[x]==bl[xx] || bl[y]==bl[yy] )
	{
		for (int i=x;i<=xx;++i)
			for (int j=y;j<=yy;++j)
				mma(s,a[i][j]+add[bl[i]][bl[j]]);
		return s;
	}
	for (int i=bl[x]+1;i<bl[xx];++i)
		for (int j=bl[y]+1;j<bl[yy];++j)
			mma(s,mx[i][j]+add[i][j]);
	for (int i=ed[bl[x]];i>=x;--i)
		for (int j=fr[bl[yy]]-1;j>=y;--j)
			mma(s,a[i][j]+add[bl[i]][bl[j]]);
	for (int i=fr[bl[xx]];i<=xx;++i)
		for (int j=ed[bl[y]]+1;j<=yy;++j)
			mma(s,a[i][j]+add[bl[i]][bl[j]]);
	for (int i=ed[bl[x]]+1;i<=xx;++i)
		for (int j=ed[bl[y]];j>=y;--j)
			mma(s,a[i][j]+add[bl[i]][bl[j]]);
	for (int i=fr[bl[xx]]-1;i>=x;--i)
		for (int j=fr[bl[yy]];j<=yy;++j)
			mma(s,a[i][j]+add[bl[i]][bl[j]]);
	return s;
}
inline long long cals(int x,int y,int xx,int yy)
{
	long long su=0;
	if (bl[x]==bl[xx] || bl[y]==bl[yy] )
	{
		for (int i=x;i<=xx;++i)
			for (int j=y;j<=yy;++j)
				su+=a[i][j]+add[bl[i]][bl[j]];
		return su;
	}
	for (int i=bl[x]+1;i<bl[xx];++i)
		for (int j=bl[y]+1;j<bl[yy];++j)
			su+=s[i][j]+1ll*(ed[i]-fr[i]+1)*(ed[j]-fr[j]+1)*add[i][j];
	for (int i=ed[bl[x]];i>=x;--i)
		for (int j=fr[bl[yy]]-1;j>=y;--j)
			su+=a[i][j]+add[bl[i]][bl[j]];
	for (int i=fr[bl[xx]];i<=xx;++i)
		for (int j=ed[bl[y]]+1;j<=yy;++j)
			su+=a[i][j]+add[bl[i]][bl[j]];
	for (int i=ed[bl[x]]+1;i<=xx;++i)
		for (int j=ed[bl[y]];j>=y;--j)
			su+=a[i][j]+add[bl[i]][bl[j]];
	for (int i=fr[bl[xx]]-1;i>=x;--i)
		for (int j=fr[bl[yy]];j<=yy;++j)
			su+=a[i][j]+add[bl[i]][bl[j]];
	return su;
}
int main()
{
	read(n);read(m);read(q);
	nn=pow(n,1.0/3.0);
	if (nn<1) nn=1;
	for (int i=1;i<=n;++i)
		bl[i]=(i-1)/nn+1;
	for (int i=1;i<=n;++i)
	{
		if (bl[i]!=bl[i-1])
			fr[bl[i]]=i;
		if (bl[i]!=bl[i+1])
			ed[bl[i]]=i;
	}
	int u,x,y,xx,yy;
	while (q--)
	{
		read(u);read(x);read(y);read(xx);read(yy);
		if (u>0)
		{
			++_;
			modify(u,x,y,xx,yy);
			if (_==m)
			{
				for (int i=1;i<=n;++i)
					for (int j=1;j<=n;++j)
						f[i][j]=ma(f[i-1][j],f[i][j-1])+add[bl[i]][bl[j]]+a[i][j];
			}
		}
		else if (!u)
			printf("%d\n",calmx(x,y,xx,yy));
		else
			printf("%lld\n",cals(x,y,xx,yy));
	}
	printf("%lld\n",f[n][n]);
	return 0;
}