{"id":613,"date":"2012-12-27T21:11:12","date_gmt":"2012-12-27T13:11:12","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=613"},"modified":"2021-09-12T06:40:48","modified_gmt":"2021-09-11T22:40:48","slug":"bzoj-1492-noi2007%e8%b4%a7%e5%b8%81%e5%85%91%e6%8d%a2cash","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/bzoj-1492-noi2007%e8%b4%a7%e5%b8%81%e5%85%91%e6%8d%a2cash\/","title":{"rendered":"BZOJ 1492. [NOI2007]\u8d27\u5e01\u5151\u6362Cash"},"content":{"rendered":"<ul>\n<li><a href=\"https:\/\/www.luogu.com.cn\/problem\/P4027\">https:\/\/www.luogu.com.cn\/problem\/P4027<\/a><\/li>\n<li><a href=\"https:\/\/darkbzoj.tk\/problem\/1492\">https:\/\/darkbzoj.tk\/problem\/1492<\/a><\/li>\n<\/ul>\n<h3>Brief description: <\/h3>\n<p>&#8230; <!--more--><\/p>\n<h3>Analysis: <\/h3>\n<p>&#8230;<\/p>\n<h5>\u7b97\u6cd5\u4e00\uff1acdq \u5206\u6cbb<\/h5>\n<p>\u968f\u7740\u79d1\u6280\u7684\u8fdb\u6b65\u6211\u4eec\u5df2\u7ecf\u77e5\u9053\u53ef\u4ee5\u4f7f\u7528 cdq \u5206\u6cbb\u6765\u89e3\u51b3\u8fd9\u7c7b\u95ee\u9898\u4e86\u3002\u3002\u3002<\/p>\n<pre class=\"brush: cpp; light: false; title: cdq 1=O(nlog^2n); toolbar: true; notranslate\" title=\"cdq 1=O(nlog^2n)\">\r\n\r\n\/\/}\/* .................................................................................................................................. *\/\r\n\r\nconst int N = int(1e5) + 9;\r\nDB A&#x5B;N], B&#x5B;N], R&#x5B;N], f&#x5B;N];\r\nint n;\r\n\r\n#define y(i) (f&#x5B;i] \/ (R&#x5B;i] * A&#x5B;i] + B&#x5B;i]))\r\n#define x(i) (R&#x5B;i] * y(i))\r\n\r\nbool cmp_k(int i, int j){\r\n    return A&#x5B;i]*B&#x5B;j] &lt; A&#x5B;j]*B&#x5B;i];\r\n}\r\n\r\nvoid cdq(int l, int r){\r\n    if (l + 1 == r){\r\n        checkMax(f&#x5B;r], f&#x5B;l]);\r\n    }\r\n    else{\r\n        int m = l + r &gt;&gt; 1; cdq(l, m);\r\n        static Po P&#x5B;N], C&#x5B;N]; int pn = 0, cn = 0;\r\n        FOR(i, l, m) P&#x5B;pn++] = Po(x(i), y(i)); sort(P, P+pn);\r\n\r\n        REP(i, pn){\r\n            while (cn &gt; 1 &amp;&amp; dett(C&#x5B;cn-1], C&#x5B;cn], P&#x5B;i]) &gt;= 0) --cn;\r\n            C&#x5B;++cn] = P&#x5B;i];\r\n        }\r\n\r\n        static int Q&#x5B;N]; int qn = 0;\r\n        FOR(i, m, r) Q&#x5B;qn++] = i; sort(Q, Q+qn, cmp_k);\r\n\r\n#define eval(c) (A&#x5B;i]*C&#x5B;c].x + B&#x5B;i]*C&#x5B;c].y)\r\n\r\n        int c = 1; REP(q, qn){\r\n            int i = Q&#x5B;q]; while (c &lt; cn &amp;&amp; eval(c) &lt; eval(c+1)) ++c;\r\n            checkMax(f&#x5B;i], eval(c));\r\n        }\r\n\r\n        cdq(m, r);\r\n    }\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;cash7.in&quot;, &quot;r&quot;, stdin);\r\n    \/\/freopen(&quot;out.txt&quot;, &quot;w&quot;, stdout);\r\n#endif\r\n\r\n    RD(n); RF(f&#x5B;0]); REP(i, n) RF(A&#x5B;i], B&#x5B;i], R&#x5B;i]);\r\n    cdq(0, n); OT(f&#x5B;n]);\r\n}\r\n\r\n<\/pre>\n<p><a href=\"https:\/\/gist.github.com\/lychees\/6f7e2fb392c24da5bd16#file-cdq_o-nlog2n-cpp\">https:\/\/gist.github.com\/lychees\/6f7e2fb392c24da5bd16#file-cdq_o-nlog2n-cpp<\/a><\/p>\n<pre class=\"brush: cpp; light: false; title: cdq 1=O(nlogn); toolbar: true; notranslate\" title=\"cdq 1=O(nlogn)\">\r\n\r\n\/\/}\/* .................................................................................................................................. *\/\r\n\r\nconst int N = int(1e5) + 9;\r\nDB A&#x5B;N], B&#x5B;N], R&#x5B;N], f&#x5B;N];\r\nint n;\r\n\r\n#define y(i) (f&#x5B;i] \/ (R&#x5B;i] * A&#x5B;i] + B&#x5B;i]))\r\n#define x(i) (R&#x5B;i] * y(i))\r\n\r\nbool cmp_k(int i, int j){\r\n    return A&#x5B;i]*B&#x5B;j] &lt; A&#x5B;j]*B&#x5B;i];\r\n}\r\n\r\nint Q&#x5B;N]; Po C&#x5B;N], P&#x5B;N];\r\n\r\nvoid cdq(int l, int r){\r\n    if (l + 1 == r){\r\n        checkMax(f&#x5B;r], f&#x5B;l]);\r\n        P&#x5B;l] = Po(x(l), y(l));\r\n    }\r\n    else{\r\n        int m = l + r &gt;&gt; 1;\r\n\r\n        static int tmp&#x5B;N]; int tl = l, tr = m;\r\n        FOR(i, l, r) if (Q&#x5B;i] &lt; m) tmp&#x5B;tl++] = Q&#x5B;i]; else tmp&#x5B;tr++] = Q&#x5B;i];\r\n        memcpy(Q+l, tmp+l, sizeof(int) * (r-l));\r\n\r\n        VP Pl, Pr; cdq(l, m);\r\n\r\n        int cn = 0; FOR(i, l, m){\r\n            while (cn &gt; 1 &amp;&amp; dett(C&#x5B;cn-1], C&#x5B;cn], P&#x5B;i]) &gt;= 0) --cn;\r\n            C&#x5B;++cn] = P&#x5B;i];\r\n        }\r\n\r\n#define eval(c) (A&#x5B;i]*C&#x5B;c].x + B&#x5B;i]*C&#x5B;c].y)\r\n\r\n        int c = 1; FOR(q, m, r){\r\n            int i = Q&#x5B;q]; while (c &lt; cn &amp;&amp; eval(c) &lt; eval(c+1)) ++c;\r\n            checkMax(f&#x5B;i], eval(c));\r\n        }\r\n\r\n        cdq(m, r);\r\n\r\n        static Po tmpP&#x5B;N]; merge(P+l, P+m, P+m, P+r, tmpP);\r\n        memcpy(P+l, tmpP, sizeof(Po)*(r-l));\r\n    }\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;cash7.in&quot;, &quot;r&quot;, stdin);\r\n    \/\/freopen(&quot;out.txt&quot;, &quot;w&quot;, stdout);\r\n#endif\r\n\r\n    RD(n); RF(f&#x5B;0]); REP(i, n) RF(A&#x5B;i], B&#x5B;i], R&#x5B;i]), Q&#x5B;i] = i; sort(Q, Q+n, cmp_k);\r\n    cdq(0, n); OT(f&#x5B;n]);\r\n}\r\n\r\n<\/pre>\n<p><a href=\"https:\/\/gist.github.com\/lychees\/6f7e2fb392c24da5bd16#file-cdq_o-nlogn-cpp\">https:\/\/gist.github.com\/lychees\/6f7e2fb392c24da5bd16#file-cdq_o-nlogn-cpp<\/a><\/p>\n<h5>\u7b97\u6cd5\u4e8c\uff1a\u5e73\u8861\u6811\u7ef4\u62a4\u51f8\u58f3<\/h5>\n<p>\u3002\u3002\u3002\u770b\u6765\u8fd8\u662f<a href=\"http:\/\/hi.baidu.com\/oimaster\/item\/d8041f4a865444ee1f19bc43\">\u8d3e\u6559\uff08Oimaster\uff09<\/a>\u89e3\u91ca\u7684\u6700\u6e05\u695a\u3002\u30020 w0\u3002<\/p>\n<blockquote><p>\n\u6839\u636e\u63d0\u793a\u5185\u5bb9\uff0c\u6211\u4eec\u5c31\u53ef\u4ee5\u5f97\u5230\u4e00\u4e2a\u52a8\u6001\u89c4\u5212\u7b97\u6cd5\uff1a\u7528f[i]\u8868\u793a\u5230\u7b2ci\u5929\u4e3a\u6b62\u80fd\u5f97\u5230\u7684\u6700\u591a\u94b1\u6570\u3002\u6839\u636ef[i]\uff0c\u6211\u4eec\u53ef\u4ee5\u5f97\u5230\u5982\u679c\u7b2ci\u5929\u5356\u51fa\u91d1\u5238\u7684\u8bdd\uff0cA\u5238\u548cB\u5238\u5404\u6709\u591a\u5c11\u5f20\uff08\u6211\u4eec\u8bbe\u4e3aX[i]\u548cY[i]\uff09\u3002\u5219\u8f6c\u79fb\u65b9\u7a0b\u4e3a\uff1a<br \/>\nf[i] = max( f[i-1], max{ X[j]*a[i] + Y[j]*b[i] | j <= i})\n\u8fb9\u754c\u6761\u4ef6\u4e3af[1]=s\u3002\n\u5176\u4e2dX[i]\u548cY[i]\u53ef\u4ee5\u6839\u636ef[i]\u5f97\u51fa\uff0c\u5177\u4f53\u5c31\u4e0d\u8bb2\u4e86\u3002\n<\/p><\/blockquote>\n<pre class=\"brush: cpp; collapse: true; first-line: 1; light: false; title: \u6734\u7d20.cpp; toolbar: true; notranslate\" title=\"\u6734\u7d20.cpp\">\r\nconst int N = 109;\r\nDB A&#x5B;N], B&#x5B;N], R&#x5B;N], f&#x5B;N];\r\nint n; DB ans;\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\tRD(n); RF(f&#x5B;0]); REP_1(i, n) RF(A&#x5B;i], B&#x5B;i], R&#x5B;i]);\r\n\r\n#define b(i) (f&#x5B;i] \/ (R&#x5B;i] * A&#x5B;i] + B&#x5B;i]))\r\n#define a(i) (R&#x5B;i] * b(i))\r\n\r\n    REP_1(i, n){\r\n        f&#x5B;i] = f&#x5B;i-1];\r\n        REP(j, i) checkMax(f&#x5B;i], a(j)*A&#x5B;i] + b(j)*B&#x5B;i]);\r\n    }\r\n\r\n\tOT(f&#x5B;n]);\r\n}\r\n<\/pre>\n<blockquote>\n<p>\u8fd9\u4e2a\u52a8\u6001\u89c4\u5212\u663e\u7136\u662f1D\/1D\u52a8\u6001\u89c4\u5212\uff0c\u666e\u901a\u505a\u6cd5\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u4e3aO(n^2)\uff0c\u5bf9\u4e8e100000\u7684\u6570\u636e\u663e\u7136\u662f\u4f1a\u8d85\u65f6\u7684\uff0c\u6240\u4ee5\u8fd8\u8981\u4f18\u5316\u3002<br \/>\n\u6211\u4eec\u628a\u6240\u6709\u7684X[i]\u548cY[i]\u62bd\u8c61\u6210\u5750\u6807\u7cfb\u4e2d\u7684\u70b9\uff0c\u5373X[i]\u4e3a\u6a2a\u5750\u6807\uff0cY[i]\u4e3a\u7eb5\u5750\u6807\u3002<br \/>\n\u7136\u540e\u6211\u4eec\u4ee4P=a[i]*x+b[i]*y\uff0c\u5373\u8f6c\u79fb\u65b9\u7a0b\u4e2d\u7684(X[j]*a[i]+Y[j]*b[i])\u3002\u53d8\u5f62\u53ef\u5f97y=(-a[i]\/b[i])*x+P\/b[i]\uff0c\u5373\u6709\u4e00\u6761\u659c\u7387\u4e00\u5b9a\u7684\u76f4\u7ebf\uff0c\u5e76\u4e14\u7ecf\u8fc7\u67d0\u4e2a\u70b9(x,y)\uff0c\u7136\u540e\u8981\u6700\u5927\u5316\u622a\u8ddd\u3002\u5bf9\u4e8e\u8fd9\u4e2a\u95ee\u9898\uff0c\u6211\u4eec\u53ef\u4ee5\u60f3\u8c61\u6210\u6709\u4e00\u6761\u659c\u7387\u4e3a(-a[i]\/b[i])\u7684\u76f4\u7ebf\u4ece\u65e0\u7a77\u8fdc\u7684\u5730\u65b9\u5411\u4e0b\uff0c\u7b2c\u4e00\u4e2a\u78b0\u5230\u7684\u70b9\u5373\u4e3a\u6700\u4f18\u89e3\u3002\u90a3\u4e48\u5c31\u53ef\u4ee5\u5f97\u5230\u4ee5\u4e0b\u7ed3\u8bba\uff1a<br \/>\n\u5982\u679c\u70b9(X[i],Y[i])\u4e3a\u67d0\u6b21\u7684\u6700\u4f18\u51b3\u7b56\uff0c\u90a3\u4e48\u663e\u7136\u8fd9\u4e2a\u70b9\u662f\u5728\u6240\u6709\u70b9\u7684\u51f8\u58f3\u4e0a\u7684\uff0c\u5982\u4e0b\u56fe\u4e2d\u7684C\u70b9\u4e0d\u53ef\u80fd\u4e3a\u6700\u4f18\u7684\u51b3\u7b56\u70b9\u3002<\/p>\n<p><a href=\"https:\/\/www.shuizilong.com\/house\/wp-content\/uploads\/2012\/12\/1.jpg\"><img loading=\"lazy\" decoding=\"async\" data-attachment-id=\"615\" data-permalink=\"https:\/\/www.shuizilong.com\/house\/archives\/bzoj-1492-noi2007%e8%b4%a7%e5%b8%81%e5%85%91%e6%8d%a2cash\/1-5\/\" data-orig-file=\"https:\/\/www.shuizilong.com\/house\/wp-content\/uploads\/2012\/12\/1.jpg\" data-orig-size=\"285,257\" data-comments-opened=\"1\" data-image-meta=\"{&quot;aperture&quot;:&quot;0&quot;,&quot;credit&quot;:&quot;&quot;,&quot;camera&quot;:&quot;&quot;,&quot;caption&quot;:&quot;&quot;,&quot;created_timestamp&quot;:&quot;0&quot;,&quot;copyright&quot;:&quot;&quot;,&quot;focal_length&quot;:&quot;0&quot;,&quot;iso&quot;:&quot;0&quot;,&quot;shutter_speed&quot;:&quot;0&quot;,&quot;title&quot;:&quot;&quot;}\" data-image-title=\"1\" data-image-description=\"\" data-image-caption=\"\" data-medium-file=\"https:\/\/www.shuizilong.com\/house\/wp-content\/uploads\/2012\/12\/1.jpg\" data-large-file=\"https:\/\/www.shuizilong.com\/house\/wp-content\/uploads\/2012\/12\/1.jpg\" data-id=\"615\"  src=\"https:\/\/www.shuizilong.com\/house\/wp-content\/uploads\/2012\/12\/1.jpg\" alt=\"\" title=\"1\" width=\"285\" height=\"257\" class=\"aligncenter size-full wp-image-615\" \/><\/a><\/p>\n<p>\u539f\u56e0\u5f88\u7b80\u5355\uff0c\u5982\u679c\u6709\u4e00\u6761\u659c\u7387\u4e00\u5b9a\u76f4\u7ebf\u4ece\u4e0a\u5411\u4e0b\u5e73\u79fb\u8fc7\u6765\uff0c\u5fc5\u5b9a\u5148\u78b0\u5230\u70b9A\u6216\u70b9B\uff0c\u4e0d\u53ef\u80fd\u5148\u78b0\u5230\u70b9C\u3002<br \/>\n\u56e0\u6b64\u6211\u4eec\u7ef4\u62a4\u4e00\u4e2a\u51b3\u7b56\u5e8f\u5217\uff0c\u8fd9\u4e2a\u51b3\u7b56\u5e8f\u5217\u4e2d\u7684\u70b9\u5373\u4e3a\u51f8\u58f3\u4e0a\u7684\u70b9\uff0c\u7136\u540e\u6211\u4eec\u6309\u6a2a\u5750\u6807\u5c06\u8fd9\u4e9b\u70b9\u6392\u5e8f\uff0c\u5219\u7eb5\u5750\u6807\u4e5f\u5c31\u6709\u5e8f\uff0c\u5e76\u4e14\u76f8\u90bb\u4e24\u4e2a\u70b9\u7684\u8fde\u7ebf\u7684\u659c\u7387\u5355\u8c03\u9012\u51cf\u3002<br \/>\n\u5bf9\u4e8e\u4e00\u6761\u659c\u7387\u4e00\u5b9a\u7684\u76f4\u7ebf\uff0c\u5176\u6700\u4f18\u89e3\u7684\u70b9\u5fc5\u7136\u662f\u8fd9\u6837\u7684\uff1a<\/p>\n<p><a href=\"https:\/\/www.shuizilong.com\/house\/wp-content\/uploads\/2012\/12\/2.jpg\"><img loading=\"lazy\" decoding=\"async\" data-attachment-id=\"616\" data-permalink=\"https:\/\/www.shuizilong.com\/house\/archives\/bzoj-1492-noi2007%e8%b4%a7%e5%b8%81%e5%85%91%e6%8d%a2cash\/2-5\/\" data-orig-file=\"https:\/\/www.shuizilong.com\/house\/wp-content\/uploads\/2012\/12\/2.jpg\" data-orig-size=\"619,486\" data-comments-opened=\"1\" data-image-meta=\"{&quot;aperture&quot;:&quot;0&quot;,&quot;credit&quot;:&quot;&quot;,&quot;camera&quot;:&quot;&quot;,&quot;caption&quot;:&quot;&quot;,&quot;created_timestamp&quot;:&quot;0&quot;,&quot;copyright&quot;:&quot;&quot;,&quot;focal_length&quot;:&quot;0&quot;,&quot;iso&quot;:&quot;0&quot;,&quot;shutter_speed&quot;:&quot;0&quot;,&quot;title&quot;:&quot;&quot;}\" data-image-title=\"2\" data-image-description=\"\" data-image-caption=\"\" data-medium-file=\"https:\/\/www.shuizilong.com\/house\/wp-content\/uploads\/2012\/12\/2-300x235.jpg\" data-large-file=\"https:\/\/www.shuizilong.com\/house\/wp-content\/uploads\/2012\/12\/2.jpg\" data-id=\"616\"  src=\"https:\/\/www.shuizilong.com\/house\/wp-content\/uploads\/2012\/12\/2.jpg\" alt=\"\" title=\"2\" width=\"619\" height=\"486\" class=\"aligncenter size-full wp-image-616\" srcset=\"https:\/\/www.shuizilong.com\/house\/wp-content\/uploads\/2012\/12\/2.jpg 619w, https:\/\/www.shuizilong.com\/house\/wp-content\/uploads\/2012\/12\/2-300x235.jpg 300w, https:\/\/www.shuizilong.com\/house\/wp-content\/uploads\/2012\/12\/2-382x300.jpg 382w\" sizes=\"auto, (max-width: 619px) 100vw, 619px\" \/><\/a><\/p>\n<p>\u5373\u5982\u679c\u8fd9\u6761\u76f4\u7ebf\u7684\u659c\u7387\u4e3ak\uff0c\u6700\u4f18\u51b3\u7b56\u70b9\u4e0e\u5176\u76f8\u90bb\u4e24\u70b9\u8fde\u7ebf\u7684\u659c\u7387\u5206\u522b\u4e3ak1\u548ck2\uff0c\u5219\u6ee1\u8db3k1>=k>=k2\u3002<\/p>\n<p>\u56e0\u6b64\u73b0\u5728\u6211\u4eec\u7684\u4efb\u52a1\u662f\u600e\u6837\u9ad8\u6548\u5730\u7ef4\u62a4\u8fd9\u4e2a\u51b3\u7b56\u70b9\u5e8f\u5217\uff0c\u663e\u7136\u5e73\u8861\u6811\u53ef\u4ee5\u5f88\u597d\u7684\u505a\u5230\u8fd9\u70b9\u3002\u6211\u4eec\u5c06\u8fd9\u4e9b\u70b9\u6309\u7167\u6a2a\u5750\u6807\u7684\u5927\u5c0f\u5efa\u4e00\u68f5\u5e73\u8861\u6811\uff0c\u90a3\u4e48\u7eb5\u5750\u6807\u4e5f\u6709\u5e8f\uff0c\u7136\u540e\u6bcf\u65b0\u7b97\u51fa\u6765\u4e00\u4e2af[i]\uff0c\u7b97\u51fa\u4e0e\u5176\u5bf9\u5e94\u7684X[i]\u4e0eY[i]\uff0c\u5148\u6309\u6a2a\u5750\u6807\u627e\u5230\u8fd9\u4e2a\u70b9\u7684\u63d2\u5165\u4f4d\u7f6e\u3002\u7136\u540e\u6211\u4eec\u5224\u65ad\u8fd9\u4e2a\u70b9\u662f\u5426\u5e94\u8be5\u4fdd\u7559\uff0c\u5982\u679c\u51fa\u73b0\u7b2c\u4e00\u5e45\u56fe\u4e2d\u7684\u60c5\u51b5\uff0c\u90a3\u4e48\u8fd9\u4e2a\u70b9\u65e0\u9700\u63d2\u5165\uff0c\u5426\u5219\u5c06\u8fd9\u4e2a\u70b9\u63d2\u5165\u5e73\u8861\u6811\u4e2d\u3002\u4e0b\u9762\u5c31\u662f\u7ef4\u62a4\u8fd9\u4e2a\u51f8\u58f3\uff0c\u6211\u4eec\u4ece\u8fd9\u4e2a\u70b9\u5f00\u59cb\uff0c\u5206\u522b\u5411\u5de6\u548c\u5411\u53f3\u627e\u5230\u7b2c\u4e00\u4e2a\u6ee1\u8db3\u51f8\u58f3\u7684\u4e24\u4e2a\u70b9\uff0c\u5c06\u4e2d\u95f4\u7684\u70b9\u5220\u9664\u3002\u5bf9\u4e8e\u53d6\u5f97f[i]\u6700\u4f18\u51b3\u7b56\uff0c\u56e0\u4e3a\u659c\u7387\u5355\u8c03\u51cf\uff0c\u56e0\u6b64\u6211\u4eec\u53ef\u4ee5\u4e8c\u5206\uff08\u5373\u5224\u65ad\u8fd9\u4e2a\u70b9\u662f\u5728\u5de6\u5b50\u6811\u4e2d\u8fd8\u662f\u53f3\u5b50\u6811\u4e2d\uff09\u3002\u5176\u4e2d\u51f8\u58f3\u7ef4\u62a4\u8fc7\u7a0b\u5982\u4e0b\u56fe\u6240\u793a<\/p>\n<p><a href=\"https:\/\/www.shuizilong.com\/house\/wp-content\/uploads\/2012\/12\/3.jpg\"><img loading=\"lazy\" decoding=\"async\" data-attachment-id=\"617\" data-permalink=\"https:\/\/www.shuizilong.com\/house\/archives\/bzoj-1492-noi2007%e8%b4%a7%e5%b8%81%e5%85%91%e6%8d%a2cash\/3-4\/\" data-orig-file=\"https:\/\/www.shuizilong.com\/house\/wp-content\/uploads\/2012\/12\/3.jpg\" data-orig-size=\"680,480\" data-comments-opened=\"1\" data-image-meta=\"{&quot;aperture&quot;:&quot;0&quot;,&quot;credit&quot;:&quot;&quot;,&quot;camera&quot;:&quot;&quot;,&quot;caption&quot;:&quot;&quot;,&quot;created_timestamp&quot;:&quot;0&quot;,&quot;copyright&quot;:&quot;&quot;,&quot;focal_length&quot;:&quot;0&quot;,&quot;iso&quot;:&quot;0&quot;,&quot;shutter_speed&quot;:&quot;0&quot;,&quot;title&quot;:&quot;&quot;}\" data-image-title=\"3\" data-image-description=\"\" data-image-caption=\"\" data-medium-file=\"https:\/\/www.shuizilong.com\/house\/wp-content\/uploads\/2012\/12\/3-300x211.jpg\" data-large-file=\"https:\/\/www.shuizilong.com\/house\/wp-content\/uploads\/2012\/12\/3.jpg\" data-id=\"617\"  src=\"https:\/\/www.shuizilong.com\/house\/wp-content\/uploads\/2012\/12\/3.jpg\" alt=\"\" title=\"3\" width=\"680\" height=\"480\" class=\"aligncenter size-full wp-image-617\" srcset=\"https:\/\/www.shuizilong.com\/house\/wp-content\/uploads\/2012\/12\/3.jpg 680w, https:\/\/www.shuizilong.com\/house\/wp-content\/uploads\/2012\/12\/3-300x211.jpg 300w, https:\/\/www.shuizilong.com\/house\/wp-content\/uploads\/2012\/12\/3-425x300.jpg 425w\" sizes=\"auto, (max-width: 680px) 100vw, 680px\" \/><\/a><\/p>\n<\/blockquote>\n<pre class=\"brush: cpp; collapse: true; first-line: 1; light: false; title: \u7ed3\u70b9\u5b9a\u4e49; toolbar: true; notranslate\" title=\"\u7ed3\u70b9\u5b9a\u4e49\">\r\nstruct node{\r\n    static node*NIL,*root; \/\/ \u54e8\u5175\u3001\u6839\u7ed3\u70b9 .. .\r\n    node*c&#x5B;2],*p; PDD o; DB k&#x5B;2]; \/\/ \u5b69\u5b50\u3001\u7236\u4eb2\u3001\u5750\u6807\u3001\u659c\u7387\u3002\u3002\r\n}\r\n<\/pre>\n<pre class=\"brush: cpp; collapse: true; first-line: 1; light: false; title: \u7ef4\u62a4; toolbar: true; notranslate\" title=\"\u7ef4\u62a4\">\r\n.. .\r\n    inline void clean(int d){\r\n        for (node*x=neighbor(d);x!=NIL;x=neighbor(d)){ \/\/x-&gt;o.se &lt; o.se ^ d\r\n            if (x-&gt;splay(this)-&gt;k&#x5B;d] &lt; get_k(o, x-&gt;o) ^ d) setc(d, x-&gt;c&#x5B;d]);\r\n            else break;\r\n        }\r\n    }\r\n\r\n    inline void clean(){\r\n        clean(0), clean(1);\r\n    }\r\n\r\n    inline node*fix(){\r\n        splay(); node*a = pred(),*b = succ();\r\n        k&#x5B;0] = a == NIL ? +OO : get_k(o, a-&gt;o);\r\n        k&#x5B;1] = b == NIL ? -OO : get_k(o, b-&gt;o);\r\n        if (k&#x5B;0] &lt; k&#x5B;1]){\r\n            root = a-&gt;splay(this), a-&gt;p = NIL, a-&gt;setr(r);\r\n        }\r\n        else {\r\n            clean(), a = pred(), b = succ();\r\n            k&#x5B;0] = a == NIL ? +OO : a-&gt;k&#x5B;1] = get_k(o, a-&gt;o);\r\n            k&#x5B;1] = b == NIL ? -OO : b-&gt;k&#x5B;0] = get_k(o, b-&gt;o);\r\n        }\r\n    }\r\n.. .\r\n<\/pre>\n<pre class=\"brush: cpp; collapse: true; first-line: 1; light: false; title: \u67e5\u627e 1=\u63d2\u5165; toolbar: true; notranslate\" title=\"\u67e5\u627e 1=\u63d2\u5165\">\r\n\/\/ x-&gt;k&#x5B;0] &gt; k &gt; x-&gt;k&#x5B;1]\r\nnode*Find(DB k){\r\n    for (node*x=root;;){\r\n        if (x-&gt;k&#x5B;0]&lt;k) x=lx; else if (k&lt;x-&gt;k&#x5B;1]) x=rx;\r\n        else return x;\r\n    }\r\n}\r\n\r\nvoid Insert(node*z){\r\n    node*x=root,*y=NIL; for(;x!=NIL;y=x,x = x-&gt;c&#x5B;z-&gt;o&gt;x-&gt;o]);\r\n    if (y == NIL) root = z; else y-&gt;setc(z-&gt;o&gt;y-&gt;o, z);\r\n    z-&gt;fix();\r\n}\r\n<\/pre>\n<blockquote><p>\n\uff08\u6211\u4eec\u73b0\u5728\u63d2\u5165\u70b9P\uff0c\u5219\u70b9B\u548c\u70b9C\u5c06\u88ab\u5220\u9664\uff09<br \/>\n\u6700\u540e\u8ba8\u8bba\u5e73\u8861\u6811\u7684\u9009\u62e9\uff0c\u8fd9\u9898\u5b9e\u9645\u4e0a\u7528\u54ea\u79cd\u5e73\u8861\u6811\u90fd\u662f\u53ef\u4ee5\u7684\uff0c\u4f46\u6700\u65b9\u4fbf\u7684\u65e0\u7591\u662fSplay\uff0c\u5982\u679c\u6211\u4eec\u9009\u62e9\u63d2\u5165\u70b9P\uff0c\u90a3\u4e48\u6211\u4eec\u5c06\u70b9P\u65cb\u8f6c\u5230\u6839\u8282\u70b9\uff0c\u7136\u540e\u627e\u5230P\u7684\u524d\u9a71\uff08\u5373\u5de6\u5b50\u6811\u4e2d\u6700\u5927\u7684\uff09\uff0c\u5224\u65ad\u662f\u5426\u5220\u9664\uff0c\u5982\u679c\u5220\u9664\uff0c\u90a3\u4e48\u7ee7\u7eed\u4e0a\u8ff0\u8fc7\u7a0b\uff0c\u7136\u540e\u518d\u5bf9\u53f3\u5b50\u6811\u8fdb\u884c\u7ef4\u62a4\u3002\u6700\u7ec8\u590d\u6742\u5ea6O(nlogn)\uff0c\u5b8c\u5168\u53ef\u4ee5\u5bf9\u4ed8100000\u7684\u6570\u636e\u3002<br \/>\n\u6700\u540e\u60f3\u8bf4\u7684\u662f\uff0c\u8fd9\u9898\u7f16\u7a0b\u4e2d\u7684\u7ec6\u8282\u6bd4\u8f83\u591a\uff0c\u5982\u9047\u5230\u6a2a\u5750\u6807\u76f8\u540c\u7684\u70b9\u600e\u4e48\u529e\uff0c\u751a\u81f3\u6a2a\u7eb5\u5750\u6807\u90fd\u76f8\u540c\u7684\u70b9\u600e\u4e48\u529e\uff0c\u6240\u4ee5\u7f16\u7a0b\u4e4b\u524d\u8981\u60f3\u6e05\u695a\u4e00\u4e9b\u7ec6\u8282\u95ee\u9898\u3002<\/p>\n<\/blockquote>\n<p><a href=\"http:\/\/paste.ubuntu.com\/1473209\/\">Splay \u7ef4\u62a4\u51f8\u58f3\u3002\u3002\uff08\u659c\u7387\u3002\u3002600ms +- <\/a><br \/>\n<a href=\"http:\/\/paste.ubuntu.com\/1473189\/\">Splay \u7ef4\u62a4\u51f8\u58f3\u3002\u3002\uff08\u53c9\u79ef\u3002\u3002550ms&#8211;<\/a><\/p>\n<h3>External link: <\/h3>\n<p><a href=\"http:\/\/www.lydsy.com\/JudgeOnline\/problem.php?id=1492\">http:\/\/www.lydsy.com\/JudgeOnline\/problem.php?id=1492<\/a><br \/>\n<a href=\"http:\/\/hi.baidu.com\/oimaster\/item\/d8041f4a865444ee1f19bc43\">http:\/\/hi.baidu.com\/oimaster\/item\/d8041f4a865444ee1f19bc43<\/a><br \/>\n<a href=\"http:\/\/ideone.com\/8hGL1\">\u79cd\u7530\u541b\u3002\u3002<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>https:\/\/www.luogu.com.cn\/problem\/P4027 https:\/\/darkbzoj.tk\/problem\/1492 Brief description: &#8230;<\/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":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[22],"tags":[],"class_list":["post-613","post","type-post","status-publish","format-standard","hentry","category-bzoj"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-9T","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/613","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=613"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/613\/revisions"}],"predecessor-version":[{"id":614,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/613\/revisions\/614"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=613"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=613"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=613"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}