POJ 2019 Cornfields

問題
http://poj.org/problem?id=2019

解法
segment tree の二次元版みたいなやつを作ると各クエリに対してO(log N)で処理できる

#include <cstdio>
#include <algorithm>
using namespace std;
typedef pair<int, int> P;
const int N_ = 256;
const int TREE_SIZE = 87381; // A_1 = 0,  A_n = 4 * A_{n-1},  n=9,  sum An
int N, B, K;
int a[N_][N_];
int tree_min[TREE_SIZE];
int tree_max[TREE_SIZE];
int min_n(int a, int b){
	if(a < 0 && b < 0) return -1;
	if(a < 0) return b;
	if(b < 0) return a;
	return min(a, b);
}
int k;
void make(int t, int l, int r, int b){
	if(t + 1 == b){
		tree_min[TREE_SIZE - N_ * N_ + k] = a[t][l];
		tree_max[TREE_SIZE - N_ * N_ + k] = a[t][l];
		k++;
		return;
	}
	make(t, l, (l+r)/2, (t+b)/2);
	make(t, (l+r)/2, r, (t+b)/2);
	make((t+b)/2, l, (l+r)/2, b);
	make((t+b)/2, (l+r)/2, r, b);
}
void init(){
	int p = TREE_SIZE - N_ * N_;
	fill(tree_min, tree_min + TREE_SIZE, -1);
	fill(tree_max, tree_max + TREE_SIZE, -1);
	make(0, 0, N_, N_);
	for(p = TREE_SIZE - N_ * N_ - 1; p >= 0; p--){
		tree_min[p] = -1;
		tree_max[p] = -1;
		for(int i = 1; i <= 4; i++){
			tree_min[p] = min_n(tree_min[p], tree_min[4*p+i]);
			tree_max[p] =   max(tree_max[p], tree_max[4*p+i]);
		}
	}
}
P query(int qt, int ql, int qr, int qb, int p, int t, int l, int r, int b){
	if(b <= qt || r <= ql || qr <= l || qb <= t) return P(-1,-1);
	if(qt <= t && ql <= l && qr >= r && qb >= b) return P(tree_min[p], tree_max[p]);
	P p1 = query(qt, ql, qr, qb, 4*p+1, t, l, (l+r)/2, (t+b)/2);
	P p2 = query(qt, ql, qr, qb, 4*p+2, t, (l+r)/2, r, (t+b)/2);
	P p3 = query(qt, ql, qr, qb, 4*p+3, (t+b)/2, l, (l+r)/2, b);
	P p4 = query(qt, ql, qr, qb, 4*p+4, (t+b)/2, (l+r)/2, r, b);
	return P(min_n(min_n(p1.first,  p2.first ), min_n(p3.first,  p4.first)),
		   max(  max(p1.second, p2.second),  max(p3.second, p4.second)));
}
int main(){
	scanf("%d %d %d", &N, &B, &K);
	for(int i = 0; i < N_; i++) for(int j = 0; j < N_; j++) a[i][j] = -1;
	for(int i = 0; i < N; i++)
		for(int j = 0; j < N; j++)
			scanf("%d", &a[i][j]);
	init();
	for(int i = 0; i < K; i++){
		int t, l;
		scanf("%d %d", &t, &l);
		t--; l--;
		P p = query(t, l, l+B, t+B, 0, 0, 0, N_, N_);
		printf("%d\n", p.second - p.first);
	}
	return 0;
}