{"id":317,"date":"2010-07-23T13:38:28","date_gmt":"2010-07-23T05:38:28","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=317"},"modified":"2012-07-25T02:34:09","modified_gmt":"2012-07-24T18:34:09","slug":"mipt-105-rmq-problem","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/mipt-105-rmq-problem\/","title":{"rendered":"MIPT 105. RMQ problem"},"content":{"rendered":"

Brief description: <\/h3>\n

… RMQ \u6a21\u677f\u9898\u3002\u3002\uff08\u65e0\u4fee\u6539\u3002\u3002\u591a\u8be2\u95ee\u3002\u3002\u3002<\/p>\n

<\/p>\n

Analysis: <\/h3>\n

… \uff08\u7ebf\u6bb5\u6811\u76f4\u63a5 T \u4e0d\u89e3\u91ca\u3002\u3002<\/p>\n

\r\n#include <iostream>\r\n#include <cstdio>\r\n#include <cstring>\r\n#include <cmath>\r\nusing namespace std;\r\ninline int _1(int x){return 1 << x;}\r\ninline void RD(int &x){scanf("%d", &x);}\r\n\r\n\/*----*\/\r\n\r\nconst int L = 19, N = 250000;\r\n\r\nfloat ST[L][N];\r\nint n, m, i, j, a, b, lv, up;\r\n\r\nint main(){\r\n\r\n    freopen("in.txt", "r", stdin);\r\n\r\n    RD(n); for(i=0;i<n;++i) scanf("%f", &ST[0][i]);\r\n\r\n    for (up = log2(n), lv = 1; lv <= up; ++ lv)\r\n        for (i = 0; i <= n - _1(lv); ++i)\r\n            ST[lv][i] = min(ST[lv - 1][i], ST[lv - 1][i + _1(lv - 1)]);\r\n\r\n    RD(m); while (m--){\r\n        RD(a), RD(b), lv = log2(b - a);\r\n        printf("%.6f\\n", min(ST[lv][a], ST[lv][b - _1(lv)]));\r\n    }\r\n}\r\n\r\n<\/pre>\n
 \r\n#include <iostream>\r\n#include <cstdio>\r\n#include <cstring>\r\n#include <cmath>\r\nusing namespace std;\r\ntemplate<class T> inline void checkMin(T &a,const T b){if (b<a) a=b;}\r\ntemplate<class T> inline T low_bit(T x) {return x & -x;}\r\ninline void RD(int &x){scanf("%d", &x);}\r\n\r\n\/*----*\/\r\n\r\nconst int N = 250001;\r\n\r\nfloat A[N], C[N], res;\r\nint n, m, i, j, a, b;\r\n\r\nint main(){\r\n\r\n    \/\/freopen("in.txt", "r", stdin);\r\n\r\n    RD(n); for(i=1;i<=n;++i) scanf("%f", &A[i]), C[i] = A[i];\r\n\r\n    for (i=1;i<=n;++i)\r\n        for (j=1;j<low_bit(i);j<<=1)\r\n            checkMin(C[i], C[i-j]);\r\n\r\n    RD(m); while (m--){\r\n        RD(a), RD(b), ++a, res = A[b];\r\n        while (b!=a){\r\n            for (--b;b-a>=low_bit(b);b-=low_bit(b)) checkMin(res, C[b]);\r\n            checkMin(res, A[b]);\r\n        }\r\n\r\n        printf("%.6f\\n", res);\r\n    }\r\n}\r\n\r\n<\/pre>\n
(\u6b63\u5e38\u5411\u3002\u3002\u3002
\n(2.10s +- \u3002\u3002
\n(3.35s +- \u3002\u3002\u3002<\/p>\n
 \r\n#include<iostream>\r\n#include<cmath>\r\nfloat a[19][250000];\r\nint n,i,j,t;main(){\r\n    for(scanf("%d",&n),i=0;i<n;++i)scanf("%f",a[0]+i);\r\n    for(t=log2(n),i=1;i<=t;++i)for(j=0;j<=n-(1<<i);++j)a[i][j]=std::min(a[i-1][j],a[i-1][j+(1<<i-1)]);\r\n    for(scanf("%d",&n);n--;)scanf("%d%d",&i,&j),t=log2(j-i),printf("%.6f\\n",std::min(a[t][i],a[t][j-(1<<t)]));\r\n}\r\n<\/pre>\n
 \r\n#include <cstdio>\r\n#define M(a,b) if (b<a) a=b;\r\n#define B(x) (x&-x)\r\nconst int N = 250001;\r\nfloat A[N], C[N], r;\r\nint n, i, j; main(){\r\n\r\n    for(scanf("%d", &n), i=1;i<=n;++i) scanf("%f", &A[i]), C[i] = A[i];\r\n    for (i=1;i<=n;++i) for (j=1;j<B(i);j<<=1) M(C[i], C[i-j]);\r\n\r\n    for(scanf("%d",&n);n--;){\r\n        scanf("%d%d",&i,&j),++i,r=A[j];\r\n        while (i!=j){\r\n            for (--j;j-i>=B(j);j-=B(j)) M(r, C[j]);\r\n            M(r, A[j]);\r\n        }\r\n        printf("%.6f\\n",r);\r\n    }\r\n}\r\n\r\n<\/pre>\n
( \u9b3c\u755c\u7f29\u7801\u7248\u3002\u3002\u3002
\n(174cm \u3002\u3002\u3002
\n(\u3002206cm \u3002\u3002\u8fd9\u5c3c\u739b\u8be2\u95ee\u8fc7\u7a0b\u4e5f\u592a\u957f\u4e86\u3002\u3002\u5b9e\u5728\u662f\u7f29\u4e0d\u52a8\u554a\u3002\u3002\u3002<\/p>\n
External link: <\/h3>\n
http:\/\/acm.mipt.ru\/judge\/problems.pl?problem=105<\/a><\/p>\n
http:\/\/richardxx.yo2.cn\/articles\/bit_rmq.html<\/a>
\nhttp:\/\/www.cnblogs.com\/ambition\/archive\/2011\/04\/06\/bit_rmq.html<\/a>
\n<\/a><\/p>\n
http:\/\/www.cppblog.com\/MatoNo1\/archive\/2011\/03\/19\/142238.html<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"
Brief description: … RMQ \u6a21\u677f\u9898\u3002\u3002\uff08\u65e0\u4fee\u6539\u3002\u3002\u591a\u8be2\u95ee\u3002\u3002\u3002<\/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":[16],"tags":[],"class_list":["post-317","post","type-post","status-publish","format-standard","hentry","category-online-judge"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-57","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/317","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=317"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/317\/revisions"}],"predecessor-version":[{"id":318,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/317\/revisions\/318"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=317"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=317"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=317"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}