{"id":929,"date":"2021-04-30T17:29:09","date_gmt":"2021-04-30T09:29:09","guid":{"rendered":"https:\/\/beijian99.top\/?p=929"},"modified":"2025-05-06T16:14:48","modified_gmt":"2025-05-06T08:14:48","slug":"%e6%a0%91%e7%8a%b6%e6%95%b0%e7%bb%84%e6%b1%82%e9%80%86%e5%ba%8f%e5%af%b9","status":"publish","type":"post","link":"https:\/\/beijian99.top\/?p=929","title":{"rendered":"\u6811\u72b6\u6570\u7ec4\u6c42\u9006\u5e8f\u5bf9"},"content":{"rendered":"\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"452\" src=\"https:\/\/beijian99.top\/wp-content\/uploads\/2025\/04\/image-65-1024x452.png\" alt=\"\" class=\"wp-image-933\" srcset=\"https:\/\/beijian99.top\/wp-content\/uploads\/2025\/04\/image-65-1024x452.png 1024w, https:\/\/beijian99.top\/wp-content\/uploads\/2025\/04\/image-65-300x132.png 300w, https:\/\/beijian99.top\/wp-content\/uploads\/2025\/04\/image-65-768x339.png 768w, https:\/\/beijian99.top\/wp-content\/uploads\/2025\/04\/image-65.png 1374w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"957\" height=\"429\" src=\"https:\/\/beijian99.top\/wp-content\/uploads\/2025\/04\/image-67.png\" alt=\"\" class=\"wp-image-937\" srcset=\"https:\/\/beijian99.top\/wp-content\/uploads\/2025\/04\/image-67.png 957w, https:\/\/beijian99.top\/wp-content\/uploads\/2025\/04\/image-67-300x134.png 300w, https:\/\/beijian99.top\/wp-content\/uploads\/2025\/04\/image-67-768x344.png 768w\" sizes=\"auto, (max-width: 957px) 100vw, 957px\" \/><\/figure>\n\n\n\n<p>\u9006\u5e8f\u5bf9\u8ba1\u6570\u793a\u4f8b\uff08\u57fa\u4e8e\u6811\u72b6\u6570\u7ec4\uff09<\/p>\n\n\n\n<p>\u9006\u5e8f\u5bf9\uff08Inversion\uff09\u662f\u6307\u6570\u7ec4\u4e2d\u524d\u9762\u7684\u5143\u7d20\u5927\u4e8e\u540e\u9762\u7684\u5143\u7d20\u7684\u5bf9\u6570\uff0c\u5373\u82e5 <code>i &lt; j<\/code> \u4e14 <code>a[i] &gt; a[j]<\/code>\uff0c\u5219 <code>(a[i], a[j])<\/code> \u662f\u4e00\u4e2a\u9006\u5e8f\u5bf9\u3002\u6811\u72b6\u6570\u7ec4\u53ef\u4ee5\u9ad8\u6548\u7edf\u8ba1\u9006\u5e8f\u5bf9\u6570\u91cf\uff0c\u6b65\u9aa4\u5982\u4e0b\uff1a<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p>\u200b<strong>\u200b\u7b97\u6cd5\u6b65\u9aa4\u200b<\/strong>\u200b<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>\u79bb\u6563\u5316\uff08\u53ef\u9009\uff09\uff1a\n<ul class=\"wp-block-list\">\n<li>\u82e5\u5143\u7d20\u503c\u8303\u56f4\u5f88\u5927\uff08\u5982 <code>1e9<\/code>\uff09\uff0c\u9700\u5148\u5c06\u6570\u7ec4\u79bb\u6563\u5316\u4e3a <code>1..n<\/code> \u7684\u6392\u540d\uff0c\u4fdd\u6301\u5927\u5c0f\u5173\u7cfb\u4e0d\u53d8\u3002<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>\u4ece\u53f3\u5411\u5de6\u904d\u5386\uff1a\n<ul class=\"wp-block-list\">\n<li>\u5bf9\u6bcf\u4e2a\u5143\u7d20 <code>a[i]<\/code>\uff0c\u67e5\u8be2\u6811\u72b6\u6570\u7ec4\u4e2d \u5c0f\u4e8e <code>a[i]<\/code> \u7684\u5143\u7d20\u6570\u91cf\uff08\u5373\u5df2\u5904\u7406\u5143\u7d20\u4e2d\u6bd4 <code>a[i]<\/code> \u5c0f\u7684\u6570\u7684\u4e2a\u6570\uff09\u3002<\/li>\n\n\n\n<li> \u9006\u5e8f\u5bf9\u6570\u91cf += <code>i - query(a[i])<\/code>\uff08\u5f53\u524d\u5143\u7d20\u53f3\u4fa7\u6bd4\u5b83\u5c0f\u7684\u6570\u7684\u4e2a\u6570\uff09\u3002<\/li>\n\n\n\n<li> \u5c06 <code>a[i]<\/code> \u63d2\u5165\u6811\u72b6\u6570\u7ec4\uff08<code>update(a[i], 1)<\/code>\uff09\u3002<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>C++ \u5b9e\u73b0<\/strong><\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: cpp; title: ; notranslate\" title=\"\">\n#include &lt;vector&gt;\n#include &lt;algorithm&gt;\nusing namespace std;\n\nclass FenwickTree {\nprivate:\n    vector&lt;int&gt; tree;\n    int lowbit(int x) { return x &amp; -x; }\npublic:\n    FenwickTree(int n) : tree(n + 1, 0) {}\n    void update(int x, int delta) {\n        while (x &lt; tree.size()) {\n            tree&#x5B;x] += delta;\n            x += lowbit(x);\n        }\n    }\n    int query(int x) {\n        int res = 0;\n        while (x &gt; 0) {\n            res += tree&#x5B;x];\n            x -= lowbit(x);\n        }\n        return res;\n    }\n};\n\nint countInversions(vector&lt;int&gt;&amp; nums) {\n    \/\/ \u79bb\u6563\u5316\uff08\u5c06\u539f\u6570\u7ec4\u6620\u5c04\u52301..n\u7684\u6392\u540d\uff09\n    vector&lt;int&gt; sorted = nums;\n    sort(sorted.begin(), sorted.end());\n    sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());\n    \n    \/\/ \u79bb\u6563\u5316\u540e\u7684\u6570\u7ec4\n    for (int&amp; num : nums) {\n        num = lower_bound(sorted.begin(), sorted.end(), num) - sorted.begin() + 1;\n    }\n\n    FenwickTree ft(nums.size());\n    int res = 0;\n    \/\/ \u4ece\u53f3\u5411\u5de6\u904d\u5386\n    for (int i = nums.size() - 1; i &gt;= 0; --i) {\n        res += ft.query(nums&#x5B;i] - 1); \/\/ \u7edf\u8ba1\u6bd4nums&#x5B;i]\u5c0f\u7684\u6570\u7684\u4e2a\u6570\n        ft.update(nums&#x5B;i], 1);        \/\/ \u63d2\u5165\u5f53\u524d\u6570\n    }\n    return res;\n}\n\n<\/pre><\/div>\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p>\u200b<strong>\u200b\u793a\u4f8b\u5206\u6790\u200b<\/strong>\u200b<br>\u8f93\u5165\u6570\u7ec4\uff1a<code>[3, 1, 4, 2]<\/code><\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>\u79bb\u6563\u5316\u540e\uff1a<code>[2, 1, 3, 4]<\/code>\uff08\u539f\u503c <code>3<\/code> \u7684\u6392\u540d\u4e3a <code>2<\/code>\uff0c<code>1<\/code> \u7684\u6392\u540d\u4e3a <code>1<\/code>\uff0c\u4f9d\u6b64\u7c7b\u63a8\uff09\u3002<\/li>\n\n\n\n<li>\u4ece\u53f3\u5411\u5de6\u5904\u7406\uff1a\n<ul class=\"wp-block-list\">\n<li> <code>i=3<\/code>\uff08\u503c <code>4<\/code>\uff09\uff1a<code>query(3-1)=0<\/code>\uff0c\u9006\u5e8f\u5bf9 <code>+=0<\/code>\uff0c\u63d2\u5165 <code>4<\/code>\u3002<\/li>\n\n\n\n<li> <code>i=2<\/code>\uff08\u503c <code>2<\/code>\uff09\uff1a<code>query(2-1)=1<\/code>\uff08<code>1<\/code> \u6bd4 <code>2<\/code> \u5c0f\uff09\uff0c\u9006\u5e8f\u5bf9 <code>+=1<\/code>\uff0c\u63d2\u5165 <code>2<\/code>\u3002<\/li>\n\n\n\n<li> <code>i=1<\/code>\uff08\u503c <code>1<\/code>\uff09\uff1a<code>query(1-1)=0<\/code>\uff0c\u9006\u5e8f\u5bf9 <code>+=0<\/code>\uff0c\u63d2\u5165 <code>1<\/code>\u3002<\/li>\n\n\n\n<li> <code>i=0<\/code>\uff08\u503c <code>3<\/code>\uff09\uff1a<code>query(2-1)=1<\/code>\uff08<code>1<\/code> \u6bd4 <code>3<\/code> \u5c0f\uff09\uff0c\u9006\u5e8f\u5bf9 <code>+=1<\/code>\uff0c\u63d2\u5165 <code>3<\/code>\u3002<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>\u603b\u9006\u5e8f\u5bf9\uff1a<code>0 + 1 + 0 + 1 = 2<\/code>\uff08\u5b9e\u9645\u9006\u5e8f\u5bf9\u4e3a <code>(3,1)<\/code> \u548c <code>(4,2)<\/code>\uff09\u3002<\/li>\n<\/ol>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p>\u200b<strong>\u200b\u65f6\u95f4\u590d\u6742\u5ea6\u200b<\/strong>\u200b<br>\u2022 \u79bb\u6563\u5316\uff1aO(nlog<sup>n<\/sup>)\uff08\u6392\u5e8f + \u53bb\u91cd\uff09\u3002<\/p>\n\n\n\n<p>\u2022 \u6811\u72b6\u6570\u7ec4\u64cd\u4f5c\uff1aO(nlog<sup>n<\/sup>)\uff08\u6bcf\u6b21 <code>update<\/code> \u548c <code>query<\/code> \u4e3a O(log<sup>n<\/sup>)\uff09\u3002<\/p>\n\n\n\n<p>\u2022 \u603b\u590d\u6742\u5ea6\uff1aO(nlog<sup>n<\/sup>)\uff0c\u4f18\u4e8e\u66b4\u529b O(n<sup>2<\/sup>)\u3002<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p>\u200b<strong>\u200b\u5173\u952e\u70b9\u200b<\/strong>\u200b<br>\u2022 \u79bb\u6563\u5316\uff1a\u5fc5\u987b\u5c06\u539f\u59cb\u503c\u538b\u7f29\u5230\u8fde\u7eed\u6574\u6570\uff0c\u5426\u5219\u6811\u72b6\u6570\u7ec4\u7a7a\u95f4\u7206\u70b8\u3002<\/p>\n\n\n\n<p>\u2022 \u4ece\u53f3\u5411\u5de6\u904d\u5386\uff1a\u786e\u4fdd\u6bcf\u6b21\u67e5\u8be2\u65f6\uff0c\u6811\u72b6\u6570\u7ec4\u4e2d\u53ea\u5305\u542b\u5f53\u524d\u5143\u7d20\u53f3\u4fa7\u7684\u6570\u3002<\/p>\n\n\n\n<p>\u2022 \u9006\u5e8f\u5bf9\u8ba1\u7b97\uff1a<code>query(a[i]-1)<\/code> \u7edf\u8ba1\u7684\u662f \u4e25\u683c\u5c0f\u4e8e <code>a[i]<\/code> \u7684\u6570\u7684\u4e2a\u6570\u3002<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p>\u200b<strong>\u200b\u6269\u5c55\u95ee\u9898\u200b<\/strong>\u200b<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>\u5982\u679c\u6570\u7ec4\u4e2d\u6709\u91cd\u590d\u5143\u7d20\uff1a\u79bb\u6563\u5316\u65f6\u4fdd\u7559\u91cd\u590d\u503c\uff0c<code>query(a[i]-1)<\/code> \u4ecd\u80fd\u6b63\u786e\u7edf\u8ba1\u4e25\u683c\u5c0f\u4e8e\u7684\u6570\u7684\u4e2a\u6570\u3002<\/li>\n\n\n\n<li>\u6c42\u6570\u7ec4\u4e2d\u6bcf\u4e2a\u5143\u7d20\u7684\u9006\u5e8f\u6570\uff1a\u5728\u904d\u5386\u65f6\u8bb0\u5f55\u6bcf\u4e2a <code>i<\/code> \u7684 <code>query(a[i]-1)<\/code>\uff0c\u5b58\u5165\u7ed3\u679c\u6570\u7ec4\u3002<\/li>\n<\/ol>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u9006\u5e8f\u5bf9\u8ba1\u6570\u793a\u4f8b\uff08\u57fa\u4e8e\u6811\u72b6\u6570\u7ec4\uff09 \u9006\u5e8f\u5bf9\uff08Inversion\uff09\u662f\u6307\u6570\u7ec4\u4e2d\u524d\u9762\u7684\u5143\u7d20\u5927\u4e8e\u540e\u9762\u7684\u5143\u7d20\u7684\u5bf9\u6570\uff0c\u5373\u82e5 i [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":937,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"footnotes":""},"categories":[4],"tags":[],"class_list":["post-929","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-algorithm"],"_links":{"self":[{"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/posts\/929","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/beijian99.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=929"}],"version-history":[{"count":4,"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/posts\/929\/revisions"}],"predecessor-version":[{"id":938,"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/posts\/929\/revisions\/938"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/media\/937"}],"wp:attachment":[{"href":"https:\/\/beijian99.top\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=929"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/beijian99.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=929"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/beijian99.top\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=929"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}