POJ 2019 Cornfields ( 2D Segment Tree )

2019 -- Cornfields
ふぁぁ、初めての二次元セグメント木AC。楽しかったです。でも僕はポインタの書き方にしかなれないから、メモリを静態に宣告しなければTLEしてしまいます。でもMAXMEMをちゃんと十分( RE )で多すぎない( MLE ) ように工夫するのは難しいですOrz。とにかく通りました、やった。
あと、これはsparse table の二次元バージョンでO( n ^ 2 ( lg ^ 2 ) n ) / O( 1 )やってもいいようです。( それこそ想定解の模様(?) ) 時間があれば追加します。

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 250 + 5;
const int MAXQ = 1e5 + 5;
const int INF = 0x3f3f3f3f;

const int MAXMEM = 1e6; // suffice

int n, b, q;

struct itvt{
    static itvt mem[ MAXMEM ];
    int minv, maxv;
    int lb, rb;
    itvt *lc, *rc;
    itvt(int _l = -1, int _r = -1): minv(INF), maxv(0), lb(_l), rb(_r), lc(NULL), rc(NULL){}
    void pull(){
        minv = min<int>( lc->minv, rc->minv );
        maxv = max<int>( lc->maxv, rc->maxv );
    }
    void update(int k, int v){
        if( lb == rb ){
            minv = min<int>( minv, v );
            maxv = max<int>( maxv, v );
            return;
        }
        int mid = lb + rb >> 1;
        if( k <= mid ) lc->update( k, v );
        else rc->update( k, v );
        pull();
    }
    int qmin(int ql, int qr){
        if( qr < lb || rb < ql ) return INF;
        if( ql <= lb && rb <= qr ) return minv;
        int res = INF;
        res = min<int>( res, lc->qmin( ql, qr ) );
        res = min<int>( res, rc->qmin( ql, qr ) );
        return res;
    }
    int qmax(int ql, int qr){
        if( qr < lb || rb < ql ) return 0;
        if( ql <= lb && rb <= qr ) return maxv;
        int res = 0;
        res = max<int>( res, lc->qmax( ql, qr ) );
        res = max<int>( res, rc->qmax( ql, qr ) );
        return res;
    }
} itvt::mem[ MAXMEM ], *itvt_ptr = itvt::mem;

itvt* buildItvt(int lb, int rb){
    itvt *t = new( itvt_ptr++ ) itvt( lb, rb );
    if( lb == rb ) return t;
    int mid = lb + rb >> 1;
    t->lc = buildItvt( lb, mid );
    t->rc = buildItvt( mid + 1, rb );
    return t;
}

struct itvt2{
    static itvt2 mem[ MAXMEM ];
    int ub, db, lb, rb;
    itvt *t;
    itvt2 *uc, *dc;
    itvt2(int _u = -1, int _d = -1, int _l = -1, int _r = -1){
        if( _u == -1 ) return;
        ub = _u, db = _d, lb = _l, rb = _r;
        uc = NULL, dc = NULL;
        t = buildItvt( lb, rb );
    }
    void update(int row, int col, int v){
        if( ub == db ){
            t->update( col, v );
            return;
        }
        int mid = ub + db >> 1;
        if( row <= mid ) uc->update( row, col, v );
        else dc->update( row, col, v );
        t->update( col, v );
    }
    int qmin(int qu, int qd, int ql, int qr){
        if( qd < ub || db < qu ) return INF;
        if( qu <= ub && db <= qd ) return t->qmin( ql, qr );
        int res = INF;
        res = min<int>( res, uc->qmin( qu, qd, ql, qr ) );
        res = min<int>( res, dc->qmin( qu, qd, ql, qr ) );
        return res;
    }
    int qmax(int qu, int qd, int ql, int qr){
        if( qd < ub || db < qu ) return 0;
        if( qu <= ub && db <= qd ) return t->qmax( ql, qr );
        int res = 0;
        res = max<int>( res, uc->qmax( qu, qd, ql, qr ) );
        res = max<int>( res, dc->qmax( qu, qd, ql, qr ) );
        return res;
    }
} itvt2::mem[ MAXMEM ], *itvt2_ptr = itvt2::mem;

itvt2* buildItvt2(int ub, int db, int lb, int rb){
    itvt2 *t = new( itvt2_ptr++ ) itvt2( ub, db, lb, rb );
    if( ub == db ) return t;
    int mid = ub + db >> 1;
    t->uc = buildItvt2( ub, mid, lb, rb );
    t->dc = buildItvt2( mid + 1, db, lb, rb );
    return t;
}

int main(){
    scanf("%d%d%d", &n, &b, &q);
    itvt2 *root = buildItvt2( 1, n, 1, n );
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j){
            int v; scanf("%d", &v);
            root->update( i, j, v );
        }
    while( q-- ){
        int r1, r2, c1, c2; scanf("%d%d", &r1, &c1);
        r2 = r1 + b - 1, c2 = c1 + b - 1;
        int minv = root->qmin( r1, r2, c1, c2 );
        int maxv = root->qmax( r1, r2, c1, c2 );
        printf("%d\n", maxv - minv);
    }
    return 0;
}