UAPC 2011 G, AOJ-1068: School of Killifish

問題概要

H*W(H*W<10^6)の配列が与えられるのでRMQのクエリQ(<10^4)個に答える。

答え

二次元RMQのライブラリ確認用にちょろっと投げるつもりだったけど、メモリ制約が非常に厳しく(普通にsegment treeでRMQを実装したら微妙に足りない)想定解法以外を許さない強い意志が感じられた。でも自分がやりたいのはライブラリの確認なので、Javaに書き直して言語補正で通した。
さすがにsparse tableはlog^2が大きすぎて論外。この問題はクエリ数が小さいのでビルドの早いRMQを選ばないといけない(segment treeか平方分割か、のはちょっと現実的じゃないし書けない)。

通したかったコード(MLEする)

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

const int INF = 0x7fffffff;

int W, H, WW, HH, seg_H, seg_W;
vector< vector<int> > data;
vector< vector<int> > seg_tree;

void initialize_W(int y, int cur_node, int lx, int rx){
	if(rx - lx <= 1){
		if(y < H && lx < W){
			seg_tree[y + HH - 1][cur_node] = data[y][lx];
		}
		return ;
	}

	const int mid = (lx + rx) / 2;

	initialize_W(y, 2*cur_node + 1, lx, mid);
	initialize_W(y, 2*cur_node + 2, mid, rx);

	seg_tree[y + HH - 1][cur_node] = min(seg_tree[y + HH - 1][2*cur_node + 1], seg_tree[y + HH - 1][2*cur_node + 2]);
}

int query_W(int node_y, int fx, int tx, int cur_node, int lx, int rx){
	if( rx <= fx || tx <= lx ){
		return INF;
	}

	if( fx <= lx && rx <= tx ){
		return seg_tree[node_y][cur_node];
	}

	const int mid = (lx + rx) / 2;
	return min(query_W(node_y, fx, tx, cur_node*2 + 1, lx, mid),
			query_W(node_y, fx, tx, cur_node*2 + 2, mid, rx));
}

void initialize_H(int cur_node, int ly, int ry){
	if(ry - ly <= 1){
		initialize_W(ly, 0, 0, WW);
		return ;
	}

	const int mid = (ly + ry) / 2;

	initialize_H(2*cur_node + 1, ly, mid);
	initialize_H(2*cur_node + 2, mid, ry);

	for(int j=0; j<seg_W; j++){
		seg_tree[cur_node][j] = min(seg_tree[2*cur_node + 1][j], seg_tree[2*cur_node + 2][j]);
	}
}

int query_H(int fy, int ty, int fx, int tx, int cur_node, int ly, int ry){
	if( ry <= fy || ty <= ly ){
		return INF;
	}

	if( fy <= ly && ry <= ty ){
		return query_W(cur_node, fx, tx, 0, 0, WW);
	}

	const int mid = (ly + ry) / 2;
	return min(query_H(fy, ty, fx, tx, cur_node*2 + 1, ly, mid),
			query_H(fy, ty, fx, tx, cur_node*2 + 2, mid, ry));
}

// [y1, y2) * [x1, x2)
int query_segtree(int y1, int x1, int y2, int x2){
	return query_H(y1, y2, x1, x2, 0, 0, HH);
}

void build_segtree(){
	const int log_H = H == 1 ? 0 : 31 - __builtin_clz(H-1), log_W = W == 1 ? 0 :31 - __builtin_clz(W-1);
	HH = 1<<(log_H+1);
	WW = 1<<(log_W+1);
	seg_H = 2*HH - 1;
	seg_W = 2*WW - 1;

	seg_tree.clear();
	seg_tree = vector< vector<int> >(seg_H, vector<int>(seg_W, INF));

	initialize_H(0, 0, HH);
}

int main(){
	int Q;
	while(scanf("%d%d%d",&H,&W,&Q), H){
		const int log_H = 31 - __builtin_clz(H), log_W = 31 - __builtin_clz(W);
		data.clear();
		seg_tree.clear();

		data = vector< vector<int> >(H, vector<int>(W));

		for(int i=0; i<H; i++){
			for(int j=0; j<W; j++){
				scanf("%d", &data[i][j]);
			}
		}

		build_segtree();

		for(int i=0; i<Q; i++){
			int y1, x1, y2, x2;
			scanf("%d%d%d%d",&y1, &x1, &y2, &x2);
			printf("%d\n", query_segtree(y1, x1, y2+1, x2+1) );
		}
	}
	return 0;
}