[可持久化線段樹] codeforces 707D. Persistent Bookcase

D. Persistent Bookcase

題意：

一個 n∗m 矩陣 A ，維護4種操作：

• 1 i j：把第A[i][j]指派為1
  • 2 i j：把第 A[i][j] 指派為0
  • 3 i：把 A[i] 的0變1，1變0
  • 4 i：回到第i個操作之後的狀态

  • 資料保證合法。

    每個操作完成後輸出整個矩陣1的個數。

    思路：

    一維的話就可持久化就好啦，二維的話就可持久化套可持久化就好啦。

    對操作3稍加思考的話可以發現可以像其他操作一樣 O(1) 的完成。

    每次都是對整行操作，隻需要打标記就好了，但是我們又不希望破壞複雜度，于是修改一下行線段樹的節點含義，令其總是維護沒有翻轉時的值，這樣操作3就不需要對行線段樹進行任何操作。

    但是操作1和操作2就需要考慮目前翻轉的狀态，如果是已經翻轉，那麼根據上面說的維護沒有翻轉時候的值，操作1就變成指派0，算上翻轉後實際狀态就變成1了，操作2類似。

    空間有點多，于是動态開點。

    注意到這題不要求線上，那麼其實離線也可以做，方法就是按時間線對操作建樹dfs一遍，每次回到k會使k的時間線分裂（一切都是命運石之門的選擇），其實還是棵樹。

    #include<bits/stdc++.h>
    using namespace std;
    const int Q = +;
    int n, m, q;
    struct nodeX{
        int v;
        nodeX *ls, *rs;
        nodeX(){ ls = rs = this; v = ; }
        nodeX(nodeX *pre){ ls = pre->ls, rs = pre->rs, v = pre->v; }
    }*NULLX = new nodeX;
    void updateX(nodeX* &rt, nodeX* pre, int l, int r, int pos, int val){
        rt = new nodeX(pre);
        if(l == r){
            rt->v = val;
            return;
        }
        int mid = (l+r) >> ;
        if(pos <= mid) updateX(rt->ls, pre->ls, l, mid, pos, val);
        else updateX(rt->rs, pre->rs, mid+, r, pos, val);
        rt->v = rt->ls->v + rt->rs->v;
    }
    struct nodeY{
        int v, rev;
        nodeY *ls, *rs;
        nodeX *Xrt;
        nodeY(){ ls = rs = this; Xrt = NULLX; v = rev = ; }
        nodeY(nodeY *pre){ ls = pre->ls, rs = pre->rs, Xrt = pre->Xrt; v = pre->v, rev = pre->rev; }
    }*NULLY = new nodeY;
    nodeY *rt[Q];
    void updateY(nodeY* &rt, nodeY* pre, int l, int r, int pos1, int pos2, int op){
        rt = new nodeY(pre);
        if(l == r){
            if(op <= ) updateX(rt->Xrt, pre->Xrt, , m, pos2, (op == )^rt->rev);
            if(op == ) rt->rev^= ;
            rt->v = rt->rev? m- rt->Xrt->v : rt->Xrt->v;
            return;
        }
        int mid = (l+r) >> ;
        if(pos1 <= mid) updateY(rt->ls, pre->ls, l, mid, pos1, pos2, op);
        else updateY(rt->rs, pre->rs, mid+, r, pos1, pos2, op);
        rt->v = rt->ls->v + rt->rs->v;
    }
    int main(){
        ios::sync_with_stdio(); cin.tie();
        rt[] = new nodeY();
        cin >> n >> m >> q;
        for(int i = ; i <= q; ++i){
            int t, x, y;
            cin >> t >> x;
            if(t <= ){
                cin >> y;
                updateY(rt[i], rt[i-], , n, x, y, t);
            }
            else if(t == ){
                updateY(rt[i], rt[i-], , n, x, , t);
            }
            else if(t == ){
                rt[i] = new nodeY(rt[x]);
            }
            cout << rt[i]->v << '\n';
        }
    }