蓝桥杯2023年第十四届省赛真题-子矩阵-二维滑动窗口+单调队列

先用滑动窗口求行的最大值，再对列求最大值，最后相乘求和取模即可

from collections import deque

def maxWindows(num,size): #求滑动窗口最大值
    n = len(num)
    if n == 0 or size == 0 or size > n :
        return [],[]
    maxqueue = deque()
    maxlist = []
    for i in range(n):
        # 单调队列求最大值
        while maxqueue and num[maxqueue[-1]] < num[i]:
            maxqueue.pop()
        maxqueue.append(i)
        if maxqueue[0] <= i - size :
            maxqueue.popleft()
        if i >= size - 1:
            maxlist.append(num[maxqueue[0]])
    return maxlist

def minWindows(num,size): #求滑动窗口最小值
    n = len(num)
    if n == 0 or size == 0 or size > n :
        return [],[]
    minqueue = deque()
    minlist = []
    for i in range(n): 
        #单调队列求最小值
        while minqueue and num[minqueue[-1]] > num[i]:
            minqueue.pop()
        minqueue.append(i)
        if minqueue[0] <= i - size :
            minqueue.popleft()
        if i >= size - 1:
            minlist.append(num[minqueue[0]])
    return minlist

def main():
    n, m, a, b = map(int, input().split())
    mod = 998244353
    nums = []
    for i in range(n):
        nums.append(list(map(int,input().split())))
    
    maxhang = []
    minhang = []
    # 先按行求二维窗口最大值、最小值
    for i in range(n):
        x = maxWindows(nums[i],b)
        y = minWindows(nums[i],b)
        maxhang.append(x)
        minhang.append(y)
    #print(maxhang)
    #print(minhang)
    
    trans_max = [[maxhang[j][i] for j in range(len(maxhang))] for i in range(len(maxhang[0]))]
    trans_min = [[minhang[j][i] for j in range(len(minhang))] for i in range(len(minhang[0]))]
    
    maxlie = []
    minlie = []
    # 按列求二维窗口最大值、最小值
    for i in range(len(trans_max)):
        x = maxWindows(trans_max[i],a)
        y = minWindows(trans_min[i],a)
        maxlie.append(x)
        minlie.append(y)
    #print(maxlie)
    #print(minlie)
    
    ans = 0
    for i in range(len(maxlie)):
        for j in range(len(maxlie[0])):
            ans += (maxlie[i][j] * minlie[i][j]) % mod
            ans %= mod
    print(ans)
    
if __name__ == '__main__':
    main()