\u4e8c\u7ef4ST\u7b97\u6cd5<\/figcaption><\/figure>\n\u5176\u52a8\u89c4\u8f6c\u79fb\u65b9\u7a0b\u4e3a<\/p>\n
\n\\(f[x][y][i][j] = \\left\\{ {\\begin{array}{ll}{\\max \\left\\{ {\\begin{array}{ll}{f[x][y][i][j - 1]} \\\\{f[x][y + 2^{j - 1} ][i][j - 1]} \\\\\\end{array}} \\right.} & i=0\\\\{\\max \\left\\{ \\begin{array}{ll}f[x][y][i - 1][j] \\\\f[x + 2^{i - 1} ][y]i - 1][j] \\\\\\end{array} \\right.} & i\\ne 0 \\\\\\end{array}} \\right.\\)\n<\/p>\n
\n \u89e3\u91ca\uff1a<\/strong>
\n\u6bcf\u6b21DP\uff0c\u82e5\u662f\u5355\u884c(i=0)\uff0c\u5219\u6309\u4e00\u7ef4\u65b9\u5f0fDP
\n\u82e5\u4e0d\u662f\uff0c\u5c06\u76ee\u6807\u533a\u57df\u5206\u5272\u4e3a\u4e0a\u4e0b\u4e24\u90e8\u5206(\u9ec4\uff0c\u7eff)\uff0c\u53d6\u5176\u6700\u503c\u5373\u53ef
\n\u6211\u81ea\u5df1\u60f3\u7684DP\u548c\u5927\u90e8\u5206\u4eba\u7684\u4e0d\u4e00\u6837\uff0cDP\u65f6\u5c06\u76ee\u6807\u533a\u57df\u5341\u5b57\u5747\u5206\u4e3a4\u4efd\u6c42\u6700\u503c(\u548c\u4e0b\u9762\u7684\u67e5\u8be2\u5dee\u4e0d\u591a)\u800c\u4e14\u4ee3\u7801\u957f\uff0c\u6548\u7387\u53ef\u80fd\u4e5f\u4f4e\uff0c\u8d34\u5728\u540e\u9762\u3002
\n\u67e5\u8be2\u65f6\uff0c\u5c06\u76ee\u6807\u533a\u57df\u5341\u5b57\u5e73\u5206\u4e3a4\u4efd\uff0c\u53d6\u5176\u6700\u503c
\n\u5e16\u4ee3\u7801:\n<\/p>\n\r\n#include \r\n#include \r\n#include \r\n#define max(x,y) (x)>(y)?(x):(y)\r\nusing namespace std;\r\nint f[300][300][11][11];\/\/x,y,\u9ad8\uff0c\u5bbd \r\nint R,C,M;\r\ninline void build();\r\ninline void build2();\/\/Comzyh\u5199\u7684 \r\ninline int get (int x1,int y1,int x2,int y2);\r\nint main(){\r\n int i,j;\r\n cin >> R >> C;\r\n for (i=1;i<=R;i++)\r\n for (j=1;j<=C;j++)\r\n cin >> f[i][j][0][0];\r\n build();\r\n cout << \"Please enter M ...\" << endl;\r\n cin >> M;\r\n int x1,y1,x2,y2;\r\n for (i=1;i<=M;i++){\r\n cin >> x1 >> y1 >> x2 >> y2;\r\n cout << get (x1,y1,x2,y2) << endl;\r\n }\r\n \r\n system(\"pause\");\r\n\r\n }s\r\ninline void build (){\r\n int i,j,x,y;\r\n for (i=0;(1<?\r\n f[x][y+(1<?\r\n f[x+(1<?\r\n f[x1 ][y2 - (1<?\r\n ( f[x2-(1<?\r\n f[x2-(1<\n\u6211\u7684Build\u51fd\u6570,\u4e00\u5f00\u59cb\u8981\u5148\u4e00\u7ef4DP f[x][y][i][0]\u548cf[x][y][0][j],\u8c8c\u4f3c\u4e0d\u548b\u597d,\u732e\u4e11 <\/p>\n
\r\ninline void build2(){\/\/Comzyh\u7684\u521d\u59cb\u5316\uff0c\u6548\u7387\u4e0d\u9ad8 \uff0c\u732e\u4e11 \r\n int i,j,x,y;\r\n \/\/\u521d\u59cb\u5316f[x][y][0][j]; \r\n for (j=1;(1<? f[x][y+(1<<(j-1))][0][j-1]; \r\n \/\/\u521d\u59cb\u5316f[x][y][i][0]; \r\n for (i=1;(1<? f[x+(1<<(i-1))][y][i-1][0];\r\n \/\/DP\r\n for (i=1;(1<?\r\n f[x+(1<?\r\n ( f[x ][y+(1<?\r\n f[x+(1<\n\u5c0f\u7ed9\u4e00\u7ec4\u81ea\u521b\u6d4b\u8bd5\u6570\u636e,\u633a\u5f3a\u7684\u3002
\n\u683c\u5f0f:
\n\u884c\u6570,\u5217\u6570()
\n\u77e9\u9635
\n\u8bf7\u6c42\u6b21\u6570M
\nM\u884c\uff0cX1,X2,Y1,Y2<\/p>\n
\r\nInput\uff1a\r\n10 10\r\n1\t2\t3\t4\t5\t6\t7\t8\t9\t10\r\n10\t9\t8\t7\t6\t5\t4\t3\t2\t1\r\n1\t6\t4\t23\t8\t41\t25\t41\t3\t4\r\n5\t4\t85\t1\t2\t1\t5\t1\t32\t2\r\n4\t52\t1\t5\t5\t2\t3\t1\t5\t5\r\n0\t0\t0\t0\t0\t0\t0\t0\t0\t0\r\n1\t63\t1\t3\t14\t5\t10\t0\t0\t1\r\n5\t6\t1\t9\t1\t0\t1\t6\t1\t1\r\n1\t1\t1\t1\t1\t1\t1\t1\t1\t1\r\n1\t1\t1\t1\t1\t1\t1\t1\t1\t1\r\n6\r\n1 1 10 10\r\n1 9 10 10\r\n1 1 5 2 \r\n6 6 10 10\r\n9 9 10 10\r\n6 5 8 7 \r\n\r\n\u7b54\u6848\u5c31\u4e0d\u7ed9\u4e86\r\n<\/pre>\n\u6ce8\u610f\uff0c\">?\" \u662fC++\u4e2d\u8f83\u5927\u503c\u8fd0\u7b97\u7b26\uff0c\u7ed3\u679c\u4e3a\u7b26\u53f7\u5de6\u53f3\u8f83\u5927\u7684\u90a3\u4e2a\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"
RMQ(range minimum\/maximum query)\u95ee\u9898 \u7ed9\u5b9a\u4e00\u7ec4\u6570\uff0c\u7ed9\u5b9a\u7ed9\u5b9a\u4e00\u4e2a\u533a\u95f4\uff0c\u6c42\u533a\u95f4\u6700\u503c […]<\/p>\n","protected":false},"author":2,"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":[9],"tags":[22,43,41,42],"class_list":["post-273","post","type-post","status-publish","format-standard","hentry","category-9","tag-nlogn","tag-o1","tag-rmq","tag-42"],"jetpack_publicize_connections":[],"aioseo_notices":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p6XQWE-4p","jetpack-related-posts":[],"jetpack_likes_enabled":true,"_links":{"self":[{"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/posts\/273","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/comments?post=273"}],"version-history":[{"count":10,"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/posts\/273\/revisions"}],"predecessor-version":[{"id":900,"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/posts\/273\/revisions\/900"}],"wp:attachment":[{"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/media?parent=273"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/categories?post=273"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/tags?post=273"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
![\"ST\u7b97\u6cd5\u7684\u533a\u95f4\u5206\u5272\"](\"https:\/\/i0.wp.com\/comzyh.com\/upload\/wordpress\/\/\/\/\/2010\/10\/RMQ1.png?resize=346%2C144\" "\\"ST\u7b97\u6cd5\u7684\u533a\u95f4\u5206\u5272\\"")
<\/a>