{"id":45,"date":"2022-06-04T10:52:00","date_gmt":"2022-06-04T02:52:00","guid":{"rendered":"http:\/\/ubuntu.tim-wcx.ltd\/wordpress\/index.php\/2022\/06\/04\/%e6%b1%82%e9%80%86%e5%ba%8f%e5%af%b9\/"},"modified":"2022-06-04T10:52:00","modified_gmt":"2022-06-04T02:52:00","slug":"%e6%b1%82%e9%80%86%e5%ba%8f%e5%af%b9","status":"publish","type":"post","link":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/2022\/06\/04\/%e6%b1%82%e9%80%86%e5%ba%8f%e5%af%b9\/","title":{"rendered":"\u6c42\u9006\u5e8f\u5bf9"},"content":{"rendered":"<p><svg  style=\"display: none;\">\n                        <path stroke-linecap=\"round\" d=\"M5,0 0,2.5 5,5z\" id=\"raphael-marker-block\" style=\"-webkit-tap-highlight-color: rgba(0, 0, 0, 0);\"><\/path>\n                    <\/svg><\/p>\n<h4><a id=\"1_0\"><\/a>1.\u6811\u72b6\u6570\u7ec4\u76f4\u63a5\u6c42\u9006\u5e8f\u5bf9<\/h4>\n<p>\u91c7\u7528\u6811\u72b6\u6570\u7ec4\u6807\u8bb0\u6765\u6c42\u9006\u5e8f\u5bf9<\/p>\n<pre><code class=\"prism language-cpp\"><span class=\"token macro property\">#<span class=\"token directive keyword\">include<\/span><span class=\"token string\"><bits\/stdc++.h><\/span><\/span>\n<span class=\"token keyword\">using<\/span> <span class=\"token keyword\">namespace<\/span> std<span class=\"token punctuation\">;<\/span>\n<span class=\"token keyword\">typedef<\/span> <span class=\"token keyword\">long<\/span> <span class=\"token keyword\">long<\/span> ll<span class=\"token punctuation\">;<\/span>\nll n<span class=\"token punctuation\">,<\/span>m<span class=\"token punctuation\">;<\/span>\nll a<span class=\"token punctuation\">[<\/span><span class=\"token number\">100500<\/span><span class=\"token punctuation\">]<\/span><span class=\"token operator\">=<\/span><span class=\"token punctuation\">{<!-- --><\/span><span class=\"token number\">0<\/span><span class=\"token punctuation\">}<\/span><span class=\"token punctuation\">;<\/span>\nll c<span class=\"token punctuation\">[<\/span><span class=\"token number\">100500<\/span><span class=\"token punctuation\">]<\/span><span class=\"token operator\">=<\/span><span class=\"token punctuation\">{<!-- --><\/span><span class=\"token number\">0<\/span><span class=\"token punctuation\">}<\/span><span class=\"token punctuation\">;<\/span>\nll maxn<span class=\"token operator\">=<\/span><span class=\"token number\">10050<\/span><span class=\"token punctuation\">,<\/span>k<span class=\"token punctuation\">,<\/span>ans<span class=\"token operator\">=<\/span><span class=\"token number\">0<\/span><span class=\"token punctuation\">;<\/span>\nll <span class=\"token function\">lowbit<\/span><span class=\"token punctuation\">(<\/span>ll x<span class=\"token punctuation\">)<\/span>\n<span class=\"token punctuation\">{<!-- --><\/span>\n    <span class=\"token keyword\">return<\/span> x<span class=\"token operator\">&<\/span><span class=\"token punctuation\">(<\/span><span class=\"token operator\">-<\/span>x<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">;<\/span>\n<span class=\"token punctuation\">}<\/span>\nll <span class=\"token function\">add<\/span><span class=\"token punctuation\">(<\/span>ll k<span class=\"token punctuation\">,<\/span>ll x<span class=\"token punctuation\">)<\/span>\n<span class=\"token punctuation\">{<!-- --><\/span>\n    <span class=\"token keyword\">for<\/span><span class=\"token punctuation\">(<\/span>ll i<span class=\"token operator\">=<\/span>k<span class=\"token punctuation\">;<\/span>i<span class=\"token operator\"><=<\/span>maxn<span class=\"token punctuation\">;<\/span>i<span class=\"token operator\">+<\/span><span class=\"token operator\">=<\/span><span class=\"token function\">lowbit<\/span><span class=\"token punctuation\">(<\/span>i<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">)<\/span>\n        c<span class=\"token punctuation\">[<\/span>i<span class=\"token punctuation\">]<\/span><span class=\"token operator\">+<\/span><span class=\"token operator\">=<\/span>x<span class=\"token punctuation\">;<\/span>\n<span class=\"token punctuation\">}<\/span>\nll <span class=\"token function\">getsum<\/span><span class=\"token punctuation\">(<\/span>ll k<span class=\"token punctuation\">)<\/span>\n<span class=\"token punctuation\">{<!-- --><\/span>\n    ll ans<span class=\"token operator\">=<\/span><span class=\"token number\">0<\/span><span class=\"token punctuation\">;<\/span>\n    <span class=\"token keyword\">for<\/span><span class=\"token punctuation\">(<\/span>ll i<span class=\"token operator\">=<\/span>k<span class=\"token punctuation\">;<\/span>i<span class=\"token operator\">>=<\/span><span class=\"token number\">1<\/span><span class=\"token punctuation\">;<\/span>i<span class=\"token operator\">-<\/span><span class=\"token operator\">=<\/span><span class=\"token function\">lowbit<\/span><span class=\"token punctuation\">(<\/span>i<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">)<\/span>\n        ans<span class=\"token operator\">+<\/span><span class=\"token operator\">=<\/span>c<span class=\"token punctuation\">[<\/span>i<span class=\"token punctuation\">]<\/span><span class=\"token punctuation\">;<\/span>\n    <span class=\"token keyword\">return<\/span> ans<span class=\"token punctuation\">;<\/span>\n<span class=\"token punctuation\">}<\/span>\n<span class=\"token keyword\">int<\/span> <span class=\"token function\">main<\/span><span class=\"token punctuation\">(<\/span><span class=\"token punctuation\">)<\/span>\n<span class=\"token punctuation\">{<!-- --><\/span>\n    <span class=\"token function\">scanf<\/span><span class=\"token punctuation\">(<\/span><span class=\"token string\">\"%lld\"<\/span><span class=\"token punctuation\">,<\/span><span class=\"token operator\">&<\/span>n<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">;<\/span>\n    <span class=\"token keyword\">for<\/span><span class=\"token punctuation\">(<\/span>ll i<span class=\"token operator\">=<\/span><span class=\"token number\">1<\/span><span class=\"token punctuation\">;<\/span>i<span class=\"token operator\"><=<\/span>n<span class=\"token punctuation\">;<\/span>i<span class=\"token operator\">++<\/span><span class=\"token punctuation\">)<\/span>\n    <span class=\"token punctuation\">{<!-- --><\/span>\n        <span class=\"token function\">scanf<\/span><span class=\"token punctuation\">(<\/span><span class=\"token string\">\"%lld\"<\/span><span class=\"token punctuation\">,<\/span><span class=\"token operator\">&<\/span>k<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">;<\/span>\n        <span class=\"token function\">add<\/span><span class=\"token punctuation\">(<\/span>k<span class=\"token punctuation\">,<\/span><span class=\"token number\">1<\/span><span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">;<\/span>\n        ans<span class=\"token operator\">+<\/span><span class=\"token operator\">=<\/span>i<span class=\"token operator\">-<\/span><span class=\"token function\">getsum<\/span><span class=\"token punctuation\">(<\/span>k<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">;<\/span>\n    <span class=\"token punctuation\">}<\/span>\n    <span class=\"token function\">printf<\/span><span class=\"token punctuation\">(<\/span><span class=\"token string\">\"%dn\"<\/span><span class=\"token punctuation\">,<\/span>ans<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">;<\/span>\n<span class=\"token punctuation\">}<\/span>\n<\/code><\/pre>\n<h4><a id=\"2_39\"><\/a>2.\u79bb\u6563\u5316+\u6811\u72b6\u6570\u7ec4\u6c42\u9006\u5e8f\u5bf9<\/h4>\n<p><a href=\"http:\/\/icpc.upc.edu.cn\/problem.php?cid=1422&#038;pid=3\">http:\/\/icpc.upc.edu.cn\/problem.php?cid=1422&#038;pid=3<\/a><\/p>\n<h6><a id=\"_41\"><\/a>\u9898\u76ee\u63cf\u8ff0<\/h6>\n<p>\u201c\u88c5\u6ee1\u4e86\u9e45\u5375\u77f3\u7684\u74f6\u5b50\u662f\u6ee1\u7684\u5417\uff1f\u201d\u58a8\u8001\u5e08\u66fe\u7ecf\u8fd9\u6837\u95ee\u8fc7\u4ed6\u7684\u5b66\u751f\u3002\u201c\u4e0d\u662f\uff0c\u56e0\u4e3a\u8fd8\u53ef\u4ee5\u653e\u5165\u5c0f\u77f3\u5b50\u3001\u518d\u653e\u5165\u7ec6\u7802\u3001\u6700\u540e\u518d\u5012\u5165\u6c34\u3002\u201d\u5b66\u751f\u4eec\u56de\u7b54\u3002\u201c\u90a3\u4e48\u4ece\u4e2d\u53ef\u4ee5\u5f97\u5230\u4ec0\u4e48\u542f\u793a\u5462\uff1f\u201d\u58a8\u8001\u5e08\u53c8\u95ee\uff0c\u201c\u542f\u793a\u6211\u4eec\u65f6\u95f4\u603b\u662f\u53ef\u4ee5\u6324\u51fa\u6765\u7684\uff01\u201d\u4e00\u4e2a\u806a\u660e\u7684\u5b66\u751f\u62a2\u7b54\u3002\u201c\u4f60\u8bf4\u5f97\u5bf9\uff01\u201d\u58a8\u8001\u5e08\u5fae\u7b11\u9053\uff0c\u201c\u4f46\u6211\u8fd8\u8981\u544a\u8bc9\u4f60\u4eec\u53e6\u4e00\u4e2a\u91cd\u8981\u7ecf\u9a8c\uff0c\u90a3\u5c31\u662f\uff1a\u5982\u679c\u4f60\u4e0d\u5148\u5c06\u5927\u7684\u9e45\u5375\u77f3\u653e\u8fdb\u74f6\u5b50\u91cc\u53bb\uff0c\u4f60\u4e5f\u8bb8\u4ee5\u540e\u6c38\u8fdc\u6ca1\u673a\u4f1a\u518d\u628a\u5b83\u4eec\u653e\u8fdb\u53bb\u4e86\u3002\u201d<\/p>\n<p>\u4f46\u8fd9\u4e16\u4e0a\u7684\u5f88\u591a\u4eba\uff0c\u505a\u4e8b\u5374\u7ecf\u5e38\u5206\u4e0d\u6e05\u4e8b\u60c5\u7684\u8f7b\u91cd\u7f13\u6025\u3002\u6211\u4eec\u53ef\u7231\u7684\u5178\u72f1\u957f\u5927\u4eba\u5c31\u72af\u4e86\u8fd9\u4e2a\u9519\u8bef\uff0c\u5f53\u4ed6\u770b\u5230\u8eab\u9ad8\u53c2\u5dee\u4e0d\u9f50\u7684\u72f1\u8b66\u4eec\u6392\u6210\u4e00\u5217\u65f6\uff0c\u7709\u6bdb\u62e7\u6210\u4e86\u4e00\u4e2a\u7ed3\uff0c\u4ed6\u6700\u60f3\u77e5\u9053\u7684\u5c31\u662f\uff0c\u5230\u5e95\u6709\u591a\u5c11\u4e2a\u72f1\u8b66\u9006\u5e8f\u6392\u961f\u4e86\u3002\u8fd9\u53ef\u4ee5\u62bd\u8c61\u4e3a\u6c42\u9006\u5e8f\u5bf9\u7684\u4e2a\u6570\u95ee\u9898\uff1a\u5373\u5bf9\u4e8e\u4e00\u4e2a\u5305\u542bn\u4e2a\u975e\u8d1f\u6574\u6570\u7684\u6570\u7ec4A[1\uff0c\u2026\uff0cn]\uff0c\u5982\u679c\u6709i < j\uff0c\u4e14A[ i ]>A[ j ]\uff0c\u5219\u79f0(A[ i] \uff0cA[ j] )\u4e3a\u6570\u7ec4A\u4e2d\u7684\u4e00\u4e2a\u9006\u5e8f\u5bf9\u3002<\/p>\n<p>\u4f8b\u5982\uff0c\u6570\u7ec4\uff083\uff0c1\uff0c4\uff0c5\uff0c2\uff09\u7684\u9006\u5e8f\u5bf9\u6709(3\uff0c1)\uff0c(3\uff0c2)\uff0c(4\uff0c2)\uff0c(5\uff0c2)\u51714\u4e2a\u3002<\/p>\n<h6><a id=\"_47\"><\/a>\u8f93\u5165<\/h6>\n<p>\u5305\u62ec\u4e24\u884c\uff0c\u7b2c\u4e00\u884c\u662f\u4e00\u4e2a\u6574\u6570n(1\u2264n\u22641000)\uff0c\u8868\u793a\u72f1\u8b66\u4eba\u6570\u3002\u7b2c\u4e8c\u884c\u5305\u542bn\u4e2a\u6574\u6570\uff0c\u7528\u7a7a\u683c\u5206\u9694\uff0c\u5373\u6bcf\u4e2a\u72f1\u8b66\u7684\u8eab\u9ad8\uff0c\u72f1\u8b66\u8eab\u9ad8\u5747\u5728int\u8303\u56f4\u5185\u3002<\/p>\n<h6><a id=\"_49\"><\/a>\u8f93\u51fa<\/h6>\n<p>\u5305\u62ec\u4e00\u884c\uff0c\u8fd9\u4e00\u884c\u53ea\u5305\u542b\u4e00\u4e2a\u6574\u6570\uff0c\u5373\u9006\u5e8f\u5bf9\u7684\u4e2a\u6570\u3002<\/p>\n<h6><a id=\"_51\"><\/a>\u6837\u4f8b\u8f93\u5165<\/h6>\n<pre><code>5\n3 1 4 5 2\n<\/code><\/pre>\n<h6><a id=\"_56\"><\/a>\u6837\u4f8b\u8f93\u51fa<\/h6>\n<pre><code>4\n<\/code><\/pre>\n<p>\u9996\u5148\u4ecb\u7ecd\u4e00\u4e0b\u79bb\u6563\u5316\uff0c\u79bb\u6563\u5316\u662f\u5728\u4e0d\u6539\u53d8\u6570\u636e\u76f8\u5bf9\u5927\u5c0f\u7684\u6761\u4ef6\u4e0b\uff0c\u5bf9\u6570\u636e\u8fdb\u884c\u76f8\u5e94\u7684\u7f29\u5c0f\u3002\u4f8b\u5982\uff1a\u539f\u6570\u636e\uff1a1,999,100000,15\uff1b\u5904\u7406\u540e\uff1a1,3,4,2\uff1b<br \/> \u8fd9\u6837\u7ecf\u8fc7\u79bb\u6563\u5316\u5904\u7406\u540e\u80fd\u591f\u51cf\u5c11\u6807\u8bb0\u6570\u7ec4\u7684\u8303\u56f4\uff0c\u51cf\u5c11\u65f6\u95f4\u590d\u6742\u5ea6<\/p>\n<pre><code class=\"prism language-cpp\"><span class=\"token macro property\">#<span class=\"token directive keyword\">include<\/span><span class=\"token string\"><bits\/stdc++.h><\/span><\/span>\n<span class=\"token keyword\">using<\/span> <span class=\"token keyword\">namespace<\/span> std<span class=\"token punctuation\">;<\/span>\n<span class=\"token keyword\">typedef<\/span> <span class=\"token keyword\">long<\/span> <span class=\"token keyword\">long<\/span> ll<span class=\"token punctuation\">;<\/span>\nll n<span class=\"token punctuation\">,<\/span>m<span class=\"token punctuation\">;<\/span>\n<span class=\"token keyword\">struct<\/span> node\n<span class=\"token punctuation\">{<!-- --><\/span>\n    ll x<span class=\"token punctuation\">;<\/span>\n    ll pos<span class=\"token punctuation\">;<\/span>\n<span class=\"token punctuation\">}<\/span><span class=\"token punctuation\">;<\/span>\nnode a<span class=\"token punctuation\">[<\/span><span class=\"token number\">100500<\/span><span class=\"token punctuation\">]<\/span><span class=\"token operator\">=<\/span><span class=\"token punctuation\">{<!-- --><\/span><span class=\"token number\">0<\/span><span class=\"token punctuation\">}<\/span><span class=\"token punctuation\">;<\/span>\nll b<span class=\"token punctuation\">[<\/span><span class=\"token number\">100500<\/span><span class=\"token punctuation\">]<\/span><span class=\"token operator\">=<\/span><span class=\"token punctuation\">{<!-- --><\/span><span class=\"token number\">0<\/span><span class=\"token punctuation\">}<\/span><span class=\"token punctuation\">;<\/span>\nll c<span class=\"token punctuation\">[<\/span><span class=\"token number\">100500<\/span><span class=\"token punctuation\">]<\/span><span class=\"token operator\">=<\/span><span class=\"token punctuation\">{<!-- --><\/span><span class=\"token number\">0<\/span><span class=\"token punctuation\">}<\/span><span class=\"token punctuation\">;<\/span>\nll maxn<span class=\"token operator\">=<\/span><span class=\"token number\">100005<\/span><span class=\"token punctuation\">,<\/span>k<span class=\"token punctuation\">,<\/span>ans<span class=\"token operator\">=<\/span><span class=\"token number\">0<\/span><span class=\"token punctuation\">;<\/span>\nll <span class=\"token function\">lowbit<\/span><span class=\"token punctuation\">(<\/span>ll x<span class=\"token punctuation\">)<\/span>\n<span class=\"token punctuation\">{<!-- --><\/span>\n    <span class=\"token keyword\">return<\/span> x<span class=\"token operator\">&<\/span><span class=\"token punctuation\">(<\/span><span class=\"token operator\">-<\/span>x<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">;<\/span>\n<span class=\"token punctuation\">}<\/span>\nll <span class=\"token function\">add<\/span><span class=\"token punctuation\">(<\/span>ll k<span class=\"token punctuation\">,<\/span>ll x<span class=\"token punctuation\">)<\/span>\n<span class=\"token punctuation\">{<!-- --><\/span>\n    <span class=\"token keyword\">for<\/span><span class=\"token punctuation\">(<\/span>ll i<span class=\"token operator\">=<\/span>k<span class=\"token punctuation\">;<\/span>i<span class=\"token operator\"><=<\/span>maxn<span class=\"token punctuation\">;<\/span>i<span class=\"token operator\">+<\/span><span class=\"token operator\">=<\/span><span class=\"token function\">lowbit<\/span><span class=\"token punctuation\">(<\/span>i<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">)<\/span>\n        c<span class=\"token punctuation\">[<\/span>i<span class=\"token punctuation\">]<\/span><span class=\"token operator\">+<\/span><span class=\"token operator\">=<\/span>x<span class=\"token punctuation\">;<\/span>\n<span class=\"token punctuation\">}<\/span>\nll <span class=\"token function\">getsum<\/span><span class=\"token punctuation\">(<\/span>ll k<span class=\"token punctuation\">)<\/span>\n<span class=\"token punctuation\">{<!-- --><\/span>\n    ll ans<span class=\"token operator\">=<\/span><span class=\"token number\">0<\/span><span class=\"token punctuation\">;<\/span>\n    <span class=\"token keyword\">for<\/span><span class=\"token punctuation\">(<\/span>ll i<span class=\"token operator\">=<\/span>k<span class=\"token punctuation\">;<\/span>i<span class=\"token operator\">>=<\/span><span class=\"token number\">1<\/span><span class=\"token punctuation\">;<\/span>i<span class=\"token operator\">-<\/span><span class=\"token operator\">=<\/span><span class=\"token function\">lowbit<\/span><span class=\"token punctuation\">(<\/span>i<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">)<\/span>\n        ans<span class=\"token operator\">+<\/span><span class=\"token operator\">=<\/span>c<span class=\"token punctuation\">[<\/span>i<span class=\"token punctuation\">]<\/span><span class=\"token punctuation\">;<\/span>\n    <span class=\"token keyword\">return<\/span> ans<span class=\"token punctuation\">;<\/span>\n<span class=\"token punctuation\">}<\/span>\n<span class=\"token keyword\">bool<\/span> <span class=\"token function\">cmp<\/span><span class=\"token punctuation\">(<\/span>node a<span class=\"token punctuation\">,<\/span>node b<span class=\"token punctuation\">)<\/span>\n<span class=\"token punctuation\">{<!-- --><\/span>\n    <span class=\"token keyword\">return<\/span> a<span class=\"token punctuation\">.<\/span>x<span class=\"token operator\"><<\/span>b<span class=\"token punctuation\">.<\/span>x<span class=\"token punctuation\">;<\/span>\n<span class=\"token punctuation\">}<\/span>\n<span class=\"token keyword\">int<\/span> <span class=\"token function\">main<\/span><span class=\"token punctuation\">(<\/span><span class=\"token punctuation\">)<\/span>\n<span class=\"token punctuation\">{<!-- --><\/span>\n    <span class=\"token function\">scanf<\/span><span class=\"token punctuation\">(<\/span><span class=\"token string\">\"%lld\"<\/span><span class=\"token punctuation\">,<\/span><span class=\"token operator\">&<\/span>n<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">;<\/span>\n    <span class=\"token keyword\">for<\/span><span class=\"token punctuation\">(<\/span>ll i<span class=\"token operator\">=<\/span><span class=\"token number\">1<\/span><span class=\"token punctuation\">;<\/span>i<span class=\"token operator\"><=<\/span>n<span class=\"token punctuation\">;<\/span>i<span class=\"token operator\">++<\/span><span class=\"token punctuation\">)<\/span>\n    <span class=\"token punctuation\">{<!-- --><\/span>\n        <span class=\"token function\">scanf<\/span><span class=\"token punctuation\">(<\/span><span class=\"token string\">\"%lld\"<\/span><span class=\"token punctuation\">,<\/span><span class=\"token operator\">&<\/span>a<span class=\"token punctuation\">[<\/span>i<span class=\"token punctuation\">]<\/span><span class=\"token punctuation\">.<\/span>x<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">;<\/span>\n        a<span class=\"token punctuation\">[<\/span>i<span class=\"token punctuation\">]<\/span><span class=\"token punctuation\">.<\/span>pos<span class=\"token operator\">=<\/span>i<span class=\"token punctuation\">;<\/span>\n    <span class=\"token punctuation\">}<\/span>\n    <span class=\"token function\">sort<\/span><span class=\"token punctuation\">(<\/span>a<span class=\"token operator\">+<\/span><span class=\"token number\">1<\/span><span class=\"token punctuation\">,<\/span>a<span class=\"token operator\">+<\/span>n<span class=\"token operator\">+<\/span><span class=\"token number\">1<\/span><span class=\"token punctuation\">,<\/span>cmp<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">;<\/span>\n    ll cnt<span class=\"token operator\">=<\/span><span class=\"token number\">1<\/span><span class=\"token punctuation\">;<\/span>\n    <span class=\"token keyword\">for<\/span><span class=\"token punctuation\">(<\/span>ll i<span class=\"token operator\">=<\/span><span class=\"token number\">1<\/span><span class=\"token punctuation\">;<\/span>i<span class=\"token operator\"><=<\/span>n<span class=\"token punctuation\">;<\/span>i<span class=\"token operator\">++<\/span><span class=\"token punctuation\">)<\/span>\n    <span class=\"token punctuation\">{<!-- --><\/span>\n        <span class=\"token keyword\">if<\/span><span class=\"token punctuation\">(<\/span>i<span class=\"token operator\">!=<\/span><span class=\"token number\">1<\/span><span class=\"token operator\">&&<\/span>a<span class=\"token punctuation\">[<\/span>i<span class=\"token punctuation\">]<\/span><span class=\"token punctuation\">.<\/span>x<span class=\"token operator\">!=<\/span>a<span class=\"token punctuation\">[<\/span>i<span class=\"token operator\">-<\/span><span class=\"token number\">1<\/span><span class=\"token punctuation\">]<\/span><span class=\"token punctuation\">.<\/span>x<span class=\"token punctuation\">)<\/span>\n            cnt<span class=\"token operator\">++<\/span><span class=\"token punctuation\">;<\/span>\n        b<span class=\"token punctuation\">[<\/span>a<span class=\"token punctuation\">[<\/span>i<span class=\"token punctuation\">]<\/span><span class=\"token punctuation\">.<\/span>pos<span class=\"token punctuation\">]<\/span><span class=\"token operator\">=<\/span>cnt<span class=\"token punctuation\">;<\/span>\n    <span class=\"token punctuation\">}<\/span>\n    <span class=\"token keyword\">for<\/span><span class=\"token punctuation\">(<\/span>ll i<span class=\"token operator\">=<\/span><span class=\"token number\">1<\/span><span class=\"token punctuation\">;<\/span>i<span class=\"token operator\"><=<\/span>n<span class=\"token punctuation\">;<\/span>i<span class=\"token operator\">++<\/span><span class=\"token punctuation\">)<\/span>\n    <span class=\"token punctuation\">{<!-- --><\/span>\n        <span class=\"token function\">add<\/span><span class=\"token punctuation\">(<\/span>b<span class=\"token punctuation\">[<\/span>i<span class=\"token punctuation\">]<\/span><span class=\"token punctuation\">,<\/span><span class=\"token number\">1<\/span><span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">;<\/span>\n        ans<span class=\"token operator\">+<\/span><span class=\"token operator\">=<\/span>i<span class=\"token operator\">-<\/span><span class=\"token function\">getsum<\/span><span class=\"token punctuation\">(<\/span>b<span class=\"token punctuation\">[<\/span>i<span class=\"token punctuation\">]<\/span><span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">;<\/span>\n    <span class=\"token punctuation\">}<\/span>\n    <span class=\"token function\">printf<\/span><span class=\"token punctuation\">(<\/span><span class=\"token string\">\"%lldn\"<\/span><span class=\"token punctuation\">,<\/span>ans<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">;<\/span>\n<span class=\"token punctuation\">}<\/span>\n<\/code><\/pre>\n<h4><a id=\"3_121\"><\/a>3.\u5f52\u5e76\u6392\u5e8f\u6c42\u9006\u5e8f\u5bf9<\/h4>\n<p><a href=\"http:\/\/icpc.upc.edu.cn\/problem.php?cid=2436&#038;pid=0\">http:\/\/icpc.upc.edu.cn\/problem.php?cid=2436&#038;pid=0<\/a><\/p>\n<h6><a id=\"_123\"><\/a>\u9898\u76ee\u63cf\u8ff0<\/h6>\n<p>\u67d0\u6b63\u6559\u6388\u7ea7\u7279\u7ea7\u6559\u5e08\u83b7\u5f97\u4e86\u4e00\u6bb5\u53e4\u8001\u7684\u6587\u5b57\uff0c\u5168\u90e8\u7531 26 \u4e2a\u5927\u5199\u82f1\u6587\u5b57\u6bcd\u7ec4\u6210\u3002\u4ed6\u4ea7\u751f\u4e86\u4e00\u4e2a\u75af\u72c2\u7684\u60f3\u6cd5\uff0c\u5373\u60f3\u628a\u8fd9\u6bb5\u6587\u5b57\u4e2d\u6240\u6709\u5b57\u6bcd\u6309 A \u5230 Z \u7684\u987a\u5e8f\u6392\u5e8f\uff0c\u5373\u6240\u6709 A \u653e\u5728\u5f00\u5934\uff0c\u7136\u540e\u8ddf\u7740\u6240\u6709 B\uff0c\u518d\u662f\u6240\u6709 C\uff0c\u6700\u540e\u662f\u6240\u6709 Z\u3002\u6bd4\u5982\u539f<br \/> \u5b57\u7b26\u4e32\u4e3a\u201cHELLOWORLD\u201d\uff0c\u6392\u5e8f\u540e\u5e94\u53d8\u4e3a\u201cDEHLLLOORW\u201d\u3002\u4f46\u662f\u7279\u6559\u6bd5\u7adf\u9886\u7740\u56fd\u52a1\u9662\u7684\u7279\u6b8a\u6d25\u8d34\uff0c\u4e8e\u662f\u4ed6\u8fd8\u6709\u4e00\u4e2a\u8981\u6c42\uff0c\u5373\u6392\u5e8f\u65f6\u6bcf\u6b21\u53ea\u80fd\u4ea4\u6362\u76f8\u90bb\u4e24\u4e2a\u5b57\u6bcd\u3002\u73b0\u5728\u4ed6\u60f3\u77e5\u9053\u6700\u5c11\u4ea4\u6362\u591a\u5c11\u6b21\u80fd\u5b8c\u6210\u6392\u5e8f\uff1f<\/p>\n<h6><a id=\"_126\"><\/a>\u8f93\u5165<\/h6>\n<p>\u4ec5\u4e00\u884c\uff0c\u5305\u542b\u4e00\u4e2a\u4ec5\u542b\u5927\u5199\u5b57\u6bcd\u7684\u957f\u5ea6\u4e3a L \u7684\u5b57\u7b26\u4e32\uff08\u6ce8\u610f L \u4e0d\u8f93\u5165\uff09\u3002<\/p>\n<h6><a id=\"_128\"><\/a>\u8f93\u51fa<\/h6>\n<p>\u5171\u4e00\u884c\uff0c\u5305\u542b\u4e00\u4e2a\u6574\u6570\u8868\u793a\u6700\u5c11\u4ea4\u6362\u6b21\u6570\u3002<\/p>\n<h6><a id=\"_130\"><\/a>\u6837\u4f8b\u8f93\u5165<\/h6>\n<p>\u3010\u6837\u4f8b1\u3011<br \/> LSDSL<br \/> \u3010\u6837\u4f8b2\u3011<br \/> HELLOWORLD<\/p>\n<h6><a id=\"_135\"><\/a>\u6837\u4f8b\u8f93\u51fa<\/h6>\n<p>\u3010\u6837\u4f8b1\u3011<br \/> 4<br \/> \u3010\u6837\u4f8b2\u3011<br \/> 16<\/p>\n<h6><a id=\"_140\"><\/a>\u63d0\u793a<\/h6>\n<p>\u5bf9\u4e8e50%\u7684\u6570\u636e\uff0c1\u2264L\u22642000\uff1b<br \/> \u5bf9\u4e8e100%\u7684\u6570\u636e\uff0c1\u2264L\u22642\u00d710^6<\/p>\n<p>\u501f\u7528\u5f52\u5e76\u6392\u5e8f\u6765\u6c42\u9006\u5e8f\u5bf9<\/p>\n<pre><code class=\"prism language-cpp\"><span class=\"token macro property\">#<span class=\"token directive keyword\">include<\/span> <span class=\"token string\"><iostream><\/span><\/span>\n<span class=\"token macro property\">#<span class=\"token directive keyword\">include<\/span> <span class=\"token string\"><bits\/stdc++.h><\/span><\/span>\n<span class=\"token keyword\">using<\/span> <span class=\"token keyword\">namespace<\/span> std<span class=\"token punctuation\">;<\/span>\n<span class=\"token keyword\">char<\/span> a1<span class=\"token punctuation\">[<\/span><span class=\"token number\">2005000<\/span><span class=\"token punctuation\">]<\/span><span class=\"token operator\">=<\/span><span class=\"token string\">\"\"<\/span><span class=\"token punctuation\">;<\/span>\n<span class=\"token keyword\">int<\/span> a<span class=\"token punctuation\">[<\/span><span class=\"token number\">2005000<\/span><span class=\"token punctuation\">]<\/span><span class=\"token operator\">=<\/span> <span class=\"token punctuation\">{<!-- --><\/span><span class=\"token number\">0<\/span><span class=\"token punctuation\">}<\/span><span class=\"token punctuation\">;<\/span>\n<span class=\"token keyword\">int<\/span> b<span class=\"token punctuation\">[<\/span><span class=\"token number\">2005000<\/span><span class=\"token punctuation\">]<\/span><span class=\"token operator\">=<\/span> <span class=\"token punctuation\">{<!-- --><\/span><span class=\"token number\">0<\/span><span class=\"token punctuation\">}<\/span><span class=\"token punctuation\">;<\/span>\n<span class=\"token keyword\">long<\/span> <span class=\"token keyword\">long<\/span> <span class=\"token keyword\">int<\/span> <span class=\"token function\">merge_sort<\/span><span class=\"token punctuation\">(<\/span><span class=\"token keyword\">long<\/span> <span class=\"token keyword\">long<\/span> <span class=\"token keyword\">int<\/span> l<span class=\"token punctuation\">,<\/span><span class=\"token keyword\">long<\/span> <span class=\"token keyword\">long<\/span> <span class=\"token keyword\">int<\/span> r<span class=\"token punctuation\">)<\/span>\n<span class=\"token punctuation\">{<!-- --><\/span>\n    <span class=\"token keyword\">if<\/span> <span class=\"token punctuation\">(<\/span>l <span class=\"token operator\">>=<\/span> r<span class=\"token punctuation\">)<\/span>\n        <span class=\"token keyword\">return<\/span> <span class=\"token number\">0<\/span><span class=\"token punctuation\">;<\/span>\n    <span class=\"token keyword\">long<\/span> <span class=\"token keyword\">long<\/span> <span class=\"token keyword\">int<\/span> mid <span class=\"token operator\">=<\/span> <span class=\"token punctuation\">(<\/span>l <span class=\"token operator\">+<\/span> r<span class=\"token punctuation\">)<\/span> <span class=\"token operator\">>><\/span> <span class=\"token number\">1<\/span><span class=\"token punctuation\">,<\/span> res <span class=\"token operator\">=<\/span> <span class=\"token number\">0<\/span><span class=\"token punctuation\">;<\/span>\n    res <span class=\"token operator\">+<\/span><span class=\"token operator\">=<\/span> <span class=\"token function\">merge_sort<\/span><span class=\"token punctuation\">(<\/span>l<span class=\"token punctuation\">,<\/span> mid<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">;<\/span>\n    res <span class=\"token operator\">+<\/span><span class=\"token operator\">=<\/span> <span class=\"token function\">merge_sort<\/span><span class=\"token punctuation\">(<\/span>mid <span class=\"token operator\">+<\/span> <span class=\"token number\">1<\/span><span class=\"token punctuation\">,<\/span> r<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">;<\/span>\n    <span class=\"token keyword\">long<\/span> <span class=\"token keyword\">long<\/span> <span class=\"token keyword\">int<\/span> i <span class=\"token operator\">=<\/span> l<span class=\"token punctuation\">,<\/span> j <span class=\"token operator\">=<\/span> mid <span class=\"token operator\">+<\/span> <span class=\"token number\">1<\/span><span class=\"token punctuation\">,<\/span> cnt <span class=\"token operator\">=<\/span> <span class=\"token number\">0<\/span><span class=\"token punctuation\">;<\/span>\n    <span class=\"token keyword\">while<\/span> <span class=\"token punctuation\">(<\/span>i <span class=\"token operator\"><=<\/span> mid <span class=\"token operator\">&&<\/span> j <span class=\"token operator\"><=<\/span> r<span class=\"token punctuation\">)<\/span>\n        <span class=\"token keyword\">if<\/span> <span class=\"token punctuation\">(<\/span>a<span class=\"token punctuation\">[<\/span>i<span class=\"token punctuation\">]<\/span> <span class=\"token operator\"><=<\/span> a<span class=\"token punctuation\">[<\/span>j<span class=\"token punctuation\">]<\/span><span class=\"token punctuation\">)<\/span>\n            b<span class=\"token punctuation\">[<\/span>cnt<span class=\"token operator\">++<\/span><span class=\"token punctuation\">]<\/span> <span class=\"token operator\">=<\/span> a<span class=\"token punctuation\">[<\/span>i<span class=\"token operator\">++<\/span><span class=\"token punctuation\">]<\/span><span class=\"token punctuation\">;<\/span>\n        <span class=\"token keyword\">else<\/span>\n        <span class=\"token punctuation\">{<!-- --><\/span>\n            res <span class=\"token operator\">+<\/span><span class=\"token operator\">=<\/span> mid <span class=\"token operator\">-<\/span> i <span class=\"token operator\">+<\/span> <span class=\"token number\">1<\/span><span class=\"token punctuation\">;<\/span>\n            b<span class=\"token punctuation\">[<\/span>cnt<span class=\"token operator\">++<\/span><span class=\"token punctuation\">]<\/span> <span class=\"token operator\">=<\/span> a<span class=\"token punctuation\">[<\/span>j<span class=\"token operator\">++<\/span><span class=\"token punctuation\">]<\/span><span class=\"token punctuation\">;<\/span>\n        <span class=\"token punctuation\">}<\/span>\n    <span class=\"token keyword\">while<\/span> <span class=\"token punctuation\">(<\/span>i <span class=\"token operator\"><=<\/span> mid<span class=\"token punctuation\">)<\/span>\n        b<span class=\"token punctuation\">[<\/span>cnt<span class=\"token operator\">++<\/span><span class=\"token punctuation\">]<\/span> <span class=\"token operator\">=<\/span> a<span class=\"token punctuation\">[<\/span>i<span class=\"token operator\">++<\/span><span class=\"token punctuation\">]<\/span><span class=\"token punctuation\">;<\/span>\n    <span class=\"token keyword\">while<\/span> <span class=\"token punctuation\">(<\/span>j <span class=\"token operator\"><=<\/span> r<span class=\"token punctuation\">)<\/span>\n        b<span class=\"token punctuation\">[<\/span>cnt<span class=\"token operator\">++<\/span><span class=\"token punctuation\">]<\/span> <span class=\"token operator\">=<\/span> a<span class=\"token punctuation\">[<\/span>j<span class=\"token operator\">++<\/span><span class=\"token punctuation\">]<\/span><span class=\"token punctuation\">;<\/span>\n    <span class=\"token keyword\">for<\/span> <span class=\"token punctuation\">(<\/span><span class=\"token keyword\">long<\/span> <span class=\"token keyword\">long<\/span> <span class=\"token keyword\">int<\/span> i <span class=\"token operator\">=<\/span> l<span class=\"token punctuation\">,<\/span> j <span class=\"token operator\">=<\/span> <span class=\"token number\">0<\/span><span class=\"token punctuation\">;<\/span> j <span class=\"token operator\"><<\/span> cnt<span class=\"token punctuation\">;<\/span> <span class=\"token operator\">++<\/span>i<span class=\"token punctuation\">,<\/span> <span class=\"token operator\">++<\/span>j<span class=\"token punctuation\">)<\/span>\n        a<span class=\"token punctuation\">[<\/span>i<span class=\"token punctuation\">]<\/span> <span class=\"token operator\">=<\/span> b<span class=\"token punctuation\">[<\/span>j<span class=\"token punctuation\">]<\/span><span class=\"token punctuation\">;<\/span>\n    <span class=\"token keyword\">return<\/span> res<span class=\"token punctuation\">;<\/span>\n<span class=\"token punctuation\">}<\/span>\n<span class=\"token keyword\">int<\/span> <span class=\"token function\">main<\/span><span class=\"token punctuation\">(<\/span><span class=\"token punctuation\">)<\/span>\n<span class=\"token punctuation\">{<!-- --><\/span>\n    <span class=\"token function\">scanf<\/span><span class=\"token punctuation\">(<\/span><span class=\"token string\">\"%s\"<\/span><span class=\"token punctuation\">,<\/span>a1<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">;<\/span>\n    <span class=\"token keyword\">for<\/span><span class=\"token punctuation\">(<\/span><span class=\"token keyword\">long<\/span> <span class=\"token keyword\">long<\/span> <span class=\"token keyword\">int<\/span> i<span class=\"token operator\">=<\/span><span class=\"token number\">0<\/span><span class=\"token punctuation\">;<\/span> a1<span class=\"token punctuation\">[<\/span>i<span class=\"token punctuation\">]<\/span><span class=\"token punctuation\">;<\/span> i<span class=\"token operator\">++<\/span><span class=\"token punctuation\">)<\/span>\n    <span class=\"token punctuation\">{<!-- --><\/span>\n        a<span class=\"token punctuation\">[<\/span>i<span class=\"token punctuation\">]<\/span><span class=\"token operator\">=<\/span>a1<span class=\"token punctuation\">[<\/span>i<span class=\"token punctuation\">]<\/span><span class=\"token operator\">-<\/span><span class=\"token string\">'a'<\/span><span class=\"token punctuation\">;<\/span>\n    <span class=\"token punctuation\">}<\/span>\n    <span class=\"token keyword\">long<\/span> <span class=\"token keyword\">long<\/span> <span class=\"token keyword\">int<\/span> sum<span class=\"token operator\">=<\/span><span class=\"token function\">merge_sort<\/span><span class=\"token punctuation\">(<\/span><span class=\"token number\">0<\/span><span class=\"token punctuation\">,<\/span><span class=\"token function\">strlen<\/span><span class=\"token punctuation\">(<\/span>a1<span class=\"token punctuation\">)<\/span><span class=\"token operator\">-<\/span><span class=\"token number\">1<\/span><span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">;<\/span>\n    cout<span class=\"token operator\"><<<\/span>sum<span class=\"token operator\"><<<\/span>endl<span class=\"token punctuation\">;<\/span>\n    <span class=\"token keyword\">return<\/span> <span class=\"token number\">0<\/span><span class=\"token punctuation\">;<\/span>\n<span class=\"token punctuation\">}<\/span>\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>1.\u6811\u72b6\u6570\u7ec4\u76f4\u63a5\u6c42\u9006\u5e8f\u5bf9 \u91c7\u7528\u6811\u72b6\u6570\u7ec4\u6807\u8bb0\u6765\u6c42\u9006\u5e8f&hellip;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-45","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts\/45","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/comments?post=45"}],"version-history":[{"count":0,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts\/45\/revisions"}],"wp:attachment":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/media?parent=45"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/categories?post=45"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/tags?post=45"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}