{"id":1072,"date":"2014-11-09T06:53:05","date_gmt":"2014-11-08T22:53:05","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=1072"},"modified":"2014-11-09T11:39:32","modified_gmt":"2014-11-09T03:39:32","slug":"vijos-1893-%e7%ad%be%e5%88%b0%e9%a2%98","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/vijos-1893-%e7%ad%be%e5%88%b0%e9%a2%98\/","title":{"rendered":"Vijos 1893. \u7b7e\u5230\u9898"},"content":{"rendered":"<h3>Brief description:<\/h3>\n<p>\u7ed9\u5b9a\u4e00\u4e2a\u6570\u7ec4\uff0c\u4f60\u5fc5\u987b\u4ea4\u6362\u5176\u4e2d\u7684\u4e24\u4e2a\u6570\uff0c\u6700\u5c0f\u5316\u9006\u5e8f\u5bf9\u6570\u3002\u3002<\/p>\n<p><a href=\"https:\/\/vijos.org\/p\/1893\">https:\/\/vijos.org\/p\/1893<\/a><\/p>\n<p><!--more--><\/p>\n<h3>Analysis:<\/h3>\n<p>\u9898\u76ee\u6765\u6e90\uff1a<a href=\"http:\/\/www.ioi-jp.org\/joi\/2012\/2013-ho\/\">http:\/\/www.ioi-jp.org\/joi\/2012\/2013-ho\/<\/a><br \/>\n\u95ee\u9898 5\uff1a<a href=\"http:\/\/www.ioi-jp.org\/joi\/2012\/2013-ho\/2013-ho-t5-review.pdf\">http:\/\/www.ioi-jp.org\/joi\/2012\/2013-ho\/2013-ho-t5-review.pdf<\/a><\/p>\n<p>\u79bb\u7ebf + \u7ebf\u6bb5\u6811\u3002<br \/>\n\u8981\u70b9\u662f\u6570\u5f62\u7ed3\u5408\u3002\u3002\u4e00\u56fe\u6d41\uff1a<\/p>\n<p><a target=\"_blank\" href=\"https:\/\/www.shuizilong.com\/house\/wp-content\/uploads\/2014\/11\/1.jpg\"><img decoding=\"async\" class=\"aligncenter size-full\" title=\"3\" src=\"https:\/\/www.shuizilong.com\/house\/wp-content\/uploads\/2014\/11\/1.jpg\" alt=\"\"\/><\/a><\/p>\n<p>\u3002\u3002\u3002\u4ea4\u6362\u4e24\u4e2a\u6570\uff08\u524d\u8005\u6bd4\u540e\u8005\u5927\uff09\u6240\u83b7\u5f97\u7684\u6536\u76ca\u3002\u3002\u662f 2*\u77e9\u5f62\u4e2d\u7684\u9762\u79ef\uff09+ 1*\u8fb9\u754c\u7684\u9762\u79ef + 1\u3002\u3002\u3002\uff08\u5148\u4e0d\u8003\u8651\u8fb9\u754c\uff09\u3002\u3002<\/p>\n<p>\u95ee\u9898\u73b0\u5728\u4fbf\u8f6c\u5316\u4e3a\u68c0\u67e5\u8fd9\u4e9b\u6781\u5927\u5b50\u77e9\u5f62\u3002\u3002\u3002<\/p>\n<p>\u4ec0\u4e48\u662f\u6781\u5927\u5b50\u77e9\u5f62\u5462\uff1f\u518d\u6765\u4e00\u5f20\u56fe\uff1a<\/p>\n<p><a target=\"_blank\" href=\"https:\/\/www.shuizilong.com\/house\/wp-content\/uploads\/2014\/11\/2.jpg\"><img decoding=\"async\" class=\"aligncenter size-full\" title=\"3\" src=\"https:\/\/www.shuizilong.com\/house\/wp-content\/uploads\/2014\/11\/2.jpg\" alt=\"\"\/><\/a><\/p>\n<p>\u6781\u5927\u5b50\u77e9\u5f62\u4e00\u5b9a\u662f\u67d0\u4e2a\u8d64\u70b9\u548c\u53f3\u4e0b\u89d2\u7684\u67d0\u4e2a\u9752\u70b9\u6240\u7ec4\u6210\u7684\u56fe\u5f62\u3002\u3002\u3002<br \/>\n\u4e8e\u662f\u6211\u4eec\u5c06\u70b9\u96c6\uff08\u4e8b\u4ef6\uff09\u5206\u6210\u4e09\u7c7b\u3002\u3002\u8d64\u70b9\u548c\u84dd\u70b9\u90fd\u5355\u8c03\u9012\u589e\u3002\u3002\u56e0\u6b64\u4ece\u5de6\u5230\u53f3\u626b\u63cf\u7ebf\u3002\u3001\u3001\u8bb0\u5f55\u6bcf\u4e2a\u4e8b\u4ef6\u79bb\u6563\u5316\u540e\u7684\u7eb5\u5750\u6807\u3002\u3002<\/p>\n<ul>\n<li>\u8d64\u70b9\uff08\u5de6\u4e0a\u89d2\uff09\uff1a\u3002\u3002\u3002\u5728\u7ebf\u6bb5\u6811\u4e2d\u6fc0\u6d3b\u8fd9\u4e2a\u5750\u6807\u3002\u3002<\/li>\n<li>\u9ed1\u70b9\uff08\u5176\u4ed6\uff09\uff1a\u3002\u3002\u52a0\u5165\u8fd9\u4e2a\u4e8b\u4ef6\u3002\u3002\u5c06\u7ebf\u6bb5\u6811\u4e2d\u8fd9\u4e2a\u70b9\u5750\u6807\u5230\u6700\u8fd1\u6fc0\u6d3b\u8d64\u70b9 += 2.\u3002\u3002\n<li>\u9752\u70b9\uff08\u53f3\u4e0b\u89d2\uff09\uff1a\u3002\u3002\u3002\u5f39\u51fa\u6240\u6709\u7eb5\u5750\u6807\u5c0f\u4e8e\u5b83\u7684\u9ed1\u70b9\uff08\u4f18\u5148\u961f\u5217\u7ef4\u62a4\uff09\u3002\u3002\u533a\u95f4\u6c42\u6700\u503c\u3002\u3002\u3002\n<\/ul>\n<p>\u53ea\u9700\u8981\u533a\u95f4\u52a0\u51cf\uff0c\u533a\u95f4\u6c42\u6700\u503c\u3002\u3002\u7ebf\u6bb5\u6811\u5373\u53ef\u3002\u3002\u3002<br \/>\n\u6700\u540e\u8fd8\u8981\u8ba8\u8bba\u5404\u79cd\u8fb9\u754c\u7684\u60c5\u51b5\u3002\u3002\u3002<br \/>\n\u5047\u8bbe\u6240\u6709\u6570\u90fd\u4e00\u6837\u3002\u3002\u8fd4\u56de 0 \u3002\u3002\u3002\u5426\u5219\u6c42\u51fa\u521d\u59cb\u7684\u9006\u5e8f\u5bf9 init_ans\u3002\u3002\u5982\u679c\u5b58\u5728\u4e24\u4e2a\u6570\u76f8\u7b49\u3002\u90a3\u4e48\u521d\u59cb\u7b54\u6848\u662f init_ans\u3002\u3002\u5426\u5219\u662f init_ans &#8211; 1\u3002\u3002<\/p>\n<p>\u518d\u8ba8\u8bba\u77e9\u5f62\u7684\u8fb9\u754c\u95ee\u9898\uff1a<br \/>\n\u5bf9\u4e8e\u4e0a\u8fb9\u754c\uff1a<br \/>\n\u3002\u3002\u5f53\u63d2\u5165\u4e00\u4e2a\u9ed1\u70b9\u65f6\u3002\u3002\u5b9e\u9645\u548c\u8fd9\u4e2a\u9ed1\u70b9\u76f8\u7b49\u7684\u90a3\u4e2a\u5750\u6807\u53ea\u80fd += 1\u3002\u3002\u3002<br \/>\n\u5bf9\u4e8e\u4e0b\u8fb9\u754c\uff1a<br \/>\n\u3002\u3002\u5f53\u51fa\u73b0\u9752\u70b9\u65f6\u3002\u4e0d\u4ec5\u8981\u5f39\u51fa\u6240\u6709\u5c0f\u4e8e\u5b83\u7684\u9ed1\u70b9\u3002\u3002\u8fd8\u8981\u3010\u6d88\u5f31\u3011\u7b49\u4e8e\u5b83\u7684\u9ed1\u70b9 -= 1\u3002\u3002\u3002<\/p>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n\r\n\/\/}\/* .................................................................................................................................. *\/\r\n\r\nconst int N = int(1e5) + 9;\r\nint a&#x5B;N]; VI P; bool red&#x5B;N], blue&#x5B;N];\r\nint n;\r\n\r\nnamespace ST{\r\n#define lx (x&lt;&lt;1)\r\n#define rx (lx|1)\r\n#define ml (l+r&gt;&gt;1)\r\n#define mr (ml+1)\r\n#define lc lx, l, ml\r\n#define rc rx, mr, r\r\n#define rt 1, 1, P.size()\r\n\r\n\r\n    int T&#x5B;4*N], D&#x5B;4*N], a, b, d, ll, rr;\r\n\r\n    void upd(int x){\r\n        T&#x5B;x] = max(T&#x5B;lx], T&#x5B;rx]);\r\n    }\r\n\r\n    void inc(int x, int d){\r\n        D&#x5B;x] += d;\r\n        T&#x5B;x] += d;\r\n    }\r\n\r\n    void rls(int x){\r\n        if (D&#x5B;x]){\r\n            inc(lx, D&#x5B;x]), inc(rx, D&#x5B;x]);\r\n            D&#x5B;x] = 0;\r\n        }\r\n    }\r\n\r\n    void add(int x, int l, int r){\r\n        if (b &lt; l || r &lt; a) return;\r\n        if (a &lt;= l &amp;&amp; r &lt;= b){\r\n            inc(x, d);\r\n        }\r\n        else{\r\n            rls(x);\r\n            add(lc); add(rc);\r\n            upd(x);\r\n        }\r\n    }\r\n\r\n    void Add(int _a, int _b, int _d){\r\n        a = _a, b = _b, d = _d; add(rt);\r\n    }\r\n\r\n    int query(int x, int l, int r){\r\n        if (b &lt; l || r &lt; a) return 0;\r\n        if (a &lt;= l &amp;&amp; r &lt;= b){\r\n            return T&#x5B;x];\r\n        }\r\n        else{\r\n            rls(x);\r\n            return max(query(lc), query(rc));\r\n        }\r\n    }\r\n\r\n    int query(){\r\n        a = ll+1, b = rr; int z = a &lt;= b ? query(rt) : 0; ++z;\r\n        return z;\r\n    }\r\n}\r\n\r\nnamespace BIT{\r\n    int C&#x5B;N], n;\r\n    int Sum(int x){\r\n        int z=0; for (;x;x^=low_bit(x)) z += C&#x5B;x];\r\n        return z;\r\n    }\r\n    void Add(int x, int d){\r\n        for(;x&lt;=n;x+=low_bit(x)) C&#x5B;x] += d;\r\n    }\r\n    int Sum(int l, int r){\r\n        return Sum(r) - Sum(l-1);\r\n    }\r\n} \/\/using namespace BIT;\r\n\r\n\r\nstruct black{\r\n    int l, r;\r\n    black(int _l, int _r):l(_l),r(_r){\r\n    }\r\n    bool operator &lt;(const black&amp; rhs) const{\r\n        return l &lt; rhs.l;\r\n    }\r\n    bool operator &gt;(const black&amp; rhs) const{\r\n        return l &gt; rhs.l;\r\n    }\r\n    void add() const{\r\n        ST::Add(l, r, 2);\r\n        ST::Add(l, l, -1);\r\n    }\r\n    void del() const{\r\n        ST::Add(l, r, -2);\r\n    }\r\n    void weak() const{\r\n        ST::Add(l, r, -1);\r\n    }\r\n};\r\n\r\npriority_queue&lt;black, vector&lt;black&gt;, greater&lt;black&gt; &gt; Q;\r\n\r\nint main(){\r\n\r\n#ifndef ONLINE_JUDGE\r\n    freopen(&quot;in.txt&quot;, &quot;r&quot;, stdin);\r\n    \/\/freopen(&quot;out.txt&quot;, &quot;w&quot;, stdout);\r\n#endif\r\n\r\n    REP_C(i, RD(n)) P.PB(RD(a&#x5B;i])); UNQ(P);\r\n\r\n    BIT::n = P.size();\r\n\r\n    LL init_ans = 0; bool same = 0, all_same = 1; REP(i, n){\r\n        a&#x5B;i] = LBD(P, a&#x5B;i])+1;\r\n        init_ans += i - BIT::Sum(a&#x5B;i]);\r\n        same |= (BIT::Sum(a&#x5B;i]) - BIT::Sum(a&#x5B;i]-1));\r\n        all_same &amp;= (!i || a&#x5B;i] == a&#x5B;i-1]);\r\n        BIT::Add(a&#x5B;i], 1);\r\n    }\r\n\r\n    if (all_same){\r\n        puts(&quot;0&quot;);\r\n        exit(0);\r\n    }\r\n\r\n    LL ans = init_ans + 1; if (same) --ans;\r\n\r\n    int t = 0; REP(i, n){\r\n        red&#x5B;i] = checkMax(t, a&#x5B;i]);\r\n    }\r\n\r\n    t = INF; DWN(i, n, 0){\r\n        blue&#x5B;i] = checkMin(t, a&#x5B;i]);\r\n    }\r\n\r\n    ST::ll = 0, ST::rr = -1;\r\n\r\n    REP(i, n){\r\n        if (red&#x5B;i]){\r\n            ST::rr = a&#x5B;i];\r\n        }\r\n        else if (blue&#x5B;i]){\r\n\r\n            while (!Q.empty() &amp;&amp; Q.top().l &lt; a&#x5B;i]){\r\n                Q.top().del();\r\n                Q.pop();\r\n            }\r\n\r\n            vector&lt;black&gt; QQ;\r\n\r\n            while (!Q.empty() &amp;&amp; Q.top().l == a&#x5B;i]){\r\n                Q.top().weak(); QQ.PB(Q.top()); Q.pop();\r\n            }\r\n            ST::ll = a&#x5B;i];\r\n            checkMin(ans, init_ans - (ST::query()));\r\n            ECH(it, QQ) it-&gt;weak();\r\n        }\r\n        else{\r\n            black t = black(a&#x5B;i], ST::rr);\r\n            Q.push(t); t.add();\r\n        }\r\n    }\r\n\r\n    OT(ans);\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Brief description: \u7ed9\u5b9a\u4e00\u4e2a\u6570\u7ec4\uff0c\u4f60\u5fc5\u987b\u4ea4\u6362\u5176\u4e2d\u7684\u4e24\u4e2a\u6570\uff0c\u6700\u5c0f\u5316\u9006\u5e8f\u5bf9\u6570\u3002\u3002 https:\/\/vijos.org\/p\/1893<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[140],"tags":[],"class_list":["post-1072","post","type-post","status-publish","format-standard","hentry","category-vijos"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-hi","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1072","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/comments?post=1072"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1072\/revisions"}],"predecessor-version":[{"id":1075,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1072\/revisions\/1075"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=1072"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=1072"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=1072"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}