UVA 11297 Census ( 2D Segment Tree Single Point Modify )

UVa Online Judge
之前的寫法是錯的

每一個二維結構存的應該是一個 x軸的線段樹，每一個節點保有該二維的上下界範圍內所有 y的 min / max。但我之前只是隨便更新而已，變成只要O( lg n )，但如果同個節點被修改兩次就會發生問題，因為包含自己的二維結構不會被通知哪個值消失了，仍然有可能繼續保有消失的節點的資料。因此，我們必須要每次都對於修改的那個列，根據子二維結構修改後的結果，再做額外的 O( lg n )查詢更新。因此複雜度才是正確的 O( lg ^ 2 n )。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500 + 5;
const int MAXQ = 4e4 + 4;
const int INF = 0x3f3f3f3f;

struct itvt{
    int minv, maxv;
    int lb, rb;
    itvt *lc, *rc;
    itvt(int _l = -1, int _r = -1): minv( INF ), maxv( -INF ){
        lb = _l, rb = _r;
        lc = rc = NULL;
    }
    void pull(){
        minv = min<int>( lc->minv, rc->minv );
        maxv = max<int>( lc->maxv, rc->maxv );
    }
    void upmin(int k, int v){
        if( lb == rb ){
            minv = v; // min<int>( minv, v );
            return;
        }
        int mid = lb + rb >> 1;
        if( k <= mid ) lc->upmin( k, v );
        else rc->upmin( k, v );
        pull();
    }
    void upmax(int k, int v){
        if( lb == rb ){
            maxv = v; // max<int>( maxv, v );
            return;
        }
        int mid = lb + rb >> 1;
        if( k <= mid ) lc->upmax( k, v );
        else rc->upmax( k, v );
        pull();
    }
    int qmax(int ql, int qr){
        if( qr < lb || rb < ql ) return -INF;
        if( ql <= lb && rb <= qr ) return maxv;
        return max<int>( lc->qmax( ql, qr ), rc->qmax( ql, qr ) );
    }
    int qmin(int ql, int qr){
        if( qr < lb || rb < ql ) return INF;
        if( ql <= lb && rb <= qr ) return minv;
        return min<int>( lc->qmin( ql, qr ), rc->qmin( ql, qr ) );
    }
};

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;
    itvt *xt;
    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;
        xt = buildItvt( lb, rb );
        uc = dc = NULL;
    }
    void update(int row, int col, int v){
        if( ub == db ){
            xt->upmin( col, v );
            xt->upmax( col, v );
            return;
        }
        int mid = ub + db >> 1;
        if( row <= mid ) uc->update( row, col, v );
        else dc->update( row, col, v );
        xt->upmin( col, min( uc->qmin( uc->ub, uc->db, col, col ),
                             dc->qmin( dc->ub, dc->db, col, col ) ) );
        xt->upmax( col, max( uc->qmax( uc->ub, uc->db, col, col ), 
                             dc->qmax( dc->ub, dc->db, col, col ) ) );
    }
    int qmin(int qu, int qd, int ql, int qr){
        if( qd < ub || db < qu ) return INF;
        if( qu <= ub && db <= qd ) return xt->qmin( ql, qr );
        return min<int>( uc->qmin( qu, qd, ql, qr ),
                         dc->qmin( qu, qd, ql, qr ) );
    }
    int qmax(int qu, int qd, int ql, int qr){
        if( qd < ub || db < qu ) return -INF;
        if( qu <= ub && db <= qd ) return xt->qmax( ql, qr );
        return max<int>( uc->qmax( qu, qd, ql, qr ),
                         dc->qmax( qu, qd, ql, qr ) );
    }
};

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

int main(){
    scanf("%d", &n);
    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 );
        }
    int q; scanf("%d", &q);
    while( q-- ){
        char op[ 3 ]; scanf("%s", op);
        if( op[ 0 ] == 'q' ){
            int x1, y1, x2, y2; scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            int maxv = root->qmax( x1, x2, y1, y2 );
            int minv = root->qmin( x1, x2, y1, y2 );
            printf("%d %d\n", maxv, minv);
        } else{
            int x, y, v; scanf("%d%d%d", &x, &y, &v);
            root->update( x, y, v );
        }
    }
    return 0;
}