\u533a\u95f4\u6700\u503c\u67e5\u8be2\u95ee\u9898 RMQ\uff08Range Minimum\/Maximum Query\uff09 \u533a\u95f4\u6700\u503c\u67e5\u8be2\u95ee\u9898 \u7528ST\u8868\u89e3\u51b3\u95ee\u9898 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[41],"tags":[],"_links":{"self":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/423"}],"collection":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/comments?post=423"}],"version-history":[{"count":5,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/423\/revisions"}],"predecessor-version":[{"id":428,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/423\/revisions\/428"}],"wp:attachment":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/media?parent=423"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/categories?post=423"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/tags?post=423"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\n\u7528ST\u8868\u89e3\u51b3\u95ee\u9898\uff0c\u4e13\u95e8\u7528\u6765\u89e3\u51b3\u533a\u95f4\u6700\u503c\u95ee\u9898\u3002\u5bf9\u6570\u5217\u8fdb\u884cO(nlogn)\u5904\u7406\uff0cO(1)\u67e5\u8be2\u3002ST\u8868\u53ef\u4ee5\u89e3\u51b3\u7684\u95ee\u9898\uff0c\u7ebf\u6bb5\u6811\uff0c\u6811\u72b6\u6570\u7ec4\u90fd\u53ef\u4ee5\u89e3\u51b3\uff0c\u4f46\u540e\u4e24\u8005\u90fd\u662fO(nlogn)\u5904\u7406\uff0cO(mlogm)\u67e5\u8be2\u3002
\nST\u8868\u662f\u5229\u7528\u500d\u589e\u7684\u601d\u60f3\u3002\u8bbe\u6570\u7ec4f[i][j]\uff0c\u8868\u793a\u4ee5\u5143\u7d20i\u5f00\u5934\u7684\uff0c\u957f\u5ea6\u4e3a2^j<\/code>\u533a\u95f4\u5185\u7684\u6700\u503c\u3002\u679a\u4e3e\u957f\u5ea6\u56e0\u5b50j\uff0cf[i][j] = max(f[i][j-1]+f[i+(1<<j)][j]).
\n\u5177\u4f53\u770b\u4ee3\u7801\uff01
\n\u6d1b\u8c37P3865 ST\u8868<\/a><\/p>\n#include <bits\/stdc++.h>\nusing namespace std;\n#pragma GCC Opimize(2);\nconst int maxn = 1e5+15;\nint f[maxn][21];\nint read(){\n int f=1,x=0;char s=getchar();\n while (s<'0' || s>'9'){\n if (s=='-') f = -1;\n s=getchar();\n }\n while (s>='0' && s<='9'){\n x = x*10 + s - '0';\n s=getchar();\n }\n return x*f;\n}\ninline int max(int a,int b){\n return a>b?a:b;\n}\ninline int query(int l,int r){\n int x = r-l+1,k;\n for (k=0;x>1;k++)\n x >>= 1;\n return max(f[l][k],f[r-(1<<k)+1][k]);\n}\nint main(){\n int n,m,l,r;\n \/\/scanf ("%d %d",&n,&m);\n n = read(),m = read();\n for (int i=1;i<=n;i++) \/\/scanf ("%d",&f[i][0]);\n f[i][0] = read();\n for (int j=1;j<=18;j++){\n for (int i=1;i+(1<<j)-1<=n;i++)\n f[i][j] = max(f[i][j-1],f[i+(1<<(j-1))][j-1]);\n }\n for (int i=1;i<=m;i++){\n \/\/scanf ("%d %d",&l,&r);\n l = read(),r = read();\n printf ("%d\\n",query(l,r));\n }\n return 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"