{"id":258,"date":"2006-07-24T20:11:00","date_gmt":"2006-07-24T12:11:00","guid":{"rendered":"http:\/\/114414"},"modified":"2006-07-24T20:11:00","modified_gmt":"2006-07-24T12:11:00","slug":"rmq","status":"publish","type":"post","link":"https:\/\/www.yewen.us\/blog\/2006\/07\/rmq\/","title":{"rendered":"RMQ"},"content":{"rendered":"<p>\u4ece<a href=\"http:\/\/whummd.blog.edu.cn\/\" target=\"_blank\">whummd<\/a>\u7684blog\u4e0acopy\u6765\u7684,\u52a0\u4e86\u70b9\u81ea\u5df1\u7684\u4fee\u6539,\u6b63\u5728\u770b,\u96c6\u8bad\u52a0\u6cb9<\/p>\n<pre class=\"brush: cpp; title: ; notranslate\" title=\"\">\/\/ StandCode for RMQ, return the smallest number in array s&#x5B;i..j]\n#include &amp;lt;iostream&amp;gt;\n#include &amp;lt;cmath&amp;gt;\nusing namespace std;\n#define MAXN 1000000\nint f2&#x5B;30];\nint s&#x5B;MAXN];\nint r&#x5B;MAXN]&#x5B;22];\n\nvoid make_f2(int n)\n{\n    int i;\n    for(i=0;i&amp;lt;=n;i++)\n        f2&#x5B;i]=1&amp;lt;&amp;lt;i;\n    return;\n}\n\nvoid make_RMQ(int n)\n{\n    int i,j;\n    for(i=1;i&amp;lt;=n;i++)\n        r&#x5B;i]&#x5B;0]=s&#x5B;i];\n    for(j=1;j&amp;lt;=log(n)\/log(2);j++)\n        for(i=1;i&amp;lt;=n;i++)\n            r&#x5B;i]&#x5B;j]=min(r&#x5B;i]&#x5B;j-1],r&#x5B;i+f2&#x5B;j-1]]&#x5B;j-1]);\n    return;\n}\n\nint RMQ(int i,int j)\n{\n    int k=int(log(j-i+1)\/log(2));\n    return(min(r&#x5B;i]&#x5B;k],r&#x5B;j-f2&#x5B;k]+1]&#x5B;k]));\n}\n\nint main()\n{\n    freopen(&quot;rmp.in&quot;,&quot;r&quot;,stdin);\n    freopen(&quot;rmp.out&quot;,&quot;w&quot;,stdout);\n\n    int n,i,start,end;\n    scanf(&quot;%d&quot;,&amp;amp;n);\n    for(i=1;i&amp;lt;=n;i++)\n        scanf(&quot;%d&quot;,&amp;amp;s&#x5B;i]);\n    make_f2(20);\n    make_RMQ(n);\n    while(scanf(&quot;%d%d&quot;,&amp;amp;start,&amp;amp;end)!=EOF)\n        printf(&quot;%dn&quot;,RMQ(start,end));\n    return 0;\n}<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u4ecewhummd\u7684blog\u4e0acopy\u6765\u7684,\u52a0\u4e86\u70b9\u81ea\u5df1\u7684\u4fee\u6539,\u6b63\u5728\u770b,\u96c6\u8bad\u52a0\u6cb9 \/\/ StandCode for  [&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":""},"categories":[7,11],"tags":[132,315,435],"class_list":["post-258","post","type-post","status-publish","format-standard","hentry","category-tech-notes","category-contests","tag-rmq","tag-315","tag-435"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/s4aR5e-rmq","_links":{"self":[{"href":"https:\/\/www.yewen.us\/blog\/wp-json\/wp\/v2\/posts\/258","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.yewen.us\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.yewen.us\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.yewen.us\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.yewen.us\/blog\/wp-json\/wp\/v2\/comments?post=258"}],"version-history":[{"count":0,"href":"https:\/\/www.yewen.us\/blog\/wp-json\/wp\/v2\/posts\/258\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.yewen.us\/blog\/wp-json\/wp\/v2\/media?parent=258"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.yewen.us\/blog\/wp-json\/wp\/v2\/categories?post=258"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.yewen.us\/blog\/wp-json\/wp\/v2\/tags?post=258"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}