{"id":130,"date":"2024-02-26T23:41:11","date_gmt":"2024-02-26T15:41:11","guid":{"rendered":"https:\/\/linxce.ink\/?p=130"},"modified":"2024-03-17T21:21:16","modified_gmt":"2024-03-17T13:21:16","slug":"%e8%99%9a%e6%a0%91","status":"publish","type":"post","link":"https:\/\/linxce.ink\/index.php\/%e8%99%9a%e6%a0%91\/%e5%85%a8%e9%83%a8\/acm\/","title":{"rendered":"\u865a\u6811"},"content":{"rendered":"

\u865a\u6811\u662f\u865a\u65e0\u661f\u795e\u5bb6\u79cd\u7684\u6811<\/del><\/h2>\n

\u865a\u6811\u5176\u5b9e\u662f\u865a\u6e0a\u7384\u548c\u85e4\u672c\u6811<\/h2>\n

\"\"
\n\"\"<\/p>\n

\u65f6\u95f4\u590d\u6742\u5ea6O(mlogn)<\/strong>\uff0c\u5176\u4e2dm\u4e3a\u5173\u952e\u70b9\u6570\uff0cn\u4e3a\u603b\u70b9\u6570\u3002<\/h3>\n
\u6784\u9020\u65b9\u6cd5\u2160\uff1a\u4e8c\u6b21\u6392\u5e8f + LCA\u8fde\u8fb9<\/h5>\n
\/*lca\u6a21\u677f*\/\n\/\/\u53ef\u4ee5\u5c061\u4f5c\u4e3a\u865a\u6811\u6839\u8282\u70b9\u65b9\u4fbf\u64cd\u4f5c\nint dfn[N];\nvector<int> kp, a, vt[N]; \/\/ kp\u5b58\u50a8\u5173\u952e\u70b9, a\u5b58\u50a8\u865a\u6811\u5e8f\u5217\u7ed3\u679c, vt\u4e3a\u65b0\u5efa\u865a\u6811\nvoid build_virtual_tree()\n{\n    auto cmp = [&](int a, int b) -> bool\n    { return dfn[a] < dfn[b]; };\n    sort(kp.begin(), kp.end(), cmp); \/\/ \u628a\u5173\u952e\u70b9\u6309\u7167 dfn \u5e8f\u6392\u5e8f\n    a.push_back(kp.front());\n    for (int i = 1; i < kp.size(); ++i)\n    {\n        a.push_back(kp[i]);\n        a.push_back(lca(kp[i - 1], kp[i])); \/\/ \u63d2\u5165 lca\n    }\n    sort(a.begin(), a.end());\n    a.erase(unique(a.begin(), a.end()), a.end());\n    \/\/ \u5efa\u865a\u6811\n    for (int i = 1; i < a.size(); ++i)\n    {\n        int lc = lca(a[i - 1], a[i]);\n        vt[lc].push_back(a[i]);\n        vt[a[i]].push_back(lc);\n    }\n}\n<\/code><\/pre>\n
\u6784\u9020\u65b9\u6cd5\u2161\uff1a\u5355\u8c03\u6808<\/h5>\n
\/*lca\u6a21\u677f*\/\nint dfn[N];\nvector<int> kp, vt[N]; \/\/ kp\u5b58\u50a8\u5173\u952e\u70b9\nvoid build_virtual_tree()\n{\n    auto cmp = [&](int a, int b) -> bool\n    { return dfn[a] < dfn[b]; };\n    auto conn = [&](int a, int b) -> void\n    { vt[a].push_back(b), vt[b].push_back(a); };\n    sort(kp.begin(), kp.end(), cmp);\n    stack<int> s;\n    s.push(1);\n    \/\/vt[1].clear(); \/\/\u91cd\u590d\u4f7f\u7528\u7684\u521d\u59cb\u5316\n    for (auto i : kp) \/\/ \u5982\u679c1\u53f7\u8282\u70b9\u662f\u5173\u952e\u8282\u70b9\u5c31\u4e0d\u8981\u91cd\u590d\u6dfb\u52a0\n        if (i != 1)\n        {\n            int lc = lca(i, s.top()); \/\/ \u8ba1\u7b97\u5f53\u524d\u8282\u70b9\u4e0e\u6808\u9876\u8282\u70b9\u7684 LCA\n            if (lc != s.top()) \/\/ \u4e0d\u540c\uff0c\u8bf4\u660e\u5f53\u524d\u8282\u70b9\u4e0d\u518d\u5f53\u524d\u6808\u6240\u5b58\u7684\u94fe\u4e0a\n            {\n                int last = s.top();\n                s.pop();\n                while (dfn[lc] < dfn[s.top()]) \/\/ \u5f53\u6b21\u5927\u8282\u70b9\u7684Dfn\u5927\u4e8eLCA\u7684Dfn\n                {\n                    conn(s.top(), last);\n                    last = s.top();\n                    s.pop();\n                }                           \/\/ \u628a\u4e0e\u5f53\u524d\u8282\u70b9\u6240\u5728\u7684\u94fe\u4e0d\u91cd\u5408\u7684\u94fe\u8fde\u63a5\u6389\u5e76\u4e14\u5f39\u51fa\n                if (dfn[lc] > dfn[s.top()]) \/\/ \u8bf4\u660eLCA\u662f\u7b2c\u4e00\u6b21\u5165\u6808\uff0c\u6e05\u7a7a\u5176\u90bb\u63a5\u8868\uff0c\u8fde\u8fb9\u540e\u5f39\u51fa\u6808\u9876\u5143\u7d20\uff0c\u5e76\u5c06 LCA\u5165\u6808\n                {\n                    \/\/vt[lc].clear();\n                    conn(lc, last);\n                    s.push(lc);\n                }\n                else \/\/ \u8bf4\u660eLCA\u5c31\u662f\u6b21\u5927\u8282\u70b9\uff0c\u76f4\u63a5\u5f39\u51fa\u6808\u9876\u5143\u7d20\n                    conn(lc, last);\n            }\n            \/\/vt[i].clear();\n            s.push(i);\n        }\n    int last = s.top();\n    s.pop();\n    while (!s.empty()) \/\/ \u5269\u4f59\u7684\u6700\u540e\u4e00\u6761\u94fe\u8fde\u63a5\u4e00\u4e0b\n    {\n        conn(last, s.top());\n        last = s.top();\n        s.pop();\n    }\n    return;\n}\n<\/code><\/pre>\n
 <\/p>\n","protected":false},"excerpt":{"rendered":"
\u865a\u6811\u662f\u865a\u65e0\u661f\u795e\u5bb6\u79cd\u7684\u6811 \u865a\u6811\u5176\u5b9e...<\/p>\n","protected":false},"author":1,"featured_media":29,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5,18],"tags":[7,17],"class_list":["post-130","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-acm","category-18","tag-cpp","tag-17"],"_links":{"self":[{"href":"https:\/\/linxce.ink\/index.php\/wp-json\/wp\/v2\/posts\/130","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/linxce.ink\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/linxce.ink\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/linxce.ink\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/linxce.ink\/index.php\/wp-json\/wp\/v2\/comments?post=130"}],"version-history":[{"count":12,"href":"https:\/\/linxce.ink\/index.php\/wp-json\/wp\/v2\/posts\/130\/revisions"}],"predecessor-version":[{"id":272,"href":"https:\/\/linxce.ink\/index.php\/wp-json\/wp\/v2\/posts\/130\/revisions\/272"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/linxce.ink\/index.php\/wp-json\/wp\/v2\/media\/29"}],"wp:attachment":[{"href":"https:\/\/linxce.ink\/index.php\/wp-json\/wp\/v2\/media?parent=130"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/linxce.ink\/index.php\/wp-json\/wp\/v2\/categories?post=130"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/linxce.ink\/index.php\/wp-json\/wp\/v2\/tags?post=130"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}