问题描述

在n * m中选择a * b的矩阵找极值的累计和取模, 对于一维情况可以选择单调队列解决, 现在扩展到二维情况
原理：在一维单调队列的基础进行a行b列的单调队列求解
对于每一行都采用一个单调队列维护该行每一个位置维重点的长度为b的窗口的最值, 
然后再从第b列开始纵向的长度为a的单调队列的数组即可
如对于下面矩阵，求解2 * 3的子矩阵的最小值
1 9 2 4
2 3 1 9
2 4 3 6
4 7 9 2
维护每一行长度为3的单调队列的值变为
1 1 1 2
2 2 1 1
2 2 3 3
4 4 4 2
那么对于该矩阵再从第b列开始以列为数组维护长度为2的单调队列的值变为
1 1 1 2
2 2 1 1
2 2 1 1
4 4 1 1
由此我们发现所需要的数值在原本的n * m矩阵中的从第a行b列开始的右下角的位置, 也就是
1 1
1 1
1 1
这就是所有符合条件的矩阵最小值了
不难发现这里面需要很多次的单调队列的使用可以写一个方法进行调用

/**
     * 滑动窗口
     *
     * @param a   要求解的数组, 从1开始(怎么方便怎么来)
     * @param k   滑动窗口大小
     * @param res 存储结果
     * @param max 是否是最大值
     */
    static void monoQueue(int[] a, int k, int[] res, boolean max) {
        ArrayDeque<Integer> q = new ArrayDeque<>();
        int n = a.length - 1;
        for (int i = 1; i <= n; i++) {
            //检查对头是否超出窗口
            if (!q.isEmpty() && i - q.getFirst() >= k) q.removeFirst();
            //检查单调性
            while (!q.isEmpty() && (max ? a[q.getLast()] <= a[i] : a[q.getLast()] >= a[i])) q.removeLast();
            q.addLast(i);
            //记录窗口最值
            res[i] = a[q.getFirst()];
        }
    }

import java.io.*;
import java.util.*;

public class Main {
    static FastReader sc = new FastReader();
    static PrintWriter out = new PrintWriter(System.out);

    static final int N = 1010, mod = 998244353;
    static int[][] g = new int[N][N], rowMin = new int[N][N], rowMax = new int[N][N];
    static int[] cowMin = new int[N], cowMax = new int[N], resMax = new int[N], resMin = new int[N];
    static int n, m, a, b;

    public static void main(String[] args) {
        n = sc.nextInt();
        m = sc.nextInt();
        a = sc.nextInt();
        b = sc.nextInt();
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                g[i][j] = sc.nextInt();
        for (int i = 1; i <= n; i++) {
            monoQueue(g[i], b, rowMin[i], false);
            monoQueue(g[i], b, rowMax[i], true);
        }

        long ans = 0;
        for (int j = b; j <= m; j++) {
            for (int i = 1; i <= n; i++) {
                cowMax[i] = rowMax[i][j];
                cowMin[i] = rowMin[i][j];
            }
            monoQueue(cowMax, a, resMax, true);
            monoQueue(cowMin, a, resMin, false);
            for (int i = a; i <= n; i++) {
                ans = (ans + (long) resMax[i] * resMin[i]) % mod;
            }
        }
        out.println(ans);
        out.flush();
    }

    static void monoQueue(int[] a, int k, int[] res, boolean max) {
        ArrayDeque<Integer> q = new ArrayDeque<>();
        int n = a.length - 1;
        for (int i = 1; i <= n; i++) {
            if (!q.isEmpty() && i - q.getFirst() >= k) q.removeFirst();
            while (!q.isEmpty() && (max ? a[q.getLast()] <= a[i] : a[q.getLast()] >= a[i])) q.removeLast();
            q.addLast(i);
            res[i] = a[q.getFirst()];//与本题而言是否加判断都可以
        }
    }
}

class FastReader {
    static BufferedReader br;
    static StringTokenizer st;

    public FastReader() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    String next() {
        String str = "";
        while (st == null || !st.hasMoreElements()) {
            try {
                str = br.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
            st = new StringTokenizer(str);
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    double nextDouble() {
        return Double.parseDouble(next());
    }

    long nextLong() {
        return Long.parseLong(next());
    }
}