{"id":755,"date":"2013-06-25T08:14:12","date_gmt":"2013-06-25T00:14:12","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=755"},"modified":"2013-06-25T12:31:03","modified_gmt":"2013-06-25T04:31:03","slug":"codeforces-round-189","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/codeforces-round-189\/","title":{"rendered":"Codeforces Round #189"},"content":{"rendered":"<p><!--more--><\/p>\n<h2>Problem C. Kalila and Dimna in the Logging Industry<\/h2>\n<h3>Brief description: <\/h3>\n<p>\u3002\u3002\u7ed9\u5b9a\u4e00\u5217\u6811 <code>A[]<\/code>\u3002\u3002\u6bcf\u9897\u6811\u6709\u4e00\u4e2a\u76f8\u5173\u7684\u4ee3\u4ef7 <code>B[]<\/code>\u3002\u3002<br \/>\n\u3002\u3002\u4f60\u6709\u4e00\u4e2a\u7535\u952f\u3002\u3002\u3002\u6bcf\u6b21\u4f60\u53ef\u4ee5\u7528\u8fd9\u4e2a\u7535\u952f\u628a\u4e00\u68f5\u6811\u7684\u9ad8\u5ea6\u952f 1.\u3002\u4e4b\u540e\u4f60\u9700\u8981\u82b1\u8d39\u4e00\u4e2a\u4ee3\u4ef7\u53bb <code>Recharge<\/code>\u3002\u3002\u3002<br \/>\n\u3002\u3002\u6bcf\u5f53\u4f60\u628a\u4e00\u4e2a\u6811\u7684\u5168\u952f\u6389\u4e4b\u540e\u3002\u3002\u4f60\u5c31\u53ef\u4ee5\u7528\u8fd9\u68f5\u6811\u4e0a\u6240\u6807\u8bb0\u7684\u4ee3\u4ef7\u53bb\u66ff\u6362\u4f60\u5f53\u524d\u7684 <code>Recharge<\/code> \u4ee3\u4ef7\u3002\u3002\u3002<br \/>\n\u3002\u3002\u3002\u6811\u7684\u9ad8\u5ea6\u9012\u589e\u3002\u3002\u4ee3\u4ef7\u9012\u51cf\u3002\u3002\u7b2c\u4e00\u6811\u7684\u9ad8\u5ea6\u662f <code>1<\/code>\uff0c\u6700\u540e\u4e00\u68f5\u6811\u7684\u4ee3\u4ef7\u662f <code>0<\/code>\u3002\u3002\u3002\u3002<br \/>\n\u3002\u3002\u3002\u6700\u5c0f\u5316\u628a\u6240\u6709\u6811\u90fd\u952f\u6389\u7684\u603b\u4ee3\u4ef7\u3002\u3002\u3002<\/p>\n<h3>Analysis: <\/h3>\n<p>\u5148\u641e\u51fa DP \u65b9\u7a0b\u3002\u3002\u3002<\/p>\n<pre class=\"brush: cpp; collapse: false; first-line: 1; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n...\r\n    FOR_1(i, 2, n){\r\n        f&#x5B;i] = INFF;\r\n        FOR(j, 1, i) checkMin(f&#x5B;i], f&#x5B;j] + a&#x5B;i]*b&#x5B;j]);\r\n    }\r\n<\/pre>\n<p>\u3002\u3002\u5f88\u660e\u663e\u8fd9\u662f\u4e00\u4e2a\u659c\u7387 DP\u3002\u3002\u3002<br \/>\n<a href=\"https:\/\/gist.github.com\/lychees\/5853543\">https:\/\/gist.github.com\/lychees\/5853543<\/a><\/p>\n<h2>Problem E. Ping-Pong<\/h2>\n<h3>Brief description: <\/h3>\n<p>\u52a8\u6001\u7ef4\u62a4\u4e00\u7ec4\u533a\u95f4\uff0c\u652f\u6301\u4ee5\u4e0b\u64cd\u4f5c\uff1a<\/p>\n<ul>\n<li><code>1 l r<\/code>\uff1a\u63d2\u5165\u4e00\u4e2a\u65b0\u533a\u95f4 <code>[l, r]<\/code>\u3002<\/li>\n<li><code>2 l r<\/code>\uff1a\u8be2\u95ee\u662f\u5426\u53ef\u4ee5\u4ece\u7b2c <code>l<\/code> \u6b21\u63d2\u5165\u7684\u533a\u95f4\u5230\u8fbe\u7b2c <code>r<\/code> \u6b21\u63d2\u5165\u7684\u533a\u95f4\u3002<\/li>\n<\/ul>\n<p>\u5b58\u5728\u4e00\u6761\u4ece <code>[a, b]<\/code> \u5230 <code>&#091;c, d]<\/code> \u7684\u6709\u5411\u8fb9\u7684\u6761\u4ef6\u662f\u3002\u3002\u4ea4\u53c9\u6216\u8005\u88ab\u5305\u542b\u3002\u3002<br \/>\n\u3002\u3002\u4e5f\u5c31\u662f\u3002\u8fd9\u6837\u8fd9\u6837 <code>[(])<\/code> \u4e92\u76f8\u53ef\u8fbe\u3002\u3002<code>[()]<\/code> \u7684\u8bdd\u53ea\u80fd\u4ece <code>() -> []<\/code>\u3002\u3002<br \/>\n\u3002\u3002(\u603b\u64cd\u4f5c\u6570 \u2264 10^5, \u4e14\u533a\u95f4\u7684\u957f\u5ea6\u6309\u7167\u65f6\u95f4\u987a\u5e8f\u4e25\u683c\u9012\u589e\u3002)<\/p>\n<h3>Analysis: <\/h3>\n<p>&#8230; \u5982\u679c\u662f\u4e92\u76f8\u56fe\u7684\u8bdd\u90a3\u4e48\u5927\u5bb6\u90fd\u4f1a\u641e\u3002\u3002\u5e76\u67e5\u96c6\u7ef4\u62a4\u4e00\u4e0b\u5c31\u884c\u4e86\u3002\u3002\u3002<br \/>\n\u3002\u3002\u4e8e\u662f\u552f\u4e00\u7684\u95ee\u9898\u5c31\u662f\u5728\u4e8e\u5982\u4f55\u5229\u7528 &#8220;\u957f\u5ea6\u9012\u589e&#8221; \u8fd9\u4e2a\u6761\u4ef6\u4e86\u3002\u3002\u3002<\/p>\n<blockquote><p>We define that intervels in the same set can go to each other in the same set. So the interval in set i can go to ( MAXL[i], MAXR[i] ).<br \/>\n(a,b) and (c,d) is in the same set if only if a < c < b < d or c < a < d < b. \n\n>> The length of the new interval is guaranteed to be strictly greater than all the previous intervals.<\/p>\n<p>So the new interval will only connected the intervals, it won&#8217;t be full coverd by any other we had added. We can used segment tree to do this, union the sets, extend MAXL, MAXR of the set. For querys, if the query intervals (a, b)  are in the same set, the answer is YES. Else, we knowed that b can be range ( MAXL[i], MAXR[i] ), just check if a is in that range or not.\t<\/p><\/blockquote>\n<p>\u3002\u3002\u3002\u7fa4\u91cc\u7684 <a href=\"http:\/\/www.renren.com\/342625862\/\">wuyiqi<\/a> \u795e\u725b Gtalks \u4e0a\u95ee\u4e86 <a href=\"http:\/\/codeforces.com\/profile\/hanhan0912\"><font style=\"color: #FF8C00\">hanhan0912<\/font><\/a> \u3002\u3002\u3002 \u6628\u5929\u4e0b\u5348\u8d34\u5230\u7fa4\u91cc\u3002\u3002\u6211\u624d\u60f3\u6e05\u695a\u3002\u3002\u3002\u3002\u3002\u5b9e\u5728\u662f\u667a\u5546\u4f4e\u7684\u4e0d\u80fd\u591a\u8bf4\u3002\u3002\u3002\u3002<br \/>\n\u3002\u3002\u5927\u610f\u5c31\u662f\u6bcf\u4e2a\u5e76\u67e5\u96c6\u3002\u3002\u76f8\u5f53\u4e8e\u6240\u6709\u96c6\u5408\u4e2d\u7684\u533a\u95f4\u6240\u7ec4\u6210\u7684\u4e00\u4e2a\u5927\u7684\u533a\u95f4\u3002\u3002\u3002\u3002\u3002\u90a3\u4e48\u5982\u679c\u4e0d\u5728\u540c\u4e00\u4e2a\u5e76\u67e5\u96c6\u91cc\u3002\u3002\u5219\u53ea\u8981\u68c0\u67e5 \u51fa\u53d1\u533a\u95f4 \u662f\u5426\u88ab\u76ee\u6807\u533a\u95f4\u6240\u5728\u7684\u5e76\u67e5\u96c6\u6240\u8868\u793a\u7684\u533a\u95f4 \u5305\u542b \u5c31\u53ef\u4ee5\u4e86\u3002\u3002\u3002<\/p>\n<p>\u4e3a\u4ec0\u4e48\u8fd9\u6837\u505a\u662f\u6b63\u786e\u7684\u3002\u3002\u3002<\/p>\n<p>\u3002\u3002\u56e0\u4e3a\u5982\u679c <code>()<\/code> \u88ab <code>{}<\/code> \u5305\u542b\u3002\u3002\u3002\u8981\u4e48\u662f\u3002\u3002<code>{   [   ( ] )   }<\/code> \u3002\u3002\u3002\u8981\u4e48\u662f\u3002\u3002<code>{   [   (   ) ] }<\/code><br \/>\n\u3002\u3002\u524d\u4e00\u79cd\u60c5\u51b5\u8bf4\u660e\u5b58\u5728\u4e00\u4e2a\u5c5e\u4e8e <code>{}<\/code> \u7684 <code>[]<\/code> \u4e0e <code>()<\/code> \u76f8\u4ea4\u3002\u3002\u3002\u6b64\u65f6\u5373\u53ef\u8bf4\u660e\u53ef\u8fbe\u3002\u3002\u3002\u3002\u3002<br \/>\n\u3002\u3002\u800c\u540e\u4e00\u79cd\u60c5\u51b5\u4e0d\u5b58\u5728\u3002\u3002\u3002<\/p>\n<p>\u2014\u2014\u2014\u2014\u2014\u2014 \u6784\u601d\u7a0b\u5e8f\u3002\u3002\u3002<\/p>\n<pre class=\"brush: cpp; collapse: false; first-line: 1; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\nstruct Query{\r\n    int id, t, l, r;\r\n    void input(int);\r\n    void process();\r\n} Q&#x5B;N];\r\n<\/pre>\n<p>\u9996\u5148\u5148\u5b9a\u4e49\u4e00\u4e2a <code>Query<\/code> \u7c7b\u3002\u3002\u5148\u58f0\u660e <code>input()<\/code> \u548c <code>process()<\/code> \u4e24\u4e2a\u65b9\u6cd5\u3002\u3002\u7559\u5230\u4e0b\u9762\u5199\u3002\u3002<br \/>\n\u7136\u540e\u662f\u5e76\u67e5\u96c6\u3002\u3002<\/p>\n<pre class=\"brush: cpp; collapse: false; first-line: 1; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\nnamespace DSU{ \/\/ Disjoint Set Union\r\n    int P&#x5B;N], R&#x5B;N], l&#x5B;N], r&#x5B;N], n;\r\n    inline void Make(int x){\r\n        P&#x5B;x] = x, R&#x5B;x] = 0;\r\n    }\r\n    inline int Find(int x){\r\n        return P&#x5B;x] == x ? x : P&#x5B;x] = Find(P&#x5B;x]);\r\n    }\r\n    inline void Unionn(int x, int y){\r\n        if (R&#x5B;x] == R&#x5B;y]) ++R&#x5B;x];\r\n        else if (R&#x5B;x] &lt; R&#x5B;y]) swap(x, y);\r\n        P&#x5B;y] = x;\r\n        checkMin(l&#x5B;x], l&#x5B;y]);\r\n        checkMax(r&#x5B;x], r&#x5B;y]);\r\n    }\r\n    inline void Union(int x, int y){\r\n        x = Find(x), y = Find(y), Unionn(x, y);\r\n    }\r\n    inline void Init(){\r\n        REP_1(i, n) Make(i);\r\n    }\r\n} \/\/using namespace DSU;\r\n<\/pre>\n<p>\u3002\u3002\u3002\u5e76\u67e5\u96c6\u9700\u8981\u589e\u52a0 <code>l<\/code> \u548c <code>r<\/code> \u4e24\u4e2a\u57df\u3002\u3002\u7528\u4ee5\u8bb0\u5f55\u96c6\u5408\u6240\u4ee3\u8868\u7684\u533a\u95f4\u3002<br \/>\n<code>Unionn(x, y)<\/code> \u5408\u5e76\u8868\u793a\u5408\u5e76\u524d <code>x, y<\/code> \u5c31\u5df2\u7ecf\u662f\u6839\u7ed3\u70b9\u4e86\u3002\u3002\uff08\u4e60\u60ef\u53cc\u5199\u672b\u5c3e\u5b57\u6bcd\u8868\u793a\u4e00\u4e2a\u76f8\u5173\u7684\u4e1c\u897f\u3002\u3002\u6bd4\u5982\u8ba1\u7b97\u51e0\u4f55\u91cc\u6211\u7ecf\u5e38\u7528 <code>dett()<\/code> \u8868\u793a <code>det()<\/code> \u540e\u53d6 <code>sgn()<\/code>\u3002\u3002\u3002\u53ef\u4ee5\u7406\u89e3\u6210 <code>Union'<\/code> \u548c <code>det'<\/code><\/p>\n<p>\u7136\u540e\u6211\u4eec\u8fd8\u9700\u8981\u4e00\u4e2a\u7ebf\u6bb5\u6811\u53bb\u7ef4\u62a4\u8fd9\u4e2a\u5e76\u67e5\u96c6\u3002\u3002\u3002<\/p>\n<pre class=\"brush: cpp; collapse: false; first-line: 1; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\nnamespace SGT{ \/\/ Segment Tree\r\n\r\n#define lx (x&lt;&lt;1)\r\n#define rx (lx|1)\r\n#define mid (l + r &gt;&gt; 1)\r\n#define lc lx, l, mid\r\n#define rc rx, mid+1, r\r\n#define root 1, 0, SZ(grid)-1\r\n\r\n    const int N = ::N*8;\r\n    VI T&#x5B;N]; int id, a, b;\r\n\r\n    void _Insert(int x, int l, int r){\r\n\r\n        if (r &lt; a || b &lt; l) return;\r\n\r\n        if (a &lt;= l &amp;&amp; r &lt;= b){\r\n            T&#x5B;x].PB(id);\r\n        }\r\n        else{\r\n            _Insert(lc);\r\n            _Insert(rc);\r\n        }\r\n    }\r\n\r\n    void _Extend(int x, int l, int r){\r\n\r\n        if (r &lt; a || a &lt; l) return;\r\n\r\n#define del(A, i) swap(A&#x5B;i], A.back()), A.pop_back(), --i;\r\n\r\n        REP(i, SZ(T&#x5B;x])){\r\n            int t = DSU::Find(T&#x5B;x]&#x5B;i]);\r\n            if (t != T&#x5B;x]&#x5B;i]){ \/\/ \u5c0f\u4f18\u5316...\r\n                del(T&#x5B;x], i);\r\n            }\r\n            else if (DSU::l&#x5B;t] &lt; a &amp;&amp; a &lt; DSU::r&#x5B;t]){\r\n                DSU::Unionn(t, id);\r\n                id = DSU::Find(id);\r\n                del(T&#x5B;x], i);\r\n            }\r\n        }\r\n\r\n        if (l &lt; r){\r\n            _Extend(lc);\r\n            _Extend(rc);\r\n        }\r\n    }\r\n\r\n    void Insert(int _id){\r\n        id = _id, a = DSU::l&#x5B;id], b = DSU::r&#x5B;id], _Extend(root), a = b, _Extend(root);\r\n        a = DSU::l&#x5B;id], b = DSU::r&#x5B;id], _Insert(root);\r\n    }\r\n\r\n    void Build(){\r\n        UNQ(grid);\r\n    }\r\n} \/\/using namespace SGT;\r\n<\/pre>\n<p>\u7ebf\u6bb5\u6811\u7684\u6bcf\u4e2a\u7ed3\u70b9\u5b58\u4e00\u4e2a <code>Vector<\/code> \u4ee5\u4efb\u610f\u987a\u5e8f\u5217\u4e3e\u6240\u6709\u76f8\u5173\u96c6\u5408\u3002\u3002\u63d2\u5165\u533a\u95f4\u524d\u9996\u5148\u9700\u8981\u6267\u884c\u6269\u5c55\u3002\u3002\u3002<\/p>\n<ul>\n<li><code>_Extend()<\/code>\u3002\u3002\u68c0\u67e5\u6240\u6709\u53ef\u4ee5\u8986\u76d6\u5f53\u524d\u533a\u95f4\u67d0\u4e2a\u7aef\u70b9\u7684\u533a\u95f4\u3002\u3002\u5e76\u6269\u5c55\u5f53\u524d\u533a\u95f4\u3002\u3002\u3002<\/li>\n<li><code>_Insert()<\/code>\u3002\u3002\u63d2\u5165\u6269\u5c55\u540e\u7684\u533a\u95f4\u3002\u3002\u3002<\/li>\n<\/ul>\n<p>\u3002\u3002\u3002\u8865\u4e0a\u5176\u4ed6\u90e8\u5206\u5c31\u884c\u4e86\u3002\u3002<\/p>\n<pre class=\"brush: cpp; collapse: false; first-line: 1; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\nvoid Query::input(int i){\r\n    if (RD(t) == 1){\r\n        grid.PB(RDD(l)), grid.PB(RDD(r)); \/\/ \u79bb\u6563\u5316\u51c6\u5907\u3002\r\n        DQ&#x5B;id = ++DSU::n] = i; \/\/ \u5efa\u7acb\u6620\u5c04\r\n    }\r\n    else{\r\n        RD(l, r);\r\n    }\r\n}\r\n\r\nvoid Query::process(){\r\n    if (t == 1){\r\n        DSU::l&#x5B;id] = l = BSC(grid, l), DSU::r&#x5B;id] = r = BSC(grid, r);\r\n        SGT::Insert(id);\r\n    }\r\n    else{\r\n        l = DQ&#x5B;l], r = DSU::Find(r);\r\n        puts(DSU::l&#x5B;r] &lt;= Q&#x5B;l].l &amp;&amp; Q&#x5B;l].r &lt;= DSU::r&#x5B;r] ? &quot;YES&quot; : &quot;NO&quot;);\r\n    }\r\n}\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_1_C(i, RD(n)) Q&#x5B;i].input(i);\r\n    DSU::Init(), SGT::Build();\r\n    REP_1(i, n) Q&#x5B;i].process();\r\n}\r\n<\/pre>\n<p><a href=\"https:\/\/gist.github.com\/lychees\/5855251\">https:\/\/gist.github.com\/lychees\/5855251<\/a><\/p>\n<p>&#8212; \u8865\u5145<br \/>\n\u3002\u3002\u3002\u3002<a href=\"https:\/\/gist.github.com\/lychees\/5854845\/revisions\">\u8fd9\u4e2a\u7248\u672c\u7684\u7a0b\u5e8f<\/a>\u867d\u7136\u662f <code>AC<\/code> \u7684\u3002\u3002&#8230; \u4f46\u662f\u4ea4\u6362 <code>Union()<\/code> \u4e24\u4e2a\u53c2\u6570\u7684\u987a\u5e8f\u5c31\u4f1a <code>WA on 5<\/code>\u3002\u3002<br \/>\n\u3002\u3002\u3002\u8fd9\u7c7b\u9519\u8bef\u975e\u5e38\u9690\u853d\u4e0d\u5b9c\u5bdf\u89c9\u3002\u3002\u7a0b\u5e8f\u91cc\u6700\u597d\u4e0d\u8981\u4f9d\u8d56\u65bc\u8fd9\u79cd\u4e1c\u897f\u3002\u3002\u3002<\/p>\n<h3>External link: <\/h3>\n","protected":false},"excerpt":{"rendered":"","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":[18],"tags":[28,118],"class_list":["post-755","post","type-post","status-publish","format-standard","hentry","category-codeforces","tag-28","tag-118"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-cb","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/755","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=755"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/755\/revisions"}],"predecessor-version":[{"id":756,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/755\/revisions\/756"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=755"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=755"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=755"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}