pixeli

#include <fstream>
#include <string>
#include <map>

#define ALPHABET_SIZE 4


std::ifstream fin ("pixeli.in");
std::ofstream fout ("pixeli.out");

struct TrieNode {
    bool isEndOfWord;
    TrieNode* children[ALPHABET_SIZE];

    TrieNode (): isEndOfWord (false) {
        for (int i = 0; i < ALPHABET_SIZE; ++ i)
            children[i] = nullptr;
    }
};

TrieNode* root = new TrieNode ();
int n, task,  q;
int64_t dim;
std::string key;
std::map <std::string, bool> Hash;


inline bool isEmpty (TrieNode* root) {
    for (int i = 0; i < ALPHABET_SIZE; ++ i)
        if (root->children[i]) return false;
    return true;
}

inline void Insert (std::string key) {
    TrieNode* pCrawl = root;
    for (int i = 0; i < (int)key.size (); ++ i) {
        int index = key[i] - '1';
        if (!pCrawl->children[index])
            pCrawl->children[index] = new TrieNode ();
        pCrawl = pCrawl->children[index];
    }
    pCrawl->isEndOfWord = true;
}

inline int64_t Search (std::string key) {
    TrieNode* pCrawl = root;
    for (int i = 0; i < (int)key.size (); ++ i) {
        int index = key[i] - '1';
        if (!pCrawl->children[index]) {
            if (isEmpty (pCrawl)) return dim >> (2 * i);
            else return dim >> (2 * (i + 1));
        }
        pCrawl = pCrawl->children[index];
    }
    return 0;
}

inline TrieNode* Remove (TrieNode* _root, std::string key, int depth = 0) {
    if (!_root) return nullptr;

    if (depth == (int)key.size ()) {
        if (_root->isEndOfWord) _root->isEndOfWord = false;
        if (isEmpty (_root)) {
            delete _root; _root = nullptr;
        }
        return _root;
    }

    int index = key[depth] - '1';
    _root->children[index] = Remove (_root->children[index], key, depth + 1);

    if (isEmpty (_root) && !_root->isEndOfWord && _root != root) {
        delete _root; _root = nullptr;
    }
    return _root;
}


int main () {
    fin >> n >> q; dim = 1LL * n * n;
    for (int i = 1; i <= q; ++ i) {
        fin >> task >> key;
        if (task == 1) {
            if (!Hash[key]) Insert (key);
            else root = Remove (root, key);
            Hash[key] = !Hash[key];
        } else {
            if (!Hash[key]) fout << Search (key) << "\n";
            else fout << "0\n";
        }
    }

    fin.close (), fout.close ();
    return 0;
}