题目描述

单调队列，求最小值构造单调递增的队列，求最大值构造单调递减的队列

样例

import java.util.*;

public class Main {

    static final int MOD = 998244353;
    static final int N = 1010;

    static int n,m,A,B;

    static int[][] w = new int[N][N];

    static int[][] rmax = new int[N][N];
    static int[][] rmin = new int[N][N];

    static int[] q = new int[N];

    static void get_max(int[] a, int[] b, int tot, int k) {
        //形成一个单调递减的队列
        int hh = 0,tt = -1;
        for (int i = 0; i < tot; i++) {

            //判断队头是否已经滑出窗口
            if (hh <= tt && i - k + 1 > q[hh]) {
               hh++;
            }

            //插入的数比队尾的数还大 队尾的数出队
            while (hh <= tt && a[q[tt]] <= a[i]) {
               //出队
               tt--;
            }
            //队尾插入数据
            q[++tt] = i;

            //当前区间的最大的元素 是队头元素
            b[i] = a[q[hh]];
        }
    }

    static void get_min(int[] a, int[] b, int tot, int k) {
        //形成一个单调递增的队列
        int hh = 0,tt = -1;
        for (int i = 0; i < tot; i++) {

            //判断队头是否已经滑出窗口
            if (hh <= tt && i - k + 1 > q[hh]) {
               hh++;
            }

            //插入的数比队尾的数还小 队尾的数出队
            while (hh <= tt && a[q[tt]] >= a[i]) {
               //出队
               tt--;
            }
            //队尾插入数据
            q[++tt] = i;

            //当前区间的最小的元素是队头元素
            b[i] = a[q[hh]];
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        A = scanner.nextInt();
        B = scanner.nextInt();

        int[][] w = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                w[i][j] = scanner.nextInt();
            }
        }

        for (int i = 0; i < n; i++) {
            get_max(w[i], rmax[i], m, B);
            get_min(w[i], rmin[i], m, B);
        }

        int res = 0;

        int[] a = new int[N];
        int[] b = new int[N];
        int[] c = new int[N];

        //枚举每一列 从0到B-1 刚好有B个元素
        for (int i = B - 1; i < m; i ++) {
            for (int j = 0; j < n; j++) {
                a[j] = rmax[j][i];
            }
            //把最大值放入b数组
            get_max(a, b, n, A);
            for (int j = 0; j < n; j++) {
                a[j] = rmin[j][i];
            }
            //把最小值放入c数组
            get_min(a, c, n, A);
            //枚举每一行 从0到A-1 刚好有A个元素
            for (int j = A - 1; j < n; j ++) {
                res = (int) ((res + (long) b[j] * c[j]) % MOD);
            }
        }

        System.out.println(res);
    }
}