This documentation is automatically generated by online-judge-tools/verification-helper
This project is maintained by tsutaj
// Binary Trie // ・色々 verify たりない。特に遅延評価はまだ何も verify してない!要注意!! // Verify 済み // ・insert, erase // ・min_element // ・count_less // ・get_kth // 通した問題一覧 // ・ARC033-C データ構造 (insert, erase, get_kth) // ・Codeforces Round #470 C Perfect Security (insert, erase, min_element) // ・SPOJ SubXor (insert, erase, count_less) template <typename Type = unsigned int, int B = 32> struct BinaryTrie { private: struct Node { int cnt; Type lazy; Node* child[2]; Node() : cnt(0), lazy(0), child{ nullptr, nullptr } {} }; int get_size(Node *t) const { return t ? t->cnt : 0; } void lazy_eval(Node* t, int b) const { if((t->lazy >> (Type)b) & (Type)1) swap(t->child[0], t->child[1]); if(t->child[0]) t->child[0]->lazy ^= t->lazy; if(t->child[1]) t->child[1]->lazy ^= t->lazy; t->lazy = 0; } Node* add(Node* t, Type val, int b = B - 1) { if(!t) t = new Node; t->cnt++; if(b < 0) return t; lazy_eval(t, b); int bin = (val >> (Type)b) & (Type)1; t->child[bin] = add(t->child[bin], val, b-1); return t; } Node* sub(Node* t, Type val, int b = B - 1) { assert(t); t->cnt--; if(t->cnt == 0) return nullptr; if(b < 0) return t; lazy_eval(t, b); int bin = (val >> (Type)b) & (Type)1; t->child[bin] = sub(t->child[bin], val, b-1); return t; } // 全体を val で XOR 取った時の最小値 Type get_min(Node* t, Type val, int b = B - 1) const { assert(t); if(b < 0) return 0; lazy_eval(t, b); int bin = (val >> (Type)b) & (Type)1; bin ^= !t->child[bin]; return get_min(t->child[bin], val, b-1) | ((Type)bin << (Type)b); } // 全体を val で XOR 取ったときに k 番目 (1-indexed) に小さい値 Type get_kth(Node* t, Type val, int k, int b = B - 1) const { assert(t); if(b < 0) return 0; lazy_eval(t, b); int bin = (val >> (Type)b) & (Type)1; if(get_size(t->child[bin]) < k) k -= get_size(t->child[bin]), bin ^= 1; // fprintf(stderr, "bin = %d\n", bin); return get_kth(t->child[bin], val, k, b-1) | ((Type)bin << (Type)b); } // 集合内にある val 以上の要素の中で最小のものの id (1-indexed? (TODO: verify)) int get_lower(Node* t, Type val, int b = B - 1) { if(!t || b < 0) return 0; lazy_eval(t, b); bool bin = (val >> (Type)b) & (Type)1; return (bin && t->child[0] ? t->child[0]->cnt : 0) + get_lower(t->child[bin], val, b-1); } // 全体を val で XOR 取ったときに x 未満になる要素の数 int count_less(Node* t, Type val, Type x, int b = B - 1) { if(!t || b < 0) return 0; lazy_eval(t, b); bool bin = (val >> (Type)b) & (Type)1; int add = 0; if(x >> (Type)b & 1) add += get_size(t->child[bin]), bin ^= 1; return add + count_less(t->child[bin], val, x, b-1); } Node* root; public: BinaryTrie() : root(nullptr) {} int size() const { return get_size(root); } bool empty() const { return !root; } void insert(Type val) { root = add(root, val); } void erase(Type val) { root = sub(root, val); } // XOR とった後の値ではなく、集合内にある値がそのまま返る Type max_element(Type XOR = 0) const { return get_min(root, ~XOR); } Type min_element(Type XOR = 0) const { return get_min(root, XOR); } // 要素全体を XOR void xor_all(Type val) { if(root) root->lazy ^= val; } // 要素のインデックスが返ってくることに注意 int lower_bound(Type val) { return get_lower(root, val); } int upper_bound(Type val) { return get_lower(root, val + 1); } // 全体に XOR したときの val 未満の値の数 int count_less(Type val, Type XOR = 0) { return count_less(root, XOR, val); } // 全体に XOR したときの val を超える値の数 int count_upper(Type val, Type XOR = 0) { return size() - count_less(root, XOR, val + 1); } // 0-indexed Type get_kth(int k, Type XOR = 0) const { assert(0 <= k and k < size()); return get_kth(root, XOR, k+1); } // 0-indexed Type operator[](int k) { return get_kth(k); } };
#line 1 "structure/strc_018_binarytrie.cpp" // Binary Trie // ・色々 verify たりない。特に遅延評価はまだ何も verify してない!要注意!! // Verify 済み // ・insert, erase // ・min_element // ・count_less // ・get_kth // 通した問題一覧 // ・ARC033-C データ構造 (insert, erase, get_kth) // ・Codeforces Round #470 C Perfect Security (insert, erase, min_element) // ・SPOJ SubXor (insert, erase, count_less) template <typename Type = unsigned int, int B = 32> struct BinaryTrie { private: struct Node { int cnt; Type lazy; Node* child[2]; Node() : cnt(0), lazy(0), child{ nullptr, nullptr } {} }; int get_size(Node *t) const { return t ? t->cnt : 0; } void lazy_eval(Node* t, int b) const { if((t->lazy >> (Type)b) & (Type)1) swap(t->child[0], t->child[1]); if(t->child[0]) t->child[0]->lazy ^= t->lazy; if(t->child[1]) t->child[1]->lazy ^= t->lazy; t->lazy = 0; } Node* add(Node* t, Type val, int b = B - 1) { if(!t) t = new Node; t->cnt++; if(b < 0) return t; lazy_eval(t, b); int bin = (val >> (Type)b) & (Type)1; t->child[bin] = add(t->child[bin], val, b-1); return t; } Node* sub(Node* t, Type val, int b = B - 1) { assert(t); t->cnt--; if(t->cnt == 0) return nullptr; if(b < 0) return t; lazy_eval(t, b); int bin = (val >> (Type)b) & (Type)1; t->child[bin] = sub(t->child[bin], val, b-1); return t; } // 全体を val で XOR 取った時の最小値 Type get_min(Node* t, Type val, int b = B - 1) const { assert(t); if(b < 0) return 0; lazy_eval(t, b); int bin = (val >> (Type)b) & (Type)1; bin ^= !t->child[bin]; return get_min(t->child[bin], val, b-1) | ((Type)bin << (Type)b); } // 全体を val で XOR 取ったときに k 番目 (1-indexed) に小さい値 Type get_kth(Node* t, Type val, int k, int b = B - 1) const { assert(t); if(b < 0) return 0; lazy_eval(t, b); int bin = (val >> (Type)b) & (Type)1; if(get_size(t->child[bin]) < k) k -= get_size(t->child[bin]), bin ^= 1; // fprintf(stderr, "bin = %d\n", bin); return get_kth(t->child[bin], val, k, b-1) | ((Type)bin << (Type)b); } // 集合内にある val 以上の要素の中で最小のものの id (1-indexed? (TODO: verify)) int get_lower(Node* t, Type val, int b = B - 1) { if(!t || b < 0) return 0; lazy_eval(t, b); bool bin = (val >> (Type)b) & (Type)1; return (bin && t->child[0] ? t->child[0]->cnt : 0) + get_lower(t->child[bin], val, b-1); } // 全体を val で XOR 取ったときに x 未満になる要素の数 int count_less(Node* t, Type val, Type x, int b = B - 1) { if(!t || b < 0) return 0; lazy_eval(t, b); bool bin = (val >> (Type)b) & (Type)1; int add = 0; if(x >> (Type)b & 1) add += get_size(t->child[bin]), bin ^= 1; return add + count_less(t->child[bin], val, x, b-1); } Node* root; public: BinaryTrie() : root(nullptr) {} int size() const { return get_size(root); } bool empty() const { return !root; } void insert(Type val) { root = add(root, val); } void erase(Type val) { root = sub(root, val); } // XOR とった後の値ではなく、集合内にある値がそのまま返る Type max_element(Type XOR = 0) const { return get_min(root, ~XOR); } Type min_element(Type XOR = 0) const { return get_min(root, XOR); } // 要素全体を XOR void xor_all(Type val) { if(root) root->lazy ^= val; } // 要素のインデックスが返ってくることに注意 int lower_bound(Type val) { return get_lower(root, val); } int upper_bound(Type val) { return get_lower(root, val + 1); } // 全体に XOR したときの val 未満の値の数 int count_less(Type val, Type XOR = 0) { return count_less(root, XOR, val); } // 全体に XOR したときの val を超える値の数 int count_upper(Type val, Type XOR = 0) { return size() - count_less(root, XOR, val + 1); } // 0-indexed Type get_kth(int k, Type XOR = 0) const { assert(0 <= k and k < size()); return get_kth(root, XOR, k+1); } // 0-indexed Type operator[](int k) { return get_kth(k); } };