\u7ee7\u4e0a\u4e00\u7bc7\u6784\u9020\u54c8\u5e0c\u8868\u7684\u6587\u7ae0\u4ee5\u540e, \u53c8\u78b0\u5230\u4e86\u4e00\u4e2a\u9700\u8981\u6784\u9020\u54c8\u5e0c\u8868\u7684\u95ee\u9898, \u53ea\u4e0d\u8fc7\u6b64\u65f6\u7684\u54c8\u5e0c\u8868\u5df2\u7ecf\u4eceunordered_map\u6362\u4e3a\u4e86unordered_set.<\/p>\n
<\/p>\n
\u4fe1\u5fc3\u6ee1\u6ee1\u5730\u60f3\u7528\u521a\u5b66\u7684\u5229\u7528\u6876\u548c\u94fe\u8868\u6784\u9020unordered_map\u7684\u65b9\u6cd5\u6765\u79d2\u4e86\u8fd9\u4e2a\u95ee\u9898, \u7ed3\u679c\u867d\u7136\u8fd8\u53ef\u4ee5, \u8dd1\u4e8628\u4e2a\u6848\u4f8b\u8017\u65f656ms\u2026\u2026 \u7136\u800c, \u5f53\u6211\u770b\u5230\u53c8\u6709\u5927\u795e\u63d0\u51fa\u66f4\u5f3a\u7684\u7b97\u6cd5\u65f6, \u771f\u662f\u4f69\u670d\u5f97\u4e94\u4f53\u6295\u5730, mark\u4e00\u4e0b, \u4ed6\u662f\u901a\u8fc7\u6784\u9020\u4e00\u68f5\u4e8c\u53c9\u67e5\u627e\u6811\u6765\u5b8c\u6210\u7684, \u5728\u91ca\u653e\u5185\u5b58\u65f6\u4e5f\u5f88\u503c\u5f97\u5b66\u4e60, \u5728\u5220\u9664\u8282\u70b9\u4e4b\u524d\u5148\u628a\u5de6\u5b50\u6811\u548c\u53f3\u5b50\u6811\u5220\u9664~ \u4ee3\u7801\u5982\u4e0b\u6240\u793a:<\/p>\n
\r\n\/\/ https:\/\/www.geeksforgeeks.org\/fast-io-for-competitive-programming\/\r\n\/\/ https:\/\/codeforces.com\/blog\/entry\/10297\r\n\/\/ People are not actually implementing any form of hash set, so I use tricks\r\nstatic const int _ = []() {\r\nios::sync_with_stdio(false);\r\ncin.tie(nullptr);\r\nreturn 0;\r\n}();\r\n\r\nstruct MyHashSetNode {\r\nint val;\r\nMyHashSetNode *left, *right;\r\n\r\nMyHashSetNode(int v) : val(v), left(nullptr), right(nullptr) {}\r\n~MyHashSetNode() {\r\nif(left != nullptr) delete left;\r\nif(right != nullptr) delete right;\r\n}\r\n};\r\n\r\nclass MyHashSetTree {\r\nprivate:\r\nMyHashSetNode *root;\r\npublic:\r\nMyHashSetTree() : root(nullptr) {}\r\n~MyHashSetTree() {\r\nif(root != nullptr)\r\ndelete root; \/\/ traverses through destructors\r\n}\r\n\r\nMyHashSetNode *Insert(int x, MyHashSetNode *parent) {\r\nMyHashSetNode *result = parent;\r\n\r\nif (parent == nullptr) {\r\nresult = new MyHashSetNode(x);\r\n} else if (x < parent->val) {\r\nparent->left = Insert(x, parent->left);\r\n} else if (x > parent->val) {\r\nparent->right = Insert(x, parent->right);\r\n} else {\r\nreturn nullptr; \/\/ duplicate, add should not comply\r\n}\r\n\r\nreturn result;\r\n}\r\n\r\nbool Insert(int x) {\r\nif(Find(x) != nullptr)\r\nreturn false;\r\n\r\nroot = Insert(x, root);\r\nreturn true;\r\n}\r\n\r\nMyHashSetNode *Find(int x, MyHashSetNode *parent) {\r\nMyHashSetNode *current = parent;\r\nint currentValue;\r\n\r\nwhile (current != nullptr) {\r\ncurrentValue = current->val;\r\nif (x < currentValue) {\r\ncurrent = current->left;\r\n} else if (x > currentValue) {\r\ncurrent = current->right;\r\n} else {\r\nreturn current;\r\n}\r\n}\r\n\r\nreturn nullptr;\r\n}\r\n\r\nMyHashSetNode *Find(int x) {\r\nif (root != nullptr)\r\nreturn Find(x, root);\r\n\r\nreturn nullptr;\r\n}\r\n\r\nMyHashSetNode *FindMin(MyHashSetNode *parent) {\r\nMyHashSetNode *current = parent;\r\nMyHashSetNode *left = nullptr;\r\n\r\nif (current != nullptr) {\r\nwhile ((left = current->left) != nullptr)\r\ncurrent = left;\r\n}\r\n\r\nreturn current;\r\n}\r\n\r\nMyHashSetNode *RemoveMin(MyHashSetNode *parent) {\r\nif (parent == nullptr) {\r\nreturn nullptr;\r\n} else if (parent->left != nullptr) {\r\nparent->left = RemoveMin(parent->left);\r\nreturn parent;\r\n} else {\r\nMyHashSetNode *result = parent->right;\r\n\r\nparent->right = parent->left = nullptr;\r\ndelete parent;\r\nreturn result;\r\n}\r\n}\r\n\r\nMyHashSetNode *Remove(int x, MyHashSetNode *parent) {\r\nMyHashSetNode *current = parent;\r\nMyHashSetNode *left = nullptr;\r\nMyHashSetNode *right = nullptr;\r\nint currentValue;\r\n\r\nif (current != nullptr) {\r\nleft = current->left;\r\nright = current->right;\r\ncurrentValue = current->val;\r\n}\r\n\r\nif (current == nullptr) {\r\nreturn nullptr;\r\n} else if (x < currentValue) {\r\ncurrent->left = Remove(x, left);\r\n} else if (x > currentValue) {\r\ncurrent->right = Remove(x, right);\r\n} else if (left != nullptr && right != nullptr) {\r\ncurrent->val = FindMin(right)->val;\r\ncurrent->right = RemoveMin(right);\r\n} else {\r\ncurrent = (left != nullptr) ? left : right;\r\n\r\nparent->right = parent->left = nullptr;\r\ndelete parent;\r\n}\r\n\r\nreturn current;\r\n}\r\n\r\nbool Remove(int x) {\r\nif(Find(x) == nullptr)\r\nreturn false;\r\n\r\nroot = Remove(x, root);\r\nreturn true;\r\n}\r\n};\r\n\r\nclass MyHashSet {\r\nprivate:\r\nMyHashSetTree tree;\r\npublic:\r\n\/** Initialize your data structure here. *\/\r\nMyHashSet() {\r\n\r\n}\r\n\r\nvoid add(int key) {\r\ntree.Insert(key);\r\n}\r\n\r\nvoid remove(int key) {\r\ntree.Remove(key);\r\n}\r\n\r\n\/** Returns true if this set contains the specified element *\/\r\nbool contains(int key) {\r\nreturn tree.Find(key) != nullptr;\r\n}\r\n};\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"\u7ee7\u4e0a\u4e00\u7bc7\u6784\u9020\u54c8\u5e0c\u8868\u7684\u6587\u7ae0\u4ee5\u540e, \u53c8\u78b0\u5230\u4e86\u4e00\u4e2a\u9700\u8981\u6784\u9020\u54c8\u5e0c\u8868\u7684\u95ee\u9898, \u53ea\u4e0d\u8fc7\u6b64\u65f6\u7684\u54c8\u5e0c\u8868\u5df2\u7ecf\u4eceunordered … \u7ee7\u7eed\u9605\u8bfb\u6784\u9020\u54c8\u5e0c\u8868II<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5],"tags":[],"_links":{"self":[{"href":"https:\/\/www.caiqinyi.cn\/index.php\/wp-json\/wp\/v2\/posts\/151"}],"collection":[{"href":"https:\/\/www.caiqinyi.cn\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.caiqinyi.cn\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.caiqinyi.cn\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.caiqinyi.cn\/index.php\/wp-json\/wp\/v2\/comments?post=151"}],"version-history":[{"count":5,"href":"https:\/\/www.caiqinyi.cn\/index.php\/wp-json\/wp\/v2\/posts\/151\/revisions"}],"predecessor-version":[{"id":801,"href":"https:\/\/www.caiqinyi.cn\/index.php\/wp-json\/wp\/v2\/posts\/151\/revisions\/801"}],"wp:attachment":[{"href":"https:\/\/www.caiqinyi.cn\/index.php\/wp-json\/wp\/v2\/media?parent=151"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.caiqinyi.cn\/index.php\/wp-json\/wp\/v2\/categories?post=151"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.caiqinyi.cn\/index.php\/wp-json\/wp\/v2\/tags?post=151"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}