Codeforces 368 div2#D

D.cpp

/* Copyright 20kSize Rafael Rendón Pablo <[email protected]> */
// region Template
#include <bits/stdc++.h>
using namespace std;
typedef long long           int64;
typedef unsigned long long  uint64;
const double kEps   = 10e-8;
const int kMax      = 100005;
const int kInf      = 1 << 30;
const int kSize     = 16;
const int kBitSize  = 64;
const int kSet      = 1;
const int kReset    = 2;
const int kInvert   = 3;
// endregion

const uint64 kBits64 = numeric_limits<uint64>::max();
uint64 globalMask[kSize];

struct Bitset {
    uint64 bits[kSize];
    int size;
    Bitset() {
        size = 0;
        bitCount = 0;
        memset(bits, 0, sizeof bits);
    }

    Bitset(int s) : size(s)  {
        memset(bits, 0, sizeof bits);
    }

    int Count() {
        unsigned int sum = 0;
        for (int i = 0; i < kSize; i++) {
            sum += __builtin_popcount(bits[i] & globalMask[i]);
        }
        return sum;
    }

    void Invert() {
        for (int i = 0; i < kSize; i++) {
            bits[i] = ~bits[i] & globalMask[i];
        }
    }

    void Set(int i) {
        int b = i / kSize;
        int p = i % kBitSize;
        bits[b] |= (1ull << p);
    }

    bool Get(int i) {
        int b = i / kSize;
        int p = i % kBitSize;
        return (bits[b] & (1ull << p)) != 0;
    }

    void Reset(int i) {
        int b = i / kSize;
        int p = i % kBitSize;
        bits[b] = (kBits64 ^ (1ull << p)) & bits[b];
    }

    void Print() {
        printf(">> ");
        for (int i = 0; i < size; i++) {
            printf("%d", Get(i));
        }
        printf("\n");
    }
};

Bitset BitsetNotFound(1);



// region PersistentArray
// Node describes a node in the tree.
struct Node {
    // Array* index.
    int idx;

    // Value stored at index.
    Bitset value;

    // Array* unique indentifier.
    int uid;

    // Reference to left subtree
    Node* left;

    // Reference to right subtree
    Node* right;

    Node() {
        idx = 0;
        value = 0;
        uid = 0;
        left = right = nullptr;
    }

    Node(int i, const Bitset& v, int u) {
        idx = i;
        value = v;
        uid = u;
        left = right = nullptr;
    }
};

// PersistentArray persistent array using balanced binary tree (through
// randomization).
class PersistentArray {
public:
    PersistentArray() {
        root_ = nullptr;
        detached_ = false;
        bit_count_ = 0;
    }

    PersistentArray(unsigned int size, int bitsetSize) {
        size_ = size;
        bit_count_ = 0;
        detached_ = true;
        vector<int> ids(size_ - 1);
        iota(begin(ids), end(ids), 1);

        // Randomize indices to raise the chances of having a balanced tree.
        unsigned seed = chrono::system_clock::now().time_since_epoch().count();
        shuffle(begin(ids), end(ids), default_random_engine(seed));

        // Create entries for all indices
        Bitset bs(bitsetSize);
        root_ = new Node(0, 0, 0);
        for (int id : ids) {
            root_ = create(root_, id, bs, 0);
        }
    }

    // Copy constructor
    PersistentArray(const PersistentArray& other) {
        this->size_ = other.size_;
        this->detached_ = false;
        this->root_ = other.root_;
        this->bit_count_ = other.bit_count_;
    }

    // Asignment operator
    PersistentArray& operator=(const PersistentArray& other) {
        this->size_ = other.size_;
        this->detached_ = false;
        this->root_ = other.root_;
        this->bit_count_ = other.bit_count_;
        return *this;
    }

    // Set sets value at index idx, i.e. A[idx] = value.
    void Set(int idx, int j) {
        int diff = 0;
        root_ = setAndDetach(root_, idx, j, diff, kSet);
        detached_ = true;
        bit_count_ += diff;
    }

    int Reset(int idx, int j) {
        int diff = 0;
        root_ = setAndDetach(root_, idx, j, diff, kReset);
        detached_ = true;
        return diff;
    }

    int Invert(int idx, int j) {
        int diff = 0;
        root_ = setAndDetach(root_, idx, j, diff, kInvert);
        detached_ = true;
        return diff;
    }

    // Get returns the value at index idx, i.e., A[idx].
    Bitset& Get(int idx) {
        return get(root_, idx);
    }


    // clean frees tree, it only deletes those nodes that were created for this
    // tree, i.e., it skips shared nodes.
    void clean(Node* root, int uid) {
        if (root == nullptr) {
            return;
        }

        if (root->left && root->left->uid == uid) {
            clean(root->left, uid);
            delete root->left;
        }

        if (root->right && root->right->uid == uid) {
            clean(root->right, uid);
            delete root->right;
        }
    }

    // Destructor
    ~PersistentArray() {
        if (detached_ && root_) {
            clean(root_, root_->uid);
            delete root_;
        }
    }

private:
    // Array* size
    int size_;

    // Bit count
    int bit_count_;

    // Flag that indicates if we should create a copy of the array*.
    bool detached_;

    // Entry point to the tree.
    Node* root_;

    // create creates entry for index idx, with value 0 and uid.
    Node* create(Node* root, int idx, const Bitset& bs, int uid) {
        if (root == nullptr) {
            return new Node(idx, bs, uid);
        }

        if (idx < root->idx) {
            root->left = create(root->left, idx, bs, uid);
        } else {
            root->right = create(root->right, idx, bs,uid);
        }
        return root;
    }

    // setValue sets value at index idx, i.e. A[idx] = value.
    void setValue(Node* root, int idx, const Bitset& value) {
        if (root == nullptr) {
            return;
        }
        if (idx == root->idx) {
            root->value = value;
            return;
        }

        if (idx < root->idx) {
            setValue(root->left, idx, value);
        } else {
            setValue(root->right, idx, value);
        }
    }

    // setAndDetach sets A[idx] = value and copies the path all the way up to
    // the root so that the original array* remains unchanged.
    Node* setAndDetach(Node* root, int idx, int j, int& diff, int op) {
        if (root == nullptr) {
            return root;
        }
        Node* node = nullptr;
        if (idx == root->idx) {
            Bitset bs = root->value;
            if (op == kSet) {
                if (!bs.Get(j)) {
                    bs.Set(j);
                    diff = 1;
                }
            } else if (op == kReset) {
                if (bs.Get(j)) {
                    diff = -1;
                    bs.Reset(j);
                }

            } else if (op == kInvert) {
                int count = bs.Count();
                bs.Invert();
                diff = bs.Count() - count;
            }
            node = new Node(idx, bs, root->uid + 1);
            node->left = root->left;
            node->right = root->right;
            return node;
        }

        if (idx < root->idx) {
            Node* l = setAndDetach(root->left, idx, j, diff, op);
            if (l != nullptr) {
                node = new Node(root->idx, root->value, l->uid);
                node->left = l;
                node->right = root->right;
            }
        } else {
            Node* r = setAndDetach(root->right, idx, j, diff, op);
            if (r != nullptr) {
                node = new Node(root->idx, root->value, r->uid);
                node->left = root->left;
                node->right = r;
            }
        }
        return node;
    }

    // get returns the value at index idx, i.e., A[idx].
    Bitset& get(Node* root, int idx) {
        // Returns 0 for non-existent indices.
        if (root == nullptr) {
            return BitsetNotFound;
        }

        if (idx == root->idx) {
            return root->value;
        }

        if (idx < root->idx) {
            return get(root->left, idx);
        } else {
            return get(root->right, idx);
        }
    }
};
// endregion

PersistentArray history[kMax];
int historySize[kMax];

void init(int size) {
    int i;
    for (i = 0; i < size / kBitSize; i++) {
        globalMask[i] = numeric_limits<uint64>::max();
    }
    globalMask[i] = (1ull << (size % kBitSize)) - 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, queries;
    cin >> n >> m >> queries;
    init(m);
    PersistentArray pa(n, m);
    history[0] = pa;
    historySize[0] = 0;
    PersistentArray current = pa;
    int pos = 0;
    for (int query = 0; query < queries; query++) {
        int op, i, j, count;
        cin >> op;
        if (op == 1) {
            cin >> i >> j;
            i--;
            j--;
            pos++;
            printf("pos = %d\n", pos);
            //history[pos] = history[pos-1];
            historySize[pos] = historySize[pos-1] + history[pos].Set(i, j);
            count = historySize[pos];
        } else if (op == 2) {
            cin >> i >> j;
            i--;
            j--;
            pos++;
            printf("pos = %d\n", pos);
            history[pos] = history[pos-1];
            historySize[pos] = historySize[pos-1] + history[pos].Reset(i, j);
            count = historySize[pos];
        } else if (op == 3) {
            cin >> i;
            i--;
            pos++;
            printf("pos = %d\n", pos);
            history[pos] = history[pos-1];
            historySize[pos] = historySize[pos-1] + history[pos].Invert(i, j);
            count = historySize[pos];
        } else if (op == 4) {
            int k;
            cin >> k;
            count = historySize[k];
            pos = k;
            printf("pos = %d\n", pos);
        }
        cout << count << "\n";
    }
    return EXIT_SUCCESS;
}