{"id":160,"date":"2024-03-09T16:00:08","date_gmt":"2024-03-09T08:00:08","guid":{"rendered":"https:\/\/linxce.ink\/?p=160"},"modified":"2024-03-09T16:28:46","modified_gmt":"2024-03-09T08:28:46","slug":"%e7%ba%bf%e6%ae%b5%e6%a0%91%e4%bc%98%e5%8c%96%e5%bb%ba%e5%9b%be","status":"publish","type":"post","link":"https:\/\/linxce.ink\/index.php\/%e7%ba%bf%e6%ae%b5%e6%a0%91%e4%bc%98%e5%8c%96%e5%bb%ba%e5%9b%be\/%e5%85%a8%e9%83%a8\/acm\/","title":{"rendered":"\u7ebf\u6bb5\u6811\u4f18\u5316\u5efa\u56fe"},"content":{"rendered":"<p>\u5728\u6700\u77ed\u8def\u3001\u5f3a\u8fde\u901a\u5206\u91cf\u30012-SAT\u3001\u7f51\u7edc\u6d41\u7b49\u56fe\u8bba\u95ee\u9898\u4e2d\uff0c\u8fb9\u6570\u6709\u65f6\u8fbe\u5230 O(n2) \u751a\u81f3 O(n3)\uff0c\u6210\u4e3a\u65f6\u95f4\u6216\u7a7a\u95f4\u590d\u6742\u5ea6\u7684\u74f6\u9888\u6240\u5728\uff0c\u4f7f\u7528\u4f18\u5316\u5efa\u56fe\u53ef\u4ee5\u5728\u4e0d\u5f71\u54cd\u6548\u679c\u7684\u60c5\u51b5\u4e0b\u5efa\u51fa\u8fb9\u6570\u66f4\u5c11\u7684\u56fe\u3002<\/p>\n<p>\u652f\u6301\u4ee5\u4e0b\u56db\u79cd\u64cd\u4f5c\uff1a<\/p>\n<blockquote><p>u-&gt;v\u8fde\u8fb9, u-&gt;[l, r]\u8fde\u8fb9, [l, r]-&gt;v \u8fde\u8fb9, [l1, r1]-&gt;[l2, r2]\u8fde\u8fb9<\/p><\/blockquote>\n<ul>\n<li>\u666e\u901a\u7248\u672c\uff1a<\/li>\n<\/ul>\n<p>\u533a\u95f4\u64cd\u4f5c\u60f3\u5230\u7ebf\u6bb5\u6811\uff0c\u53ef\u4ee5\u628a\u533a\u95f4\u62c6\u6210 nlogn \u4e2a\u7ebf\u6bb5\u6811\u4e0a\u533a\u95f4\u3002\u5148\u6309\u7167\u7ebf\u6bb5\u6811\u5efa\u51fa\u4e24\u68f5\u6811\uff1a\u5916\u5411\u6811\u548c\u5185\u5411\u6811\u3002\u5bf9\u4e8e\u6240\u6709\u8fde\u5165\u4e00\u4e2a\u533a\u95f4\u7684\u64cd\u4f5c\uff0c\u5c06\u8fb9\u8fde\u5411\u5916\u5411\u6811\uff0c\u8fd9\u4ee3\u8868\u7740\u8fde\u5165\u4e00\u4e2a\u5927\u533a\u95f4\u7684\u8fb9\u5728\u7ecf\u8fc7\u5916\u5411\u6811\u8fb9\u540e\uff0c\u4e5f\u53ef\u4ee5\u8fde\u5165\u5c0f\u533a\u95f4\uff1b\u5bf9\u4e8e\u6240\u6709\u4ece\u4e00\u4e2a\u533a\u95f4\u8fde\u51fa\u7684\u64cd\u4f5c\uff0c\u5c06\u8fb9\u4ece\u5185\u5411\u6811\u8fde\u51fa\uff0c\u8fd9\u4ee3\u8868\u7740\u4e00\u4e2a\u5c0f\u533a\u95f4\u5728\u7ecf\u8fc7\u5916\u5411\u6811\u7684\u8fb9\u540e\uff0c\u53ef\u4ee5\u8fde\u51fa\u5927\u533a\u95f4\u7684\u8fb9\u3002<\/p>\n<p>\u4e3a\u4e86\u907f\u514d\u51b2\u7a81\uff0c\u5c06\u5916\u5411\u6811\u7684\u7f16\u53f7\u4ece 1 \u5f00\u59cb\uff0c\u5185\u5411\u6811\u7684\u7f16\u53f7\u4ece 4n \u5f00\u59cb\uff0c\u5355\u4e2a\u8282\u70b9\u7684\u7f16\u53f7\u4ece 8n \u5f00\u59cb\uff0c\u4e14\u8981\u4e0e\u4e24\u68f5\u6811\u7684\u53f6\u5b50\u76f8\u8fde\u3002<\/p>\n<p>\u533a\u95f4\u4e0e\u533a\u95f4\u76f8\u8fde\u6309\u7167\u4e0a\u9762\u505a\u6cd5\u662f logn * logn \u6761\u8fb9\uff0c\u53ef\u4ee5\u65b0\u5efa\u4e24\u4e2a\u8282\u70b9\u4ee5\u4e00\u6761\u8fb9\u76f8\u8fde\uff0c\u5c06\u8fb9\u6743\u8bbe\u7f6e\u5728\u8fd9\u6761\u8fb9\u4e0a\u3002\u5185\u5411\u6811\u5bf9\u5e94\u533a\u95f4\u5168\u90e8\u7531\u5176\u4e2d\u4e00\u4e2a\u8282\u70b9\u8fde\u5165\uff0c\u5916\u5411\u6811\u5bf9\u5e94\u533a\u95f4\u5168\u90e8\u8fde\u5230\u53e6\u4e00\u4e2a\u8282\u70b9\uff0c\u8fd9\u6837\u5c31\u53ea\u6709 logn \u6761\u8fb9\u3002\u603b\u70b9\u6570\u5927\u6982\u5728 10n \u5de6\u53f3\uff0c\u603b\u8fb9\u6570\u662f mlogn \u7ea7\u522b\u3002<\/p>\n<ul>\n<li>LinXce\u7248\u672c\uff1a<\/li>\n<\/ul>\n<p>\u76ee\u524d\u53ea\u6709 u-&gt;v\u8fde\u8fb9, u-&gt;[l, r]\u8fde\u8fb9, [l, r]-&gt;v \u8fde\u8fb9\uff0c\u4e09\u79cd\u8fde\u8fb9\u65b9\u5f0f\u3002<\/p>\n<p>\u533a\u95f4\u64cd\u4f5c\u8054\u7cfb\u7ebf\u6bb5\u6811\uff0c\u4ee5\u7ebf\u6bb5\u6811\u7684\u7f16\u53f7\u4f5c\u4e3a\u8282\u70b9\u7f16\u53f7\u3002\u6a21\u4eff\u666e\u901a\u7ebf\u6bb5\u6811\u533a\u95f4\u67e5\u8be2\u64cd\u4f5c\uff0c\u82e5\u5f53\u524d\u533a\u95f4\u5728\u76ee\u6807\u533a\u95f4 [l, r] \u5185\uff0c\u5c31\u8fde\u63a5\u70b9\u548c\u5f53\u524d\u533a\u95f4\uff0c\u7136\u540e\u5411\u4e0b\u8bbf\u95ee\u3002<\/p>\n<p>\u8fdb\u884c\u6700\u77ed\u8def\u8fd0\u7b97\u65f6\uff0c\u5bf9\u4e8e\u5f53\u524d\u8282\u70b9 i\uff0c\u5411\u4e0a\u67e5\u627e\u5305\u542b\u5b83\u7684\u7236\u533a\u95f4\uff0c\u5411\u4e0b\u67e5\u627e\u5b83\u7684\u6240\u6709\u5b50\u533a\u95f4\uff0c\u5c06\u6240\u6709\u67e5\u627e\u5230\u7684\u8282\u70b9\u4ee5\u53ca\u5176\u672c\u8eab\u52a0\u5165\u6808\uff0c\u5e76 vis \u6807\u8bb0\u3002\u8ba1\u7b97\u8def\u5f84\u6743\u503c\u65f6\uff0c\u4ee5\u5f53\u524d\u8282\u70b9\u7684 dis[i] \u4e3a\u521d\u59cb\u4ee3\u4ef7\uff0c\u904d\u5386\u6240\u6709\u6808\u4e2d\u7684\u8282\u70b9 j\uff0c\u4ee5\u6808\u4e2d\u7ed3\u70b9\u8fb9 (j, k) \u7684\u6743\u503c w \uff0c\u7528 dis[i] + w \u66f4\u65b0\u5230\u8fbe\u7684\u8282\u70b9\u7684 dis[k]\u3002<\/p>\n<pre><code class=\"language-cc\" lang=\"cc\">typedef pair&lt;ll, int&gt; pli;\nstruct edge { ll v, w; };\nstack&lt;int&gt; st;\nvector&lt;edge&gt; g[N &lt;&lt; 2];\nll dis[N &lt;&lt; 2];\nint node[N], leaf[N &lt;&lt; 2];\nbool vis[N &lt;&lt; 2];\nvoid build(int k, int l, int r)\n{\n    if (l == r)\n    {\n        node[l] = k;\n        leaf[k] = l; \/\/\u8bb0\u5f55\u53f6\u5b50\u8282\u70b9\u5bf9\u5e94\u4f4d\u7f6e\n        return;\n    }\n    int mid = l + r &gt;&gt; 1;\n    build(k &lt;&lt; 1, l, mid);\n    build(k &lt;&lt; 1 | 1, mid + 1, r);\n}\n\/\/\u8fde\u63a5\u8fb9\uff1aop == 0\u7531\u70b9\u5355\u5411\u8fde\u63a5\u8fb9\uff0cop == 1\u7531\u8fb9\u5355\u5411\u8fde\u63a5\u70b9\nvoid conPI(int k, int l, int r, int x, int y, int u, ll w, int op)\n{\n    if (x &lt;= l &amp;&amp; r &lt;= y)\n        return op ? g[k].pb({node[u], w}) : g[node[u]].pb({k, w});\n    int mid = l + r &gt;&gt; 1;\n    if (x &lt;= mid)\n        conPI(k &lt;&lt; 1, l, mid, x, y, u, w, op);\n    if (mid &lt; y)\n        conPI(k &lt;&lt; 1 | 1, mid + 1, r, x, y, u, w, op);\n}\nvoid upRange(int k, ll w) \/\/\u5411\u4e0a\u641c\u7d22\u8fb9\n{\n    if (!vis[k])\n        st.push(k), vis[k] = true;\n    if (k == 1)\n        return;\n    upRange(k &gt;&gt; 1, w);\n}\nvoid downRange(int k, ll w) \/\/\u5411\u4e0b\u641c\u7d22\u8fb9\n{\n    dis[k] = min(dis[k], dis[k &gt;&gt; 1]);\n    if (!vis[k])\n        st.push(k), vis[k] = true;\n    if (leaf[k])\n        return;\n    downRange(k &lt;&lt; 1, w);\n    downRange(k &lt;&lt; 1 | 1, w);\n}\nvoid dijkstra(int s, int n)\n{\n    memset(dis, 0x3f, sizeof dis);\n    dis[node[s]] = 0;\n    priority_queue&lt;pli, vector&lt;pli&gt;, greater&lt;pli&gt;&gt; pq;\n    pq.push({0, node[s]});\n    while (!pq.empty())\n    {\n        ll w = pq.top().fi, u = pq.top().se;\n        pq.pop();\n        upRange(u, w);\n        downRange(u, w);\n        while (!st.empty())\n        {\n            int e = st.top();\n            st.pop();\n            for (auto ed : g[e])\n            {\n                ll v = ed.v, w = ed.w;\n                if (dis[v] &gt; dis[u] + w)\n                {\n                    dis[v] = dis[u] + w;\n                    pq.push({dis[v], v});\n                }\n            }\n        }\n    }\n}\n<\/code><\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u5728\u6700\u77ed\u8def\u3001\u5f3a\u8fde\u901a\u5206\u91cf\u30012-SAT&#46;&#46;&#46;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5,22,18],"tags":[21,7,23],"class_list":["post-160","post","type-post","status-publish","format-standard","hentry","category-acm","category-22","category-18","tag-acm","tag-cpp","tag-23"],"_links":{"self":[{"href":"https:\/\/linxce.ink\/index.php\/wp-json\/wp\/v2\/posts\/160","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=160"}],"version-history":[{"count":4,"href":"https:\/\/linxce.ink\/index.php\/wp-json\/wp\/v2\/posts\/160\/revisions"}],"predecessor-version":[{"id":167,"href":"https:\/\/linxce.ink\/index.php\/wp-json\/wp\/v2\/posts\/160\/revisions\/167"}],"wp:attachment":[{"href":"https:\/\/linxce.ink\/index.php\/wp-json\/wp\/v2\/media?parent=160"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/linxce.ink\/index.php\/wp-json\/wp\/v2\/categories?post=160"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/linxce.ink\/index.php\/wp-json\/wp\/v2\/tags?post=160"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}