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