文件列表:

AVL_tree.cpp (5747, 2022-07-29)
Arpa's Trick.cpp (904, 2022-07-29)
BIT 1D.cpp (1039, 2022-07-29)
BIT 2D.cpp (668, 2022-07-29)
BIT 3D.cpp (1403, 2022-07-29)
Black Box/ (0, 2022-07-29)
Black Box/Advanced DS/ (0, 2022-07-29)
Black Box/Advanced DS/Centroid Decomposition.cpp (2546, 2022-07-29)
Black Box/Advanced DS/Heavy Light Decomposition.cpp (1564, 2022-07-29)
Black Box/Advanced DS/Li Chao Tree Lines.cpp (913, 2022-07-29)
Black Box/Advanced DS/Li Chao Tree Parabolic Sample.cpp (4357, 2022-07-29)
Black Box/Advanced DS/Mo Algorithm Example.cpp (1857, 2022-07-29)
Black Box/Advanced DS/Mo on Tree Path.cpp (2691, 2022-07-29)
Black Box/Advanced DS/Persistent Trie.cpp (1481, 2022-07-29)
Black Box/Advanced DS/Rope.cpp (1523, 2022-07-29)
Black Box/Advanced DS/Splay Tree.cpp (6973, 2022-07-29)
Black Box/DP/ (0, 2022-07-29)
Black Box/DP/Convex Hull Line Container.cpp (1713, 2022-07-29)
Black Box/DP/Convex Hull Trick.cpp (1573, 2022-07-29)
Black Box/DP/Digit DP Sample 2.cpp (1263, 2022-07-29)
Black Box/DP/Digit DP Sample.cpp (860, 2022-07-29)
Black Box/DP/Divide and Conquer DP.cpp (1624, 2022-07-29)
Black Box/DP/Dynamic Convex Hull Trick.cpp (2091, 2022-07-29)
Black Box/DP/Edit Distance Recursive.cpp (425, 2022-07-29)
Black Box/DP/IOI Aliens by koosaga.cpp (1878, 2022-07-29)
Black Box/DP/In-out DP.cpp (2010, 2022-07-29)
Black Box/DP/Knuth Optimization.cpp (1234, 2022-07-29)
Black Box/DP/LCS.cpp (1118, 2022-07-29)
Black Box/DP/LIS nlogk.cpp (328, 2022-07-29)
Black Box/DP/Matrix Expo Class.cpp (732, 2022-07-29)
Black Box/DP/Palindrome in a String.cpp (432, 2022-07-29)
Black Box/Game/ (0, 2022-07-29)
Black Box/Game/Green Hacenbush.cpp (546, 2022-07-29)
Black Box/Game/Green Hackenbush 2.cpp (2896, 2022-07-29)
Black Box/Geometry/ (0, 2022-07-29)
Black Box/Geometry/Convex Hull.cpp (774, 2022-07-29)
Black Box/Geometry/Counting Closest Pair of Points.cpp (2045, 2022-07-29)
Black Box/Geometry/Geometry Library.cpp (12779, 2022-07-29)
Black Box/Geometry/Maximum Points to Enclose in a Circle of Given Radius with Angular Sweep.cpp (1458, 2022-07-29)
... ...

# CP Library Handy Data Structures and Algorithms --- ## Arpa's Trick ```cpp #include #include using namespace std; // Arpa's O(nlogn) offline min/max range query algorithm template vector Arpas(const vector& a, vector>& queries) { T n = (T)a.size(); vector parent(n); function find = [&](https://github.com/souravrax/cp-library/blob/master/T x) { return x == parent[x] ? x : parent[x] = find(parent[x]); }; stack st; vector>> transition(n); for (int i = 0; i < (int)queries.size(); i++) { T l = queries[i][0]; T r = queries[i][1]; transition[r].push_back({l, i}); } vector ans(n); for (T i = 0; i < n; i++) { while (!st.empty() && a[st.top()] >= a[i]) { parent[st.top()] = i; st.pop(); } st.push(i); for (auto& [l, idx] : transition[i]) { ans[idx] = a[find(l)]; } } return ans; } ``` --- ## AVL Tree ```cpp #include using namespace std; struct node { node *left, *right; int left_height, right_height; int count; int val; node(int val) : val(val), left(nullptr), right(nullptr), left_height(1), right_height(1), count(1) {} int bf() { return left_height - right_height; } }; void assignHeight(node *root) { root->left_height = root->left ? max(root->left->left_height, root->left->right_height) + 1 : 1; root->right_height = root->right ? max(root->right->left_height, root->right->right_height) + 1 : 1; root->count = (root->left ? root->left->count : 0) + (root->right ? root->right->count : 0) + 1; } class tree { node *root; int sz; node *insert(node *root, int val) { if (root == nullptr) return new node(val); if (root->val > val) { root->left = insert(root->left, val); } else { root->right = insert(root->right, val); } assignHeight(root); root = balance(root); return root; } bool find(node *root, int val) { if (root == nullptr) return false; if (root->val == val) return true; if (root->val < val) return find(root->right, val); return find(root->left, val); } node *ll(node *root) { node *left = root->left; root->left = left->right; left->right = root; assignHeight(root); assignHeight(left); return left; } node *rr(node *root) { node *right = root->right; root->right = right->left; right->left = root; assignHeight(root); assignHeight(right); return right; } node *lr(node *root) { root->left = rr(root->left); return ll(root); } node *rl(node *root) { root->right = ll(root->right); return rr(root); } node *balance(node *root) { if (root->bf() == 2) { // left_heavy if (root->left->bf() == 1) { // left-left return ll(root); } else { // left-right return lr(root); } } else if (root->bf() == -2) { // right_heavy if (root->right->bf() == 1) { // right-left return rl(root); } else { // right-right return rr(root); } } return root; } node* append_end(node* curr, node* left) { if (curr == nullptr) return left; curr->left = append_end(curr->left, left); assignHeight(curr); return curr; } node* erase(node* root, int val) { if (root == nullptr) return nullptr; if (root->val == val) { if (root->right == nullptr) return root->left; root->right = append_end(root->right, root->left); node* right = root->right; delete root; return right; } if (root->val < val) { root->right = erase(root->right, val); } else { root->left = erase(root->left, val); } assignHeight(root); return root; } int nth_node(node* root, int n) { if (root == nullptr) return -1; int left_val = root->left ? root->left->count : 0; int right_val = root->right ? root->right->count : 0; if (n == left_val + 1) return root->val; if (n > left_val + 1) { return nth_node(root->right, n - left_val - 1); } else { return nth_node(root->left, n); } } int get_rank(node* root, int val) { if (root == nullptr) return -1; if (root->val == val) { return (root->left ? root->left->count : 0) + 1; } else if (root->val < val) { return get_rank(root->right, val) + (root->left ? root->left->count : 0) + 1; } else { return get_rank(root->left, val); } } public: tree() { this->root = nullptr; sz = 0; } bool insert(int val) { if (find(val)) return false; sz++; root = insert(root, val); return true; } bool find(int val) { return find(root, val); } int size() { return this->sz; } bool erase(int val) { if (!find(val)) return false; erase(root, val); return true; } void print() { queue q; q.push(root); while (!q.empty()) { queue nq; while (!q.empty()) { cout << q.front()->val << ' ' << q.front()->left_height << ' ' << q.front()->right_height << ' ' << q.front()->count << endl; if (q.front()->left) nq.push(q.front()->left); if (q.front()->right) nq.push(q.front()->right); q.pop(); } q = move(nq); } } int nth_node(int n) { return nth_node(root, n); } int get_rank(int val) { return get_rank(root, val); } }; int main() { srand(time(NULL)); tree t; int n = 7; vector a; for (int i = 0; i < n; i++) { a.push_back(rand() % 100); t.insert(a.back()); } cout << endl; t.print(); for (int i = 1; i <= n; i++) { cout << t.nth_node(i) << ' '; } cout << endl; for (int& i : a) { cout << i << ' ' << t.get_rank(i) << endl; } } ```

近期下载者：

相关文件：

评论：[我要评论] [举报此文件]

收藏者：