{"id":114,"date":"2026-03-28T18:45:29","date_gmt":"2026-03-28T10:45:29","guid":{"rendered":"https:\/\/\u9f50\u6cb3\u4e00\u4e2d.cn\/blog\/?p=114"},"modified":"2026-03-28T18:45:29","modified_gmt":"2026-03-28T10:45:29","slug":"%e5%80%8d%e5%a2%9e%e4%b8%8est%e8%a1%a8","status":"publish","type":"post","link":"https:\/\/\u9f50\u6cb3\u4e00\u4e2d.cn\/blog\/index.php\/2026\/03\/28\/%e5%80%8d%e5%a2%9e%e4%b8%8est%e8%a1%a8\/","title":{"rendered":"\u500d\u589e\u4e0eST\u8868"},"content":{"rendered":"\n<p>\u6a21\u7248\u9898: <a href=\"https:\/\/www.luogu.com.cn\/problem\/P2880\">https:\/\/www.luogu.com.cn\/problem\/P2880<\/a><\/p>\n\n\n\n<p>\u52a8\u753b\u89e3\u6790: <a href=\"https:\/\/www.bilibili.com\/video\/BV1pTr8BsEgK\/\">https:\/\/www.bilibili.com\/video\/BV1pTr8BsEgK\/<\/a><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include &lt;iostream>\n#include &lt;cmath>\n#include &lt;vector>\n\nusing namespace std;\ntypedef long long ll;\nint a&#91;2000000], stmax&#91;60000]&#91;600], stmin&#91;60000]&#91;600], p1&#91;60000];\nint n, m;\n\n\n\nint main() {\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    \n    cin >> n >> m;\n    \n    for (int i=1;i&lt;=n;i++) cin >> a&#91;i];\n    \/\/ \u9884\u5904\u7406\u6570\u636e\n    p1&#91;1] = 0;\n    for (int x=2;x&lt;=n;x++) {\n    \tp1&#91;x] = p1&#91;x\/2] + 1;\n    }\n    \n    for (int i=1;i&lt;=n;i++) {\n    \tstmax&#91;i]&#91;0] = a&#91;i];\n    \tstmin&#91;i]&#91;0] = a&#91;i];\n    }\n    for (int p=1;1 &lt;&lt; p &lt;= n;p++) {\n    \tfor (int i=1;i + (1 &lt;&lt; p) - 1 &lt;= n;i++) {\n    \t\tint tmp = i + (1 &lt;&lt; (p - 1));\n    \t\tstmax&#91;i]&#91;p] = max(stmax&#91;i]&#91;p-1], stmax&#91;tmp]&#91;p-1]);\n    \t\tstmin&#91;i]&#91;p] = min(stmin&#91;i]&#91;p-1], stmin&#91;tmp]&#91;p-1]);\n\t}\n    }\n\t\n\tfor (int i=1;i&lt;=m;i++) {\n\t\tint a, b;\n\t\tcin >> a >> b;\n\t\tint k = p(b - a + 1); \/\/ \u53ef\u66ff\u6362\u4e3alog2(b - a + 1)\n\t\tcout &lt;&lt; max(stmax&#91;a]&#91;k], stmax&#91;b - (1 &lt;&lt; k) + 1]&#91;k]) - min(stmin&#91;a]&#91;k], stmin&#91;b - (1 &lt;&lt; k) + 1]&#91;k]) &lt;&lt; endl;\n\t}\n    return 0;\n}<\/code><\/pre>\n\n\n\n<p>\u5176\u4e2d<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>1 &lt;&lt; p<\/code><\/pre>\n\n\n\n<p>\u662f\u5c06p\u7684\u4e8c\u8fdb\u5236\u60f3\u53f3\u79fb\u52a8\u4e00\u4f4d\uff0c\u5373\u6210\u4e8c\u3002\u4ee5\u4e0a\u4ee3\u7801\u7b49\u4ef7\u4e8e1 * 2 \u4e58\u65b9 p<\/p>\n\n\n\n<p>\u6b64\u5916\uff0c\u8fd8\u8981\u6ce8\u610f<strong>\u4f55\u65f6\u52a01\u4f55\u65f6\u51cf\u4e00<\/strong><\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u6a21\u7248\u9898: https:\/\/ww&#8230;<\/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-114","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/\u9f50\u6cb3\u4e00\u4e2d.cn\/blog\/index.php\/wp-json\/wp\/v2\/posts\/114","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/\u9f50\u6cb3\u4e00\u4e2d.cn\/blog\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/\u9f50\u6cb3\u4e00\u4e2d.cn\/blog\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/\u9f50\u6cb3\u4e00\u4e2d.cn\/blog\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/\u9f50\u6cb3\u4e00\u4e2d.cn\/blog\/index.php\/wp-json\/wp\/v2\/comments?post=114"}],"version-history":[{"count":1,"href":"https:\/\/\u9f50\u6cb3\u4e00\u4e2d.cn\/blog\/index.php\/wp-json\/wp\/v2\/posts\/114\/revisions"}],"predecessor-version":[{"id":115,"href":"https:\/\/\u9f50\u6cb3\u4e00\u4e2d.cn\/blog\/index.php\/wp-json\/wp\/v2\/posts\/114\/revisions\/115"}],"wp:attachment":[{"href":"https:\/\/\u9f50\u6cb3\u4e00\u4e2d.cn\/blog\/index.php\/wp-json\/wp\/v2\/media?parent=114"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/\u9f50\u6cb3\u4e00\u4e2d.cn\/blog\/index.php\/wp-json\/wp\/v2\/categories?post=114"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/\u9f50\u6cb3\u4e00\u4e2d.cn\/blog\/index.php\/wp-json\/wp\/v2\/tags?post=114"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}