自动搬运

查看原文

来自洛谷，原作者为

	Loser_King Just stay where you are; Let your fear subside

搬运于2025-08-24 22:36:31，当前版本为作者最后更新于2023-07-13 13:18:18，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

能不写成答辩题的题就不要用答辩做法！！1

想起来补了 z 宝模拟赛，JOI22 本选去掉第一题组成提高组模拟赛（

官方题解里有个特别抽象的图，实际上感觉不用那么多 case 啊。

intro：小课题 1 扫过去，找大于小于号连续段。小课题 2 枚举矩形按值排序，观察在值上相邻的格子在原位置上是否相邻。

同样考虑走的路径，发现在走链的路径的过程中，恰好有一个点没有入度，一个点没有出度，其他点都是出度为一，入度为一，这个和官方题解是一样的。

而且在确定了当前矩形边界的情况下，可以发现它只可能走四周比它小的最大格子，这个可以通过小课题 2 的暴力 $O(n^2m^2\log(nm))$ 做法得出。

有了上面两个结论以后，在确定了当前矩形边界的情况下，我们把一个格子 $(i,j)$ 的权 $v_{i,j}$ 定义为：

记 $l$ 表示 $(i,j)$ 四周比 $A_{i,j}$ 小的最大值（没有就记为 $0$），$r$ 为 $(i,j)$ 四周比这个格子权大的最小值（没有就记为 $X$，表示一个充分大的值），那么 $v_{i,j}=\operatorname{R}(r<X,A_{i,j},X)-l$。其中 $\operatorname{R}(P,x,y)$ 表示条件 $P$ 为真时值为 $x$，否则为 $y$。

根据上面的结论，一条合法路径上所有格子的权值和应该是 $X$。（在链上的非端点都抵掉了，链尾剩下个 $0$，链头贡献 $X$）

后面就是转棋盘，枚举上下行的范围，然后扫过去，问题变成了满足左右列之间格子权值和为 $X$ 的对数，这个可以差分后 $O(m\log m)$ 解决。

剩下的部分是枚举长或宽为一的矩阵，这个在小课题 1 里已经解决。

总时间复杂度 $O((nm)^{1.5}\log m)$。

求 $v_{i,j}$ 的时候需要做五次前缀和，枚举左右列的时候根据靠边情况权值需要拆成六部分，别的应该没什么难写的。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int const N=400010,X=500000000000ll,dx[]={0,-1,1,0},dy[]={-1,0,0,1};
int n,m,ans;
vector<vector<int> >a,l,r,u,d,s;
void init(vector<vector<int> >&a){
	a.resize(n+2);
	for(int i=0;i<=n+1;i++)
		a[i].resize(m+2);
}
int calc(int x,int y,int s){
	int l=0,r=X;
	for(int i=0;i<4;i++)
		if(s>>i&1){
			int tx=x+dx[i],ty=y+dy[i];
			if(tx<1||ty<1||tx>n||ty>m)
				continue;
			if(a[tx][ty]>a[x][y])
				r=min(r,a[tx][ty]);
			else l=max(l,a[tx][ty]);
		}
	return(r<X?a[x][y]:X)-l;
}
signed main(){
	ios::sync_with_stdio(0);
	cin>>n>>m,ans=n*m;
	if(n>m){
		swap(n,m),init(a);
		for(int j=1;j<=m;j++)
			for(int i=1;i<=n;i++)
				cin>>a[i][j];
	}else{
		init(a);
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				cin>>a[i][j];
	}
	init(l),init(r),init(u),init(d),init(s);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			l[i][j]=l[i-1][j]+calc(i,j,14),
			r[i][j]=r[i-1][j]+calc(i,j,7),
			u[i][j]=u[i][j-1]+calc(i,j,13),
			d[i][j]=d[i][j-1]+calc(i,j,11),
			s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+calc(i,j,15);
	for(int pl=1;pl<=n;pl++)
		for(int pr=pl+1;pr<=n;pr++){
			map<int,int>f;
			for(int i=1;i<=m;i++){
				ans+=f[X-r[pr-1][i]+r[pl][i]-u[pl][i-1]-d[pr][i-1]-s[pr-1][i-1]+s[pl][i-1]-calc(pl,i,5)-calc(pr,i,3)];
				f[l[pr-1][i]-l[pl][i]-u[pl][i]-d[pr][i]-s[pr-1][i]+s[pl][i]+calc(pl,i,12)+calc(pr,i,10)]++;
			}
		}
	for(int i=1;i<=n;i++)
		for(int t=1,j=2;j<=m;j++)
			if(t++,j==m||(a[i][j]-a[i][j-1])*(a[i][j+1]-a[i][j])<0)
				ans+=t*(t-1)/2,t=1;
	for(int j=1;j<=m;j++)
		for(int t=1,i=2;i<=n;i++)
			if(t++,i==n||(a[i][j]-a[i-1][j])*(a[i+1][j]-a[i][j])<0)
				ans+=t*(t-1)/2,t=1;
	cout<<ans<<"\n";
}