BOJ 1999 - 최대최소

BOJ 1999 - 최대최소

그냥 나이브하게 $O(n^3)$ 으로 가로부분에 대해서만 $B$ 길이의 가로로 최대값과 최소값을 각 칸에 대해서 모두 전처리해둔다.

그럼 정답은 $O(nk)$ 에 해결할 수 있다.

int mx[251][251], mn[251][251];
void solve() {
   int n, B, k;
   cin >> n >> B >> k;
   vvi b(n, vi(n));
   fv2(b);
   for (int y = 0; y < n; y++) {
      for (int x = 0; x + B - 1 < n; x++) {
         debug(y, x);
         mx[y][x] = mn[y][x] = b[y][x];
         for (int r = x + 1; r < x + B; r++) {
            mina(mn[y][x], b[y][r]);
            maxa(mx[y][x], b[y][r]);
         }
      }
   }
   debug(mx[0][2]);
   while (k--) {
      int sy, sx;
      cin >> sy >> sx, sy--, sx--;

      int mx1 = 0, mn1 = 1e9;
      for (int y = sy; y < sy + B; y++) {
         maxa(mx1, mx[y][sx]);
         mina(mn1, mn[y][sx]);
      }
      cout << mx1 - mn1 << endl;
   }
}