E. OpenStreetMap (2D monotone queue)

Codeforces Round #574 (Div. 2)

Problem

Given a size of $n\times m$ Matrix h, Find all sizes as $a\times b$ In the submatrix of Sum of minimum values .

Solution

Answer key
Find out h in , The length in all rows is b The minimum value in the sliding window of , Store its results in f Array
Find out f in , The length in all columns is a The minimum value in the sliding window of , The result is that all sizes are $a\times b$ The minimum value in the submatrix of
Time complexity $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];

	// Find the length of all lines is b The minimum value in the window of 
	for (int i = 1; i <= n; i++)
	{
    
		// The operation array is 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()];
		}
	}
	// Find the length of all columns is a The minimum value in the window of （ In essence a * b The minimum value of the matrix ）
	for (int j = 1; j <= m; j++)
	{
    
		// The operation array is 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];// Here is the optimization space , So just use h Come and save 
		}
	}

	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;
}