属于网站开发的动态服务器/今日关注

4964. 子矩阵 - AcWing题库

from collections import deque

n, m, a, b = map(int, input().split())
mod = 998244353
nums = []
for _ in range(n):
    nums.append(list(map(int, input().split())))

rmin = [[0 for i in range(m)] for i in range(n)]
rmax = [[0 for i in range(m)] for i in range(n)]

def get_max(nums, r, n, k):
    max_q = deque()
    for i in range(n):
        if max_q and max_q[0] == i - k:
            max_q.popleft()
        while max_q and nums[max_q[-1]] <= nums[i]:
            max_q.pop()
        max_q.append(i)
        r[i] = nums[max_q[0]]

def get_min(nums, r, n, k):
    min_x = deque()
    for i in range(n):
        if min_x and min_x[0] == i - k:
            min_x.popleft()
        while min_x and nums[min_x[-1]] >= nums[i]:
            min_x.pop()
        min_x.append(i)
        r[i] = nums[min_x[0]]

# Preprocessing
for i in range(n):
    get_max(nums[i], rmax[i], m, b)
    get_min(nums[i], rmin[i], m, b)

res = 0
A = [0 for i in range(n)]
B = [0 for i in range(n)]
C = [0 for i in range(n)]

for i in range(b - 1, m):
    for j in range(n):
        A[j] = rmax[j][i]
    get_max(A, B, n, a)
    for j in range(n):
        A[j] = rmin[j][i]
    get_min(A, C, n, a)
    for j in range(a - 1, n):
        res = (res + B[j] * C[j]) % mod

print(res)

 AcWing 154. 滑动窗口（算法基础课） - AcWing

from collections import deque  
  
def sliding_window_max_min(nums, k):  
    # 函数返回两个列表，分别包含每个滑动窗口的最大值和最小值  
    max_values = []  
    min_values = []  
      
    # 双端队列，存储元素的索引  
    max_q = deque()  
    min_q = deque()  
      
    for i in range(len(nums)):  
        # 移除队列中超出当前窗口的元素  
        if max_q and max_q[0] == i - k:  
            max_q.popleft()  
        if min_q and min_q[0] == i - k:  
            min_q.popleft()  
          
        # 移除队列中所有小于当前元素的元素，以保持max_q的单调递减  
        while max_q and nums[max_q[-1]] <= nums[i]:  
            max_q.pop()  
        # 移除队列中所有大于当前元素的元素，以保持min_q的单调递增  
        while min_q and nums[min_q[-1]] >= nums[i]:  
            min_q.pop()  
          
        # 将当前元素的索引加入队列  
        max_q.append(i)  
        min_q.append(i)  
          
        # 当窗口大小达到k时，记录最大值和最小值  
        if i >= k - 1:  
            max_values.append(nums[max_q[0]])  
            min_values.append(nums[min_q[0]])  
      
    return max_values, min_values  
  
# 输入部分  
n, k = map(int, input().split())  
nums = list(map(int, input().split()))  
  
# 调用函数并输出结果  
max_values, min_values = sliding_window_max_min(nums, k)  
# 输出每个滑动窗口的最小值  
for val in min_values:  
    print(val, end=" ")  
print()  # 换行
  
# 输出每个滑动窗口的最大值  
for val in max_values:  
    print(val, end=" ")  
print()  # 换行