E. OpenStreetMap（二维单调队列）

Codeforces Round #574 (Div. 2)

Problem

给定一个大小为 $n\times m$ 的矩阵h， 求出所有大小为 $a\times b$ 的子矩阵中最小值的和。

Solution

题解
求出h中，所有行中长度为b的滑动窗口中的最小值，将其结果存入f数组
求出f中， 所有列中长度为a的滑动窗口中的最小值，其结果即为所有大小为 $a\times b$ 的子矩阵中的最小值
时间复杂度 $O(nm)$

Code

int h[3003][3003], g[3003 * 3003];
int f[3003][3003];

int main()
{
    
	IOS;
	int n, m, a, b; cin >> n >> m >> a >> b;
	int x, y, z; cin >> g[0] >> x >> y >> z;
	for (int i = 1; i <= n * m; i++)
		g[i] = ((ll)g[i - 1] * x + y) % z;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			h[i][j] = g[(i - 1) * m + j - 1];

	//求出所有行中的长度为b的窗口中的最小值
	for (int i = 1; i <= n; i++)
	{
    
		//操作数组为h
		deque <int> q;
		for (int j = 1; j <= m; j++)
		{
    
			if (!q.empty() && q.back() - q.front() + 1 >= b) q.pop_front();
			while (!q.empty() && h[i][q.back()] >= h[i][j]) q.pop_back();
			q.push_back(j);
			f[i][j] = h[i][q.front()];
		}
	}
	//求出所有列中的长度为a的窗口中的最小值（实质为a * b的矩阵的最小值）
	for (int j = 1; j <= m; j++)
	{
    
		//操作数组为f
		deque<int> q;
		for (int i = 1; i <= n; i++)
		{
    
			if (!q.empty() && q.back() - q.front() + 1 >= a) q.pop_front();
			while (!q.empty() && f[q.back()][j] >= f[i][j]) q.pop_back();//
			q.push_back(i);
			h[i][j] = f[q.front()][j];//此处为优化空间，所以直接用h来存
		}
	}

	ll ans = 0;
	for (int i = a; i <= n; i++)
		for (int j = b; j <= m; j++)
			ans += h[i][j];
	cout << ans << endl;

	return 0;
}