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; }