AOJ 1068 School of Killifish ( STILL MLE 2D Segment Tree )

School of Killifish | Aizu Online Judge
二次元セグメント木をやるだけ、だと聞きました。でも当たり前にMLEしました。O( n * ( lg ^ 2 ) n ) で n ≤ 1e6。諦めますが、初めての二次元セグメント木で、色々勉強になったので一応MLEしたコードでも載せます。普通のやり方はとにかく長方形をメインテインします、二次元目では上と下を決めたら左から右へとのセグメント木で葉ノードごとにその列の最小値 / 最大値を保存するだけです。操作は全て O( ( lg ^ 2 ) n ) になります。ただ、こういう問題はメモリを注意する事が多いです。

// MLE
#include <bits/stdc++.h>
using namespace std;
const int MAXRC = 1e6 + 6;
const int MAXQ = 1e4 + 4;
const int INF = ~( 1 << 31 );

int r, c, q;

struct itvt{
    int minv;
    int lb, rb;
    itvt *lc, *rc;
    itvt(int _l = 0, int _r = 0): minv(INF), lb(_l), rb(_r), lc(NULL), rc(NULL){}
    ~itvt(){ delete lc; delete rc; }
    void pull(){
        minv = min<int>( lc->minv, rc->minv );
    }
    void update(int k, int v){
        if( lb == rb ){
            minv = min<int>( minv, 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;
    }
};

itvt* buildItvt(int lb, int rb){
    itvt *t = new 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{
    int ub, db, lb, rb;
    itvt2 *uc, *dc;
    itvt *t;
    itvt2(int _u = 0, int _d = 0, int _l = 0, int _r = 0){
        ub = _u, db = _d, lb = _l, rb = _r;
        uc = NULL, dc = NULL;
        t = buildItvt( lb, rb );
    }
    ~itvt2(){ delete uc; delete dc; delete t; }
    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;
    }
};

itvt2* buildItvt2(int ub, int db, int lb, int rb){
    itvt2 *t = new 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(){
    while( scanf("%d%d%d", &r, &c, &q) == 3 && r + c + q ){
        itvt2 *root = buildItvt2( 0, r - 1, 0, c - 1 );
        for(int i = 0; i < r; ++i)
            for(int j = 0; j < c; ++j){
                int v; scanf("%d", &v);
                root->update( i, j, v );
            }
        for(int i = 0; i < q; ++i){
            int r1, c1, r2, c2; scanf("%d%d%d%d", &r1, &c1, &r2, &c2);
            printf("%d\n", root->qmin( r1, r2, c1, c2 ));
        }
        delete root;
    }
    return 0;
}