TIOJ 1045 A.細菌培養 ( Ad hoc )

1045 - A.細菌培養 | TIOJ INFOR Online Judge

題意：
給矩形的座標，每次使矩形內的所有數字 * 2，初始時皆為 1，求所有操作後矩形內數字總和。

資料規模：
座標 0 ≤ X, Y ≤ 10000
操作數 1 ≤ Q ≤ 200
時限 1000 ms
保證解 ≤ 8e18

解法：
本來想用 imosu ( 前綴差分和 ) + map 去搞一波，才發現我以前寫過這題，所以就直接拉出來看了。
原來半年前我是單純離散化，一步步算貢獻，而且竟然壓線!!! 時限是 1000 ms，還真跑了 1000 ms 整。

時間 / 空間複雜度：
O( N ^ 3 lg ^ 2 N )

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200 + 2;
const int MAXR = 1e4 + 4;
typedef long long ll;

int n;
int l[ MAXN ], t[ MAXN ], r[ MAXN ], b[ MAXN ];
map< int, int > v_id[ 2 ]; // row, col
vector< int > id_v[ 2 ];

void discretize(){
    for( int i = 0; i < 2; ++i )
        v_id[ i ].clear(),
        id_v[ i ].clear();
    for( int i = 0; i < n; ++i ){
        id_v[ 1 ].push_back( l[ i ] );
        id_v[ 0 ].push_back( t[ i ] );
        id_v[ 1 ].push_back( r[ i ] );
        id_v[ 0 ].push_back( b[ i ] );
    }
    for( int i = 0; i < 2; ++i ){
        id_v[ i ].push_back( 0 );
        id_v[ i ].push_back( 10000 );
        sort( id_v[ i ].begin(), id_v[ i ].end() );
        id_v[ i ].erase( unique( id_v[ i ].begin(), id_v[ i ].end() ), id_v[ i ].end() );
        for( int j = 0; j < id_v[ i ].size(); ++j )
            v_id[ i ][ id_v[ i ][ j ] ] = j;
    }
}

void solve(){
    vector< vector< ll > > G( id_v[ 0 ].size(), vector< ll >( id_v[ 1 ].size() ) );
    for( int i = 0; i < id_v[ 0 ].size(); ++i )
        for( int j = 0; j < id_v[ 1 ].size(); ++j )
            G[ i ][ j ] = 1;
    for( int i = 0; i < n; ++i )
        for( int row = v_id[ 0 ][ t[ i ] ]; row < v_id[ 0 ][ b[ i ] ]; ++row )
            for( int col = v_id[ 1 ][ l[ i ] ]; col < v_id[ 1 ][ r[ i ] ]; ++col )
                G[ row ][ col ] *= 2;
    ll ans = 0;
    for( int row = 0; row < id_v[ 0 ].size() - 1; ++row )
        for( int col = 0; col < id_v[ 1 ].size() - 1; ++col ){
            int hit = id_v[ 0 ][ row + 1 ] - id_v[ 0 ][ row ];
            int wid = id_v[ 1 ][ col + 1 ] - id_v[ 1 ][ col ];
            ans += G[ row ][ col ] * hit * wid;
        }
    cout << ans << "\n";
}

int main(){
    ios::sync_with_stdio( false );
    while( cin >> n && n ){
        for( int i = 0; i < n; ++i )
            cin >> l[ i ] >> t[ i ] >> r[ i ] >> b[ i ];
        discretize();
        solve();
    }
    return 0;
}