CF15D-Map题解

题目传送门

题意：有一个 \(n\times m\) 的矩阵，每个格子有一个权值。每次操作会选择一个 \(x\times y\) 的矩形区域，花费为“每个位置的权值减去最小权值”之和，区域之间不能重叠。每次会选择花费最小的区间，如果有重复，则优先选上面的，再优先选左边的。输出每次的区域和花费。

显然选区域不会影响其他区域的花费，只会影响其他区域是否可选。思考可以发现，选择一个左上角为 \((a,b)\) 的区域，会导致左上角在 \((a-x+1\sim a+x-1,b-y+1\sim b+y-1)\) 的所有区域不可选。于是每次操作找到当前能选的最优区域，更改其他区域即可。

具体实现上，要用横竖两遍滑动窗口求出每个区域的最小值，再用二维前缀和求出每个区域的权值和，则该区域的花费为权值和减去 \(x\times y\) 倍最小值。

统计答案时，由于常数要求比较严格，需要预先对所有区域进行从优到劣的排序，每次看一个区域是否可选，如果可选就更新，否则到下一个。

对于判断是否可选，可以使用二维树状数组维护，也可以暴力更新。对于暴力更新的复杂度证明：首先发现选的区域个数不会超过 \(\frac{n\cdot m}{x\cdot y}\)，而每次暴力更新的复杂度为 \(4xy\)，所以更新的总复杂度为 \(4nm\)。

暴力更新 By cxm1024

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read() {
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)) f=(ch=='-'?-1:f),ch=getchar();
	while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	return x*f;
}
int a[1010][1010],s[1010][1010],t[1010][1010],sum[1010][1010];
bool vis[1010][1010];
signed main() {
	int n=read(),m=read(),x=read(),y=read();
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++) {
			a[i][j]=read();
			sum[i][j]=sum[i][j-1]+a[i][j];
		}
		deque<pair<int,int> > q;
		for(int j=0;j<y;j++) {
			while(!q.empty()&&q.back().second>=a[i][j])
				q.pop_back();
			q.push_back({j,a[i][j]});
		}
		for(int j=y;j<=m;j++) {
			if(!q.empty()&&q.front().first==j-y)
				q.pop_front();
			while(!q.empty()&&q.back().second>=a[i][j])
				q.pop_back();
			q.push_back({j,a[i][j]});
			s[i][j-y+1]=q.front().second;
		}
	}
	for(int j=1;j<=m-y+1;j++) {
		deque<pair<int,int> > q;
		for(int i=0;i<x;i++) {
			while(!q.empty()&&q.back().second>=s[i][j])
				q.pop_back();
			q.push_back({i,s[i][j]});
		}
		for(int i=x;i<=n;i++) {
			if(!q.empty()&&q.front().first==i-x)
				q.pop_front();
			while(!q.empty()&&q.back().second>=s[i][j])
				q.pop_back();
			q.push_back({i,s[i][j]});
			t[i-x+1][j]=q.front().second;
		}
	}
	for(int j=1;j<=m;j++)
		for(int i=1;i<=n;i++)
			sum[i][j]+=sum[i-1][j];
	vector<pair<int,pair<int,int> > > v;
	for(int i=1;i<=n-x+1;i++)
		for(int j=1;j<=m-y+1;j++) {
			int res=sum[i+x-1][j+y-1];
			res-=sum[i+x-1][j-1]+sum[i-1][j+y-1];
			res+=sum[i-1][j-1];
			v.push_back({res-t[i][j]*x*y,{i,j}});
		}
	sort(v.begin(),v.end());
	vector<pair<int,pair<int,int> > > ans;
	for(auto [tmp,pos]:v) {
		auto [i,j]=pos;
		if(vis[i][j]) continue;
		ans.push_back({tmp,pos});
		for(int di=-x+1;di<=x-1;di++)
			for(int dj=-y+1;dj<=y-1;dj++)
				if(i+di>0&&j+dj>0) vis[i+di][j+dj]=1;
	}
	printf("%lu\n",ans.size());
	for(auto [tmp,pos]:ans)
		printf("%lld %lld %lld\n",pos.first,pos.second,tmp);
	return 0;
}

二维树状数组 By vepifanov

int n;
int m;
int f[1001][1001];
int ww[1001][1001], w[1001][1001], g[1001][1001];
long long s[1001][1001];
ii st[1001];

vector<pair<long long, pair<int, int> > > all;
vector<pair<pair<int, int>, long long > > res;

int add (int x, int y) {
	for (int p = x; p <= n; p |= (p + 1))
		for (int q = y; q <= m; q |= (q + 1))
			f[p][q]++;
}

int get (int x, int y) {
	int s = 0;
	for (int p = x; p > 0; p = (p & (p + 1)) - 1)
		for (int q = y; q > 0; q = (q & (q + 1)) - 1)
			s += f[p][q];
	return s;
}

int main() {
	int a, b;
	scanf ("%d%d%d%d", &n, &m, &a, &b);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			scanf ("%d", &g[i][j]);
	memset (s, 0, sizeof (s));
	for (int i = n - 1; i >= 0; i--)
		for (int j = m - 1; j >= 0; j--)
			s[i][j] = s[i + 1][j] + s[i][j + 1] - s[i + 1][j + 1] + g[i][j];
	for (int i = 0; i < n; i++) {
		int r = 0, l = 0;
		for (int j = 0; j < m; j++) {
			while (l < r && st[l].second + b <= j) l++;
			while (r > l && st[r - 1].first > g[i][j]) r--;
			st[r++] = make_pair (g[i][j], j);
			if (j - b + 1 >= 0) ww[i][j - b + 1] = st[l].first;
		}
	}

	for (int j = 0; j + b <= m; j++) {
		int r = 0, l = 0;
		for (int i = 0; i < n; i++) {
			while (l < r && st[l].second + a <= i) l++;
			while (r > l && st[r - 1].first > ww[i][j]) r--;
			st[r++] = make_pair (ww[i][j], i);
			if (i - a + 1 >= 0) w[i - a + 1][j] = st[l].first;
		}
	}

	for (int i = 0; i + a <= n; i++)
		for (int j = 0; j + b <= m; j++) {
			long long cur = s[i][j] - s[i + a][j] - s[i][j + b] + s[i + a][j + b];
			cur -= (long long)w[i][j] * a * b;
			all.push_back (make_pair (cur, make_pair (i, j)));
		}
	sort (all.begin (), all.end ());
	for (int i = 0; i < all.size (); i++) {
		long long q = all[i].first;
		int x = all[i].second.first;
		int y = all[i].second.second;
		if (get (x + a, y + b) - get (max (x - a + 1, 0), y + b) - get (x + a, max (y - b + 1, 0)) + get (max (x - a + 1, 0), max (y - b + 1, 0)) == 0) {
			res.push_back (make_pair (make_pair (x, y), q));
			add (x + 1, y + 1);
		}
	}
	printf ("%d\n", res.size ());
	for (int i = 0; i < res.size (); i++)
		printf ("%d %d %I64d\n", res[i].first.first + 1, res[i].first.second + 1, res[i].second);
	return 0;
}