学步园

对K矩阵枚举右下角，对所有可能的所取位置，标注在其k矩阵大小的范围内标志出最小值。

在某个区间范围内的最大值或者最小值都可以用单调队列维护。对于此题，先按列做一次标志，完了以后再在标志过后的新矩阵上按行再做一次标志，这样就可以得到二维上的最小值矩阵了

#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
using namespace std;
#define MAXN 1010
#define INF 0x7f7f7f7f

int P[MAXN][MAXN], S[MAXN][MAXN];
int Q[MAXN][MAXN], K[MAXN][MAXN];
int SK[MAXN][MAXN], SSK[MAXN][MAXN];
int deq[MAXN];
int n, m, a, b, c, d;
int h, t;

int main()
{
//    freopen("912.in", "r", stdin);

    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d%d%d%d%d", &n, &m, &a, &b, &c, &d);
        for(int i = 1; i <= n; i++)
        {
            scanf("%d", &P[i][1]);
            for(int j = 2; j <= m; j++)
                P[i][j] = (P[i][j - 1] * 71 + 17) % 100 + 1;
        }

        memset(K, 0x3f, sizeof(K));
        memset(SK, 0x3f, sizeof(SK));
        memset(SSK, 0x3f, sizeof(SSK));

        for(int i = 0; i <= n; i++)
            S[i][0] = S[0][i] = 0;
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
                S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] + P[i][j];

        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
                if((i >= c) && (j >= d))
                    K[i][j] = S[i][j] - S[i - c][j] - S[i][j - d] + S[i - c][j - d];

        for(int i = 1; i <= n; i++)
        {
            h = t = 0;
            for(int j = 1; j <= m; j++)
            {
                while((h < t) && K[i][deq[t - 1]] >= K[i][j])
                    t--;
                deq[t++] = j;
                if(j >= (b - d - 1))
                {
                    SK[i][j] = K[i][deq[h]];
                    while((h < t) && deq[h] <= (j - (b - d - 1) + 1))
                        h++;
                }
            }
        }

        for(int j = 1; j <= m; j++)
        {
            h = t = 0;
            for(int i = 1; i <= n; i++)
            {

                while((h < t) && SK[deq[t - 1]][j] >= SK[i][j])
                    t--;
                deq[t++] = i;
                if(i >= (a - c - 1))
                {
                    SSK[i][j] = SK[deq[h]][j];
                    while((h < t) && deq[h] <= (i - (a - c - 1) + 1))
                        h++;
                }
            }
        }

        int ans = 0;
        for(int i = a; i <= n; i++)
            for(int j = b; j <= m; j++)
                ans = max(ans, S[i][j] - S[i - a][j] - S[i][j-b] + S[i - a][j - b] - SSK[i - 1][j - 1]);

        printf("%d\n", ans);
    }
    return 0;
}