自动搬运

查看原文

来自洛谷，原作者为

	qwqUwU 「怒りも喜びも哀しさも全部ぶちこめ！」

搬运于2025-08-24 22:37:08，当前版本为作者最后更新于2022-07-28 15:21:09，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

农场 题解报告

题意简述

$n \times m$ 的网格型矩阵，每格有初始权 $a_{i,j}$ 。

给定 $Q$ 个子矩阵，定义一个子矩阵 “盈利” 当且仅当子矩阵内格子的权之和不小于给定值 $b_i$。

给出 $T$ 天，每天发生若干事件形如：

• $a_{x,y} \leftarrow a_{x,y}-z$

对于每个子矩阵，求出一个时间 $t$ ，满足：

• 第 $t$ 天结束时该子矩阵仍然 “盈利”。

• 第 $t+1$ 天结束时该子矩阵不 “盈利”。

• 若第 $T$ 天结束时仍然盈利，则输出 $-1$。

题目分析

先评价一下这道题吧。

这道题是一道可以作为整体二分模板题的好题。

个人认为这题整体二分比较直接好想，不像有些题会涉及到值域等略微复杂的东西。

先来讲一下整体二分是什么。

顾名思义，你可以把它理解成若干次二分一起做。

我们先来想一个子问题：

• $Q=1$

那这道题就有一个很简单的做法：

• 二分第几次事件后开始不 “盈利” ，利用二维树状数组动态维护单点修改与子矩阵查询。

当然，这里要时刻注意哪些事件做了哪些事件没做。

当然不难证明这里的时间复杂度是 $O(\sum p \log n \log m)$ 的。

那么，当 $Q$ 大起来时，有一种直接的想法是跑 $Q$ 次上述操作。

当然这样时间复杂度是 $O(Q \sum p \log n \log m)$ 的，考虑优化。

一般而言，优化一般会往几个方向：

• 减少重复/无用操作。（如本题）

• 提高信息利用率（如 KMP）。

而本题主要旨在减少重复操作。

我们考虑单次操作的时间复杂度瓶颈在哪。

对于每次二分判定，我们都需要来回改变当前当前做到哪个“事件”，以确保能够正确判定。

但消耗如此多的时间只判定一个显得太亏了。

因此我们考虑每次二分都一次性把所有子矩阵分成“仍然盈利”与“不盈利了”两类，然后再分治两边。

这，就是整体二分。

本质上来说，整体二分的本质就是：一次修改，多次判定。

也因此，使用整体二分有以下几个要求：

• 单词询问二分可解。

• 支持离线

• 修改的时间复杂度高，而判定的复杂度低。

关于时间复杂度，你可以把它近似理解成 $Q=1$ 的时间 复杂度。

具体一点是 $O(( \sum p+Q) \log n \log m)$，足矣通过本题。

上代码：

#include<bits/stdc++.h>
#define ll long long
#define lb(x) (x&-x)
#define mid (l+r>>1)
using namespace std;
const int N=510;
const int SUMQ=1e5+10;
const int MAXQ=5e4+10;
const ll INF=1e18;
inline ll read(){
	ll x=0,f=1,c=getchar();
	while(c<'0'||c>'9')f=(c=='-'?-1:1),c=getchar();
	while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
int n,m,Q,T,tot,ans[MAXQ];
struct Field{
	int x1,y1,x2,y2,id;
	ll k;
}q[MAXQ],q1[MAXQ],q2[MAXQ];
struct Rain{
	int x,y,t;
	ll k;
}rain[SUMQ+N*N];
ll t[N][N];
inline void Insert(int x,int y,ll k){
	for(int i=x+1;i<=n+1;i+=lb(i))
		for(int j=y+1;j<=m+1;j+=lb(j))
			t[i][j]+=k;
}
inline ll query(int x,int y,ll A=0){
	for(int i=x+1;i;i-=lb(i))
		for(int j=y+1;j;j-=lb(j))
			A+=t[i][j];
	return A;
}//这里x,y加一是为了防止x=0或y=0的死循环
inline void solve(int L,int R,int l,int r){
	if(L>R){
		for(int i=l;i<=r;i++)Insert(rain[i].x,rain[i].y,rain[i].k);
		return ;
	}
	if(l==r){
		for(int i=L;i<=R;i++)ans[q[i].id]=rain[l].t;
		Insert(rain[l].x,rain[l].y,rain[l].k);
		return;
	}
	for(int i=l;i<=mid;i++)Insert(rain[i].x,rain[i].y,rain[i].k);
	int top1=0,top2=0;
	for(int i=L;i<=R;i++){
		ll res=query(q[i].x2,q[i].y2)-query(q[i].x2,q[i].y1-1)-query(q[i].x1-1,q[i].y2)+query(q[i].x1-1,q[i].y1-1);
		if(res>=q[i].k)q2[++top2]=q[i];
		else q1[++top1]=q[i];
	}
	for(int i=1;i<=top1;i++)q[L+i-1]=q1[i];
	for(int i=1;i<=top2;i++)q[L+top1+i-1]=q2[i];
	for(int i=l;i<=mid;i++)Insert(rain[i].x,rain[i].y,-rain[i].k);
	solve(L,L+top1-1,l,mid);
	solve(L+top1,R,mid+1,r);
}//整个函数还是挺好理解的，一定要注意每个“事件”是否已经被计算了。
int main(){	
	n=read(),m=read();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			Insert(i,j,read());
	Q=read();
	for(int i=1;i<=Q;i++)q[i]={read(),read(),read(),read(),i,read()};
	T=read();
	for(int i=1;i<=T;i++){
		int q=read();
		for(int j=1;j<=q;j++)
			rain[++tot]={read(),read(),i-1,-read()};//这里i-1是因为当天结束还能盈利才会统计哪一天，而ans出来的是哪次事件结束后就“不盈利”了。
	}
	rain[++tot].t=-1;
	solve(1,Q,0,tot);
	for(int i=1;i<=Q;i++)
		printf("%d ",ans[i]);
	return 0;
}

后记：

有不少题解习惯把“修改”和“询问”放在一起进行二分，我觉得那么写有些难以理解，且我这种写法与他们的写法效率相差也小，因此用了这种直白一点的写法。

总而言之，做整体二分的题目还是要多想想我要二分那些东西，$L\sim R$ 与 $l\sim r$ 到底表达的是什么，切忌一味的对着题解码。

本人也算是整体二分的初学者，如有错误欢迎指出。

That's all.Thanks.