AOJ 1068 - School of Killifish

問題 : めだかの学校

解答 :

長い MLE との戦いに勝ちました... こういう Memory Allocation が肝である問題はメモリの割当を自分で書くのが大事だなあと再認識.

問題は2-D での RMQ です.

むかしからやろうやろうと思っていた 2-D RMQ を書きました. といってもやることは1-D RMQ をy 座標についてやりながら, それぞれの深さでx 座標で 1-D RMQ をするというシンプルなもの.
$O(\log H)$ 個の地点で $O(\log W)$ 個の更新を行うので $O(\log W \log H)$ で1 更新, クエリも同じ感じなので総じて $O( (Q + WH)\log W \log H)$ 時間でこの問題が解けます.
昔は$O(Q\min(W, H) \log\max(W, H))$ みたいなもので解いていたので, この手法でもきちんと解けてよかった.

コード :

#include <bits/stdc++.h>
 
using namespace std;

int pool[9000000]; //9 MB
int header;

int *assign(int block)
{
	int *ret = &pool[header];
	header += block;
	return (ret);
}

vector<int *> seg;
int wbin, hbin;
 
void update(int y, int x, int v)
{
    y += hbin - 1;
    x += wbin - 1;
     
    seg[y][x] = v;
     
    while (y >= 0){
        int _x = x;
        while (_x){
            _x = (_x - 1) / 2;
            seg[y][_x] = min(seg[y][_x * 2 + 1], seg[y][_x * 2 + 2]);
        }
        if (y == 0) break;
        y = (y - 1) / 2;
        seg[y][x] = min(seg[y * 2 + 1][x], seg[y * 2 + 2][x]);
    }
}
 
int r1, c1, r2, c2, G;
 
int _query(int k = 0, int l = 0, int r = wbin)
{
    if (c2 <= l || r <= c1) return (INT_MAX);
    if (c1 <= l && r <= c2) return (seg[G][k]);
     
    int lval = _query(k * 2 + 1, l, (l + r) / 2);
    int rval = _query(k * 2 + 2, (l + r) / 2, r);
     
    return (min(lval, rval));
}
 
int query(int k = 0, int l = 0, int r = hbin)
{
    if (r2 <= l || r <= r1) return (INT_MAX);
    if (r1 <= l && r <= r2){
        G = k;
        return (_query());
    }
     
    int lval = query(k * 2 + 1, l, (l + r) / 2);
    int rval = query(k * 2 + 2, (l + r) / 2, r);
     
    return (min(lval, rval));
}
 
int main()
{
    int w, h, q;
     
    while (scanf("%d %d %d", &h, &w, &q) && w){
        wbin = hbin = 1;
        while (wbin < w) wbin *= 2;
        while (hbin < h) hbin *= 2;
		
		header = 0;
        seg.resize(hbin * 2 - 1);
        for (int i = 0; i < seg.size(); i++) seg[i] = assign(wbin * 2 - 1);
        
        for (int i = 0; i < h; i++){
            for (int j = 0; j < w; j++){
                int a;
                scanf("%d", &a);
                update(i, j, a);
            }
        }
        
        for (int i = 0; i < q; i++){
            scanf("%d %d %d %d", &r1, &c1, &r2, &c2);
            ++r2; ++c2;
            printf("%d\n", query());
        }
    }
    
    return (0);
}