1999번: 최대최소

https://www.acmicpc.net/problem/1999

$O(n^2+k)$

n항의 수열이 존재할 때 monotonous queue를 이용해서 연속된 b개 마다의 최댓값, 최솟값을 구할 수 있다.

1. 주어진 행렬에서 각 행마다 연속된 b개의 최댓값, 최솟값을 구한다.
2. 이 값들로 다시 행렬을 만들어 각 열마다 연속된 b개의 최댓값, 최솟값을 구한다.
마지막 값들로 행렬을 다시 만들어 보면 b*b 마다의 최댓값, 최솟값이 구해져 있다.

#include<cstdio>
#include<deque>
using namespace std;
int n, b, k, maxi[251][251], mini[251][251];
void f(deque<pair<int, int> > &dq, int x, int y) {
    while (!dq.empty() && dq.back().second < y) dq.pop_back();
    dq.push_back({ x,y });
    if (x - dq.front().first >= b) dq.pop_front();
}
int main() {
    scanf("%d%d%d", &n, &b, &k);
    for (int i = 1; i <= n; i++) {
        deque<pair<int, int> > dq1, dq2;
        for (int j = 1, x; j <= n; j++) {
            scanf("%d", &x);
            f(dq1, j, x);
            f(dq2, j, -x);
            if (j >= b) {
                maxi[i][j - b + 1] = dq1.front().second;
                mini[i][j - b + 1] = -dq2.front().second;
            }
        }
    }
    for (int i = 1; i <= n - b + 1; i++) {
        deque<pair<int, int> > dq1, dq2;
        for (int j = 1; j <= n; j++) {
            f(dq1, j, maxi[j][i]);
            f(dq2, j, -mini[j][i]);
            if (j >= b) {
                maxi[j - b + 1][i] = dq1.front().second;
                mini[j - b + 1][i] = -dq2.front().second;
            }
        }
    }
    for (int x, y; k--;) {
        scanf("%d%d", &x, &y);
        printf("%d\n", maxi[x][y] - mini[x][y]);
    }
    return 0;
}