CFR 707 D. Persistent Bookcase ( Persistent Matrix )

Problem - D - Codeforces
本來以為開頭提的持久化只是唬人的，但最後我還是用了 ( ? )。考慮到總共最多只會改變 Q = 1e5 個行，意味著最多只需紀錄 1e5 * 1e3 個位元。這是 512 MB 能勉強容下的。那麼就用持久化的思想，只有被改變的新創，否則統一指到池裡。這麼一來時間上和空間上都恰好是 1e8 級別的，以 CFR 的優秀系統肯定能壓線過。
一開始用的是 integer 然後正式就爆惹，後來訂正時改用位元壓縮，因為一直以為 bool 會佔滿 1 byte 什麼的，必須要用 integer 搞位元才能使得真正 1 bit，但後來用 bool 記憶體也沒差多少，以前被唬了 ( ? )。
p.s. 前位的人都是寫某種神秘的 DFS，而且 code 超短，有空要理解一下
p.p.s. 後來想揭發 bool 的記憶體真面目，可是很多東西很奇怪，讓我不得不又相信 bool 就是 1 byte，因此留下兩份 code，下面的是位元壓縮。

( 上 bool 下 bit )

嗯.. 持久化才是邪門?

struct pers{
    int cnt;
    vi row_id;
    pers():cnt( 0 ){}
} *root[ 100001 ];

pers* clone( pers *t ){
    pers *res = new pers();
    res->cnt = t->cnt;
    res->row_id = t->row_id;
    return res;
}

pers* add( pers *t, int x, int y ){
    pers *res = clone( t );
    vector< bool > new_row = row[ res->row_id[ x ] ];
    res->row_id[ x ] = row.size();
    row.push_back( new_row );
    if( not row[ res->row_id[ x ] ][ y ] )
        row[ res->row_id[ x ] ][ y ] = 1,
        ++res->cnt;
    return res;
}

pers* rmv( pers *t, int x, int y ){
    pers *res = clone( t );
    vector< bool > new_row = row[ res->row_id[ x ] ];
    res->row_id[ x ] = row.size();
    row.push_back( new_row );
    if( row[ res->row_id[ x ] ][ y ] )
        row[ res->row_id[ x ] ][ y ] = 0,
        --res->cnt;
    return res;
}

pers* invert( pers *t, int x ){
    pers *res = clone( t );
    vector< bool > new_row = row[ res->row_id[ x ] ];
    res->row_id[ x ] = row.size();
    row.push_back( new_row );
    for( int i = 0; i < M; ++i ){
        if( not row[ res->row_id[ x ] ][ i ] )
            row[ res->row_id[ x ] ][ i ] = 1,
            ++res->cnt;
        else
            row[ res->row_id[ x ] ][ i ] = 0,
            --res->cnt;
    }
    return res;
}

void solve(){
    cin >> N >> M >> Q;
    root[ 0 ] = new pers();
    root[ 0 ]->row_id = vi( N );
    row.push_back( vector< bool >( M ) );
    for( int i = 1; i <= Q; ++i ){
        int op; cin >> op;
        if( op == 1 ){
            int x, y; cin >> x >> y;
            --x, --y;
            root[ i ] = add( root[ i - 1 ], x, y );
        } else if( op == 2 ){
            int x, y; cin >> x >> y;
            --x, --y;
            root[ i ] = rmv( root[ i - 1 ], x, y );
        } else if( op == 3 ){
            int x; cin >> x;
            --x;
            root[ i ] = invert( root[ i - 1 ], x );
        } else if( op == 4 ){
            int k; cin >> k;
            root[ i ] = clone( root[ k ] );
        }
        cout << root[ i ]->cnt << "\n";
    }
}

// 位元壓縮
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair< int, int > pii;
typedef pair< int, ll > pil;
typedef pair< ll, int > pli;
typedef pair< ll, ll > pll;
typedef vector< int > vi;
typedef vector< vi > vvi;
typedef vector< ll > vl;
typedef vector< vl > vvl;
typedef vector< double > vd;
typedef vector< vd > vvd;
typedef vector< pii > vp;
typedef vector< vp > vvp;
typedef vector< bool > vb;
typedef vector< vb > vvb;

template< class T1, class T2 >
bool upmin( T1 &x, T2 v ){
    if( x > v ){
        x = v;
        return true;
    }
    return false;
}

template< class T1, class T2 >
bool upmax( T1 &x, T2 v ){
    if( x < v ){
        x = v;
        return true;
    }
    return false;
}

int N, M, Q;

vvi row;

struct pers{
    int cnt;
    vi row_id;
    pers():cnt( 0 ){}
} *root[ 100001 ];

pers* clone( pers *t ){
    pers *res = new pers();
    res->cnt = t->cnt;
    res->row_id = t->row_id;
    return res;
}

pers* add( pers *t, int x, int y ){
    pers *res = clone( t );
    vi new_row = row[ res->row_id[ x ] ];
    int b = y / 32;
    int k = y % 32;
    if( not ( new_row[ b ] & 1 << k ) )
        new_row[ b ] |= 1 << k,
        ++res->cnt;
    res->row_id[ x ] = row.size();
    row.push_back( new_row );
    return res;
}

pers* rmv( pers *t, int x, int y ){
    pers *res = clone( t );
    vi new_row = row[ res->row_id[ x ] ];
    int b = y / 32;
    int k = y % 32;
    if( new_row[ b ] & 1 << k )
        new_row[ b ] ^= 1 << k,
        --res->cnt;
    res->row_id[ x ] = row.size();
    row.push_back( new_row );
    return res;
}

pers* invert( pers *t, int x ){
    pers *res = clone( t );
    vi new_row = row[ res->row_id[ x ] ];
    for( int i = 0; i < new_row.size(); ++i ){
        int u = new_row[ i ];
        int sz = ( i + 1 == new_row.size() and M % 32 ? M % 32 : 32 );
        for( int j = 0, k = 1; j < sz; ++j, k <<= 1 ){
            if( not ( u & k ) )
                u ^= k,
                ++res->cnt;
            else
                u ^= k,
                --res->cnt;
        }
        new_row[ i ] = u;
    }
    res->row_id[ x ] = row.size();
    row.push_back( new_row );
    return res;
}

void solve(){
    cin >> N >> M >> Q;
    root[ 0 ] = new pers();
    root[ 0 ]->row_id = vi( N );
    row.push_back( vi( ( M + 31 ) / 32 ) );
    for( int i = 1; i <= Q; ++i ){
        int op; cin >> op;
        if( op == 1 ){
            int x, y; cin >> x >> y;
            --x, --y;
            root[ i ] = add( root[ i - 1 ], x, y );
        } else if( op == 2 ){
            int x, y; cin >> x >> y;
            --x, --y;
            root[ i ] = rmv( root[ i - 1 ], x, y );
        } else if( op == 3 ){
            int x; cin >> x;
            --x;
            root[ i ] = invert( root[ i - 1 ], x );
        } else if( op == 4 ){
            int k; cin >> k;
            root[ i ] = clone( root[ k ] );
        }
        cout << root[ i ]->cnt << "\n";
    }
}

int main(){
    ios::sync_with_stdio( false );
    solve();
    return 0;
}