{"id":2999,"date":"2023-06-08T06:39:17","date_gmt":"2023-06-07T22:39:17","guid":{"rendered":"https:\/\/www.shuizilong.com\/house\/?p=2999"},"modified":"2023-06-08T06:40:39","modified_gmt":"2023-06-07T22:40:39","slug":"luogu-p2048-noi2010-%e8%b6%85%e7%ba%a7%e9%92%a2%e7%90%b4","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/luogu-p2048-noi2010-%e8%b6%85%e7%ba%a7%e9%92%a2%e7%90%b4\/","title":{"rendered":"Luogu P2048. [NOI2010] \u8d85\u7ea7\u94a2\u7434"},"content":{"rendered":"<ul>\n<li><a href=\"https:\/\/darkbzoj.cc\/problem\/2006\">https:\/\/darkbzoj.cc\/problem\/2006<\/a><\/li>\n<li><a href=\"https:\/\/www.luogu.com.cn\/problem\/P2048\">https:\/\/www.luogu.com.cn\/problem\/P2048<\/a><\/li>\n<\/ul>\n<p>\u53ef\u4ee5\u5148\u5199\u4e00\u4e2a\u66b4\u529b RMQ \u89e3\u51b3 K=1 \u7684 10 \u5206\u4ee3\u7801\uff0c\u786e\u4fdd\u81ea\u5df1\u6ca1\u8bfb\u9519\u9898\u7406\u89e3\u6210\u5b57\u7b26\u4e32\u95ee\u9898\u4e86\u56e7\u3002<br \/>\n\u90a3\u4e48 top K \u53ef\u4ee5\u7528\u7c7b\u4f3c <a href=\"https:\/\/www.luogu.com.cn\/problem\/P2723\">[USACO3.1]\u4e11\u6570 Humble Numbers<\/a> \u90a3\u4e2a\u9898\u91cc\u7684\u65b9\u6cd5\uff0c\u5f00\u4e2a\u5806\uff0c\u6bcf\u6b21\u627e\u5230\u4e00\u4e2a\u6570\u5c31\u5206\u88c2\u4e00\u4e0b\u585e\u56de\u53bb\u3002<\/p>\n<p>\u8fd9\u4e2a\u9898\u6570\u636e\u91cf\u8db3\u591f\u5927\uff0c\u8be2\u95ee\u6570\u7ec4\u7684\u4e0b\u6807\u4ece 0 \u5f00\u59cb\uff0c\u8fd8\u8981\u8be2\u95ee rmq \u7684\u4f4d\u7f6e\uff0c\u975e\u5e38\u9002\u5408\u7528\u6211\u4eec\u65b0\u5b66\u4e60\u7684 <a href=\"https:\/\/www.shuizilong.com\/house\/archives\/on-on-o1-rmq\/\">O(n)-O(1) RMQ<\/a> \u5927\u663e\u8eab\u624b\uff01\u3002\u3002\u3002<\/p>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n#include &lt;lastweapon\/bitwise&gt;\r\n\r\nusing namespace lastweapon;\r\n\r\nconst int N = int(5e5) + 9;\r\nint s&#x5B;N];\r\nint n, K, L, R;\r\n\r\ntemplate&lt;typename T&gt; struct rmq {\r\n\tvector&lt;T&gt; v; int n;\r\n\tstatic const int b = 30; \/\/ block size\r\n\tvector&lt;int&gt; mask, t; \/\/ mask and sparse table\r\n\r\n\tint op(int x, int y) {\r\n\t\treturn v&#x5B;x] &lt; v&#x5B;y] ? x : y;\r\n\t}\r\n\t\/\/ least significant set bit\r\n\tint lsb(int x) {\r\n\t\treturn x &amp; -x;\r\n\t}\r\n\t\/\/ index of the most significant set bit\r\n\tint msb_index(int x) {\r\n\t\treturn __builtin_clz(1)-__builtin_clz(x);\r\n\t}\r\n\t\/\/ answer query of v&#x5B;r-size+1..r] using the masks, given size &lt;= b\r\n\tint small(int r, int size = b) {\r\n\t\t\/\/ get only 'size' least significant bits of the mask\r\n\t\t\/\/ and then get the index of the msb of that\r\n\t\tint dist_from_r = msb_index(mask&#x5B;r] &amp; ((1&lt;&lt;size)-1));\r\n\r\n\t\treturn r - dist_from_r;\r\n\t}\r\n\r\n\trmq(){}\r\n\r\n\trmq(const vector&lt;T&gt;&amp; v_) : v(v_), n(v.size()), mask(n), t(n) {\r\n\t\tint curr_mask = 0;\r\n\t\tfor (int i = 0; i &lt; n; i++) {\r\n\r\n\t\t\t\/\/ shift mask by 1, keeping only the 'b' least significant bits\r\n\t\t\tcurr_mask = (curr_mask&lt;&lt;1) &amp; ((1&lt;&lt;b)-1);\r\n\r\n\t\t\twhile (curr_mask &gt; 0 and op(i, i - msb_index(lsb(curr_mask))) == i) {\r\n\t\t\t\t\/\/ current value is smaller than the value represented by the\r\n\t\t\t\t\/\/ last 1 in curr_mask, so we need to turn off that bit\r\n\t\t\t\tcurr_mask ^= lsb(curr_mask);\r\n\t\t\t}\r\n\t\t\t\/\/ append extra 1 to the mask\r\n\t\t\tcurr_mask |= 1;\r\n\r\n\t\t\tmask&#x5B;i] = curr_mask;\r\n\t\t}\r\n\r\n\t\t\/\/ build sparse table over the n\/b blocks\r\n\t\t\/\/ the sparse table is linearized, so what would be at\r\n\t\t\/\/ table&#x5B;j]&#x5B;i] is stored in table&#x5B;(n\/b)*j + i]\r\n\t\tfor (int i = 0; i &lt; n\/b; i++) t&#x5B;i] = small(b*i+b-1);\r\n\t\tfor (int j = 1; (1&lt;&lt;j) &lt;= n\/b; j++) for (int i = 0; i+(1&lt;&lt;j) &lt;= n\/b; i++)\r\n\t\t\tt&#x5B;n\/b*j+i] = op(t&#x5B;n\/b*(j-1)+i], t&#x5B;n\/b*(j-1)+i+(1&lt;&lt;(j-1))]);\r\n\t}\r\n\t\/\/ query(l, r) returns the actual minimum of v&#x5B;l..r]\r\n\t\/\/ to get the index, just change the first and last lines of the function\r\n\tT query(int l, int r) {\r\n\t\t\/\/ query too small\r\n\t\t\/\/if (r-l+1 &lt;= b) return v&#x5B;small(r, r-l+1)];\r\n\t\tif (r-l+1 &lt;= b) return small(r, r-l+1);\r\n\r\n\t\t\/\/ get the minimum of the endpoints\r\n\t\t\/\/ (there is no problem if the ranges overlap with the sparse table query)\r\n\t\tint ans = op(small(l+b-1), small(r));\r\n\r\n\t\t\/\/ 'x' and 'y' are the blocks we need to query over\r\n\t\tint x = l\/b+1, y = r\/b-1;\r\n\r\n\t\tif (x &lt;= y) {\r\n\t\t\tint j = msb_index(y-x+1);\r\n\t\t\tans = op(ans, op(t&#x5B;n\/b*j+x], t&#x5B;n\/b*j+y-(1&lt;&lt;j)+1]));\r\n\t\t}\r\n\r\n\t\t\/\/return v&#x5B;ans];\r\n\t\treturn ans;\r\n\t}\r\n};\r\n\r\n\r\nrmq&lt;int&gt; T;\r\n\r\nstruct rec {\r\n    int i, l, r, m, f;\r\n    rec(int i, int l, int r) : i(i), l(l), r(r), m(T.query(l, r)) {\r\n        f = s&#x5B;i] - s&#x5B;m];\r\n    }\r\n    bool operator &lt; (const rec&amp; r) const {\r\n        return f &lt; r.f;\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;\/Users\/minakokojima\/Documents\/GitHub\/ACM-Training\/Workspace\/out.txt&quot;, &quot;w&quot;, stdout);\r\n#endif\r\n\r\n    RD(n, K, L, R);\r\n\r\n    VI a; a.PB(0);\r\n    REP_1(i, n) RD(s&#x5B;i]) += s&#x5B;i-1], a.PB(s&#x5B;i]); a.pop_back();\r\n\r\n    T = rmq&lt;int&gt;(a);\r\n\r\n    priority_queue&lt;rec&gt; Q;\r\n    FOR_1(i, L, n) {\r\n        Q.push(rec(i, max(0, i-R), i-L));\r\n    }\r\n\r\n    LL z = 0; DO(K) {\r\n        auto u = Q.top(); Q.pop(); z += u.f;\r\n        if (u.m != u.l) Q.push(rec(u.i, u.l, u.m-1));\r\n        if (u.m != u.r) Q.push(rec(u.i, u.m+1, u.r));\r\n    }\r\n\r\n    cout &lt;&lt; z &lt;&lt; endl;\r\n}\r\n\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>https:\/\/darkbzoj.cc\/problem\/2006 https:\/\/www.luogu.com.cn\/problem\/P2048 \u53ef\u4ee5\u5148\u5199\u4e00\u4e2a\u66b4\u529b RMQ \u89e3\u51b3 K=1 \u7684 10 \u5206\u4ee3\u7801\uff0c\u786e\u4fdd\u81ea\u5df1\u6ca1\u8bfb\u9519\u9898\u7406\u89e3\u6210\u5b57\u7b26\u4e32\u95ee\u9898\u4e86\u56e7\u3002 \u90a3\u4e48 top K \u53ef\u4ee5\u7528\u7c7b\u4f3c [USACO3.1]\u4e11\u6570 Humble Numbers \u90a3\u4e2a\u9898\u91cc\u7684\u65b9\u6cd5\uff0c\u5f00\u4e2a\u5806\uff0c\u6bcf\u6b21\u627e\u5230\u4e00\u4e2a\u6570\u5c31\u5206\u88c2\u4e00\u4e0b\u585e\u56de\u53bb\u3002 \u8fd9\u4e2a\u9898\u6570\u636e\u91cf\u8db3\u591f\u5927\uff0c\u8be2\u95ee\u6570\u7ec4\u7684\u4e0b\u6807\u4ece 0 \u5f00\u59cb\uff0c\u8fd8\u8981\u8be2\u95ee rmq \u7684\u4f4d\u7f6e\uff0c\u975e\u5e38\u9002\u5408\u7528\u6211\u4eec\u65b0\u5b66\u4e60\u7684 O(n)-O(1) RMQ \u5927\u663e\u8eab\u624b\uff01\u3002\u3002\u3002 #include &lt;lastweapon\/bitwise&gt; using namespace lastweapon; const int N = int(5e5) + 9; int s&#x5B;N]; int n, K, L, R; template&lt;typename T&gt; struct rmq { vector&lt;T&gt; v; int n; static const [&hellip;]<\/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":[1],"tags":[],"class_list":["post-2999","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-Mn","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/2999","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=2999"}],"version-history":[{"count":4,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/2999\/revisions"}],"predecessor-version":[{"id":3003,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/2999\/revisions\/3003"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=2999"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=2999"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=2999"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}