蓝桥杯-子矩阵

"""
题目来源
https://www.lanqiao.cn/problems/3521/learning/?page=1&first_category_id=1&name=%E5%AD%90%E7%9F%A9%E9%98%B5
"""
import os
import sys
from collections import deque

# 请在此输入您的代码
n, m, a, b = map(int, input().split())
datas = []
for i in range(n):
  datas.append(list(map(int, input().split())))

# 记录所有子矩阵区间最大值
def max_value_queue(x):
  # 记录每一行所有区间长度为b的区间最大值
  ws = []
  for i in range(n):
    nums = datas[i]
    # w记录当前行所有区间长度为b的区间最大值
    w = []
    # 单调队列
    q = deque()
    for i, v in enumerate(nums):
      # 1.入队列
      while q and v >= nums[q[-1]]:
          q.pop()
      q.append(i)
      # 2.出队列
      # 单调队列的长度限制为b, 当队列元素个数大于b就需要将队首元素出队
      if i - q[0] + 1 >= b + 1:
          q.popleft()
      # 3.开始记录答案
      if i >= b - 1:
          # 单调队列降序, 队首元素为区间最大值
          w.append(nums[q[0]])
    ws.append(w)

  # 记录所有二维区间长度为a宽度为b的区间最大值
  ans = []
  
  # 将ws中的每一列作为一行
  tmps = [[ws[j][i] for j in range(n)] for i in range(len(ws[0]))]
  for i in range(len(ws[0])):
    nums = tmps[i]
    # w记录当前行所有区间长度为a的区间最大值
    w = []
    # 单调队列
    q = deque()
    for i, v in enumerate(nums):
      # 1.入队列
      while q and v >= nums[q[-1]]:
          q.pop()
      q.append(i)
      # 2.出队列
      # 单调队列的长度限制为a, 当队列元素个数大于a就需要将队首元素出队
      if i - q[0] + 1 >= a + 1:
          q.popleft()
      # 3.开始记录答案
      if i >= a - 1:
          # 单调队列降序, 队首元素为区间最大值
          w.append(nums[q[0]])
    ans.append(w)
  return ans

# 记录所有矩阵最小值
def min_value_queue(x):
  # 记录每一行所有区间长度为b的区间最小值
  ws = []
  for i in range(n):
    nums = datas[i]
    # w记录当前行所有区间长度为b的区间最小值
    w = []
    # 单调队列
    q = deque()
    for i, v in enumerate(nums):
      # 1.入队列
      while q and v <= nums[q[-1]]:
          q.pop()
      q.append(i)
      # 2.出队列
      # 单调队列的长度限制为b, 当队列元素个数大于b就需要将队首元素出队
      if i - q[0] + 1 >= b + 1:
          q.popleft()
      # 3.开始记录答案
      if i >= b - 1:
          # 单调队列降序, 队首元素为区间最小值
          w.append(nums[q[0]])
    ws.append(w)

  # 记录所有二维区间长度为a宽度为b的区间最小值
  ans = []
  
  # 将ws中的每一列作为一行
  tmps = [[ws[j][i] for j in range(n)] for i in range(len(ws[0]))]
  for i in range(len(ws[0])):
    nums = tmps[i]
    # w记录当前行所有区间长度为a的区间最小值
    w = []
    # 单调队列
    q = deque()
    for i, v in enumerate(nums):
      # 1.入队列
      while q and v <= nums[q[-1]]:
          q.pop()
      q.append(i)
      # 2.出队列
      # 单调队列的长度限制为a, 当队列元素个数大于a就需要将队首元素出队
      if i - q[0] + 1 >= a + 1:
          q.popleft()
      # 3.开始记录答案
      if i >= a - 1:
          # 单调队列降序, 队首元素为区间最小值
          w.append(nums[q[0]])
    ans.append(w)
  return ans
maxs = max_value_queue(datas)
mins = min_value_queue(datas)

answer = 0
for i in range(len(maxs)):
  for j in range(len(maxs[0])):
    answer = (answer + maxs[i][j] * mins[i][j]) % 998244353
print(answer)

解题思路:

这个就是二维单调队列的使用, 一维单调队列求区间最值比较简单, 可以去做一下滑动窗口最大值:

https://leetcode.cn/problems/sliding-window-maximum/, 那么二维区间最值怎么求呢？

首先从横向来看，可以用单调队列将每一行的区间最值求出来, 用数组w记录当前行的所有区间最值, 用ws将每一行的w都存储一起。接下来再来纵看，取已经求得的ws二维数组其中一列，求纵向的区间最值, 用t记录当前列的区间最值, 用ts记录每一列的t。最后ts就存储了所有的子矩阵的区间最值。

将区间最大值和区间最小值相乘求和求模就是最终答案, 代码看起来很长, 其实功能比较相似, 两个函数都是求区间最值, 一个是最大一个是最小。