\u7ed9\u5b9a\u4e00\u7ec4\u533a\u95f4\uff0c\u6bcf\u6b21\u8be2\u95ee [a, b] \u533a\u95f4\u5185\u7b2c k \u5c0f\u7684\u6570\u3002
\n.. .<\/p>\n
<\/p>\n
\u2014\u2014\u2014\u2014 UPD \u2014\u2014\u2014\u2014\u2014\u2014 … \u533a\u95f4 k \u5c0f\u6570\u95ee\u9898\uff0c\u8fd9\u7c7b\u95ee\u9898\u5f15\u51fa\u7684\u7b97\u6cd5\u5f88\u591a\uff0c\u4e92\u76f8\u4e4b\u95f4\u90fd\u6709\u8054\u7cfb\uff0c\u540c\u65f6\u95ee\u9898\u672c\u8eab\u4e5f\u6709\u8bf8\u591a\u6269\u5c55\u548c\u53d8\u5f62\uff0c\u5fc5\u987b\u505a\u603b\u7ed3\u3002 \u4ee5 A = { 1, 7, 2, 5, 8, 3, 4, 6 } \u4e3a\u4f8b\uff0c\u4e0b\u9762\u7ed9\u51fa\u56fe\u793a\uff1a<\/p>\n \u50cf\u8fd9\u6837\u628a\u5f52\u5e76\u6392\u5e8f (Merge Sort<\/a>) \u4e2d\uff0c \u5bf9\u4e8e\u5f52\u5e76\u6811\uff0c\u5bb9\u6613\u56de\u7b54 x \u5728\u5f53\u524d\u533a\u95f4\u4e2d\u7684\u6392\u540d\uff0c\u56e0\u800c\u53ef\u4ee5\u8bbe\u8ba1\u4e00\u4e2a\u7ed9\u4e88\u4e8c\u5206\u7b54\u6848\u7684\u7b97\u6cd5\u3002 \u800c\u5bf9\u4e8e\u5212\u5206\u6811\uff0c\u53ef\u4ee5\u76f4\u63a5\u5b8c\u6210\u4e0a\u8ff0\u8be2\u95ee\u4e0d\u9700\u8981\u4e8c\u5206\u7b54\u6848\uff0c\u65b9\u6cd5\u662f\u518d\u5212\u5206\u6811\u7684\u57fa\u7840\u4e0a\u5efa\u7acb\u4e00\u4e2a\u8f85\u52a9\u6811 (Auxiliary Tree)\u3002 \u8fd9\u6837\u5177\u4f53\u662f\u5bf9\u4e8e\u8be2\u95ee ([a, b], k)\uff0c\u53ef\u4ee5\u786e\u5b9a\u6700\u7ec8\u7b54\u6848\u662f\u5728\u5de6\u5b50\u6811\u8fd8\u662f\u5728\u53f3\u5b50\u6811\u5185\uff0c \uff08\u4ee3\u7801 \u2192\u8fd9\u91cc<\/a>\u3002<\/p>\n \u6ce8\u610f\u901a\u5e38\u6211\u4eec\u53ea\u9700\u8981 Auxiliary Tree\uff0c\u800c\u4e0d\u9700\u8981\u5212\u5206\u6811\uff0c\u4e3a\u4e86\u8282\u7ea6\u7a7a\u95f4\u5f00\u9500\uff0c\u6211\u4eec\u53ea\u9700\u8981\u4fdd\u5b58\u5176 Auxiliary Tree \u5c31\u597d\u3002 \u5f52\u5e76\u6811\u4ee3\u7801\u79fb\u6b65 \u2192\u8fd9\u91cc<\/a> \u3002\u3002\u3002 \u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014 UPD\uff1a \u8fd9\u6837\u5bf9\u4e8e\u6bcf\u4e2a\u8be2\u95ee ([a, b], k)\uff0c\u4ece\u7ebf\u6bb5\u6811\u7684\u6839\u8282\u70b9\u5f00\u59cb\uff0c\u6bcf\u6b21\u6839\u636e\u5de6\u5b50\u6811\u4e0b\u6807\u5206\u5e03\u5728 [a, b] \u533a\u95f4\u4e2d\u6570\u5b57\u7684\u4e2a\u6570, .. \u5b8c\u6574\u4ee3\u7801<\/a>\u3002\u3002\uff09<\/p>\n \u6211\u4eec\u53d1\u73b0\u8fd9\u79cd \u201c\u7ebf\u6bb5\u6811\u201d \u5176\u5b9e\u5bf9\u5e94\u5212\u5206\u6811\u7684 Pos \u7248\u672c\u3002\uff08\u53d6\u4f4d\u7f6e\u3002\u3002\u3002 \uff08\u503c\u5f97\u6ce8\u610f\u7684\u662f\u5de6\u8fb9\u7684 \u201c\u7ebf\u6bb5\u6811\u201d \u5efa\u7acb\u8d77\u6765\u7684\u65b9\u5f0f\uff0c\u5b9e\u9645\u4e0a\u662f\u53cd\u5411\uff0c\u4ece\u53f6\u5b50\u7ed3\u70b9\u5f00\u59cb\u505a\u5f52\u5e76\u6811\u3002\u3002\u3002 http:\/\/poj.org\/problem?id=2104<\/a> Brief description: \u7ed9\u5b9a\u4e00\u7ec4\u533a\u95f4\uff0c\u6bcf\u6b21\u8be2\u95ee [a, b] \u533a\u95f4\u5185\u7b2c k \u5c0f\u7684\u6570\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":[19],"tags":[],"class_list":["post-308","post","type-post","status-publish","format-standard","hentry","category-poj"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-4Y","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/308","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=308"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/308\/revisions"}],"predecessor-version":[{"id":309,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/308\/revisions\/309"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=308"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=308"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=308"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\n\u4e3b\u5e2d\u6811<\/a>
\n\u5212\u5206\u6811<\/a><\/p>\n
\n\u9996\u5148\uff0c\u574a\u95f4\u6d41\u4f20\u6bd4\u8f83\u591a\u7684\u505a\u6cd5\u662f\u5f52\u5e76\u6811\u548c\u5212\u5206\u6811\u3002<\/p>\n\r\n[1 2 3 4 5 6 7 8] [1 7 2 5 8 3 4 6] root\r\n[1 2 5 7][3 4 7 8] [1 2 3 4][7 5 8 6]\r\n[1 7][2 5][3 8][4 6] [1 2][3 4][5 6][7 8]\r\n[1][7][2][5][8][3][4][6] [1][2][3][4][5][6][7][8] leaf\r\n\t\u5f52\u5e76\u6811\t\t\t \u5212\u5206\u6811\r\n<\/pre>\n
\n\u7684\u4e2d\u95f4\u8fc7\u7a0b\u8bb0\u5f55\u4e0b\u6765\u7684\u8bdd\uff0c\u5c31\u5f97\u5230\u4e86\u5f52\u5e76\u6811\u3002\u3002\uff08\u5bf9\u5e94\u7684\u3001\u5c06\u5feb\u901f\u6392\u5e8f (Quick Sort<\/a>) \u7684\u4e2d\u95f4\u8fc7\u7a0b\u8bb0\u5f55\u4e0b\u6765\uff0c\u5c31\u5f97\u5230\u4e86\u5212\u5206\u6811\u3002\u3002<\/p>\n
\n\u5bf9\u4e8e\u8be2\u95ee ([a, b], k)\uff0c\u5177\u4f53\u505a\u6cd5\u662f\u73b0\u5728\u6811\u4e0a\u627e\u5230\u6240\u6709\u7ec4\u6210 [a, b] \u7684\u533a\u95f4\uff0c\u4e4b\u540e\u5f97\u5230 x \u5728\u6240\u6709\u8fd9\u4e9b\u533a\u95f4\u4e2d\u7684\u6392\u540d\u5e76\u548c k \u8fdb\u884c\u6bd4\u8f83\u3002
\n\u603b\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u662f O(nlog^3n)\u3002\u3002\u3002<\/p>\n
\nT[lv][i] \u8bb0\u5f55\u4ece\u533a\u95f4\u5f00\u59cb\u5230\u7b2c i \u4e2a\u4f4d\u7f6e\u7ed3\u675f\u65f6\uff0c\u6709\u591a\u5c11\u6570\u88ab\u5212\u5206\u5230\u4e86\u5de6\u8fb9\u3002\u3002<\/p>\n
\n\u540c\u65f6\u6839\u636e Auxiliary Tree \u4e2d\u5b58\u50a8\u7684\u4fe1\u606f\uff0c\u8fdb\u4e00\u6b65\u7f29\u5c0f\u533a\u95f4 [a, b]\u3002
\n\u65f6\u95f4\u590d\u6742\u5ea6\u53ea\u6709 O(nlogn)\u3002\u3002\u3002<\/p>\n\r\n\/\/}\/* .................................................................................................................................. *\/\r\n\r\nconst int N = int(1e5)+9, M = 18;\r\nint A[N], T[M][N];\r\nint n, m;\r\n\r\n#define rt 0,0,n-1\r\n#define lvv (lv+1)\r\n#define ml (l+r>>1)\r\n#define mr (ml+1)\r\n#define lc lvv,l,ml\r\n#define rc lvv,mr,r\r\n#define t T[lv][i]\r\n\r\nvoid Build(int lv, int l, int r){\r\n if (l == r) return;\r\n int ll = l, rr = mr; FOR_1(i, l, r){\r\n if (t <= A[ml]) T[lvv][ll++] = t; else T[lvv][rr++] = t;\r\n t = ll-l;\r\n }\r\n Build(lc), Build(rc);\r\n}\r\n\r\n\/*\r\nint Query(int lv, int l, int r, int a, int b, int k){\r\n if (l == r) return A[a];\r\n int ll = a == l ? 0 : T[lv][a-1], rr = T[lv][b];\r\n return rr - ll >= k ? Query(lc,l+ll,l+rr-1,k) : Query(rc,mr+a-l-ll,mr+b-l-rr,k+ll-rr);\r\n}*\/\r\n\r\ninline int Query(int lv, int l, int r, int a, int b, int k){\r\n while (l < r){\r\n int ll = a == l ? 0 : T[lv][a-1], rr = T[lv][b];\r\n if (rr - ll >= k) a=l+ll,b=l+rr-1,r=ml;\r\n else a=mr+a-l-ll,b=mr+b-l-rr,k-=rr-ll,l = mr;\r\n ++lv;\r\n }\r\n return A[a];\r\n}\r\n\r\nint main(){\r\n\r\n#ifndef ONLINE_JUDGE\r\n freopen("in.txt", "r", stdin);\r\n \/\/freopen("out.txt", "w", stdout);\r\n#endif\r\n\r\n RD(n, m); REP(i, n) T[0][i] = RDD(A[i]); sort(A,A+n);\r\n Build(rt);int a,b,k;DO(m){\r\n RD(a,b,k);--a,--b;\r\n OT(Query(rt,a,b,k));\r\n }\r\n}\r\n<\/pre>\n\r\n[1 7 2 5 8 3 4 6] [1 1 2 2 2 3 4 4] root\r\n[1 2 3 4][7 5 8 6] [1 2 2 2][0 1 1 2]\r\n[1 2][3 4][5 6][7 8] [1 1][1 1][1 1][1 1]\r\n[1][2][3][4][5][6][7][8] \u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014 leaf\r\n\t\u5212\u5206\u6811\t\t\t \u5bf9\u5e94\u8f85\u52a9\u6811\r\n<\/pre>\n
\n\u53e6\u5916\u6ce8\u610f\u5230\u5bf9\u4e8e\u53f6\u5b50\u8282\u70b9\uff0c\u8f85\u52a9\u6811\u662f\u6ca1\u6709\u5b9a\u4e49\u7684\uff0c\u4e0a\u9762\u7684\u7a0b\u5e8f\u4e2d\u5728\u5212\u5206\u6811\u7684\u6bcf\u4e2a\u975e\u53f6\u5b50\u7ed3\u70b9\uff0c
\n\u5728\u5b8c\u6210\u4e86\u5bf9\u5e94\u7684\u5efa\u6811\u65f6\u523b\u7684\u529f\u80fd\u540e\uff0c\u90fd\u88ab\u5bf9\u5e94\u7684 Auxiliary Tree \u7684\u7ed3\u70b9\u8986\u76d6\u4e86\u3002
\n\uff08\u6ce8\u610f\u6240\u6709\u53f6\u5b50\u7ed3\u70b9\u662f\u6ca1\u6709\u88ab\u8986\u76d6\u7684\u3002\u3002\u3002\u5728\u8be2\u95ee\u7684\u5230\u53f6\u5b50\u7ed3\u70b9\u7684\u65f6\u5019\uff0c\u4e5f\u53ef\u4ee5\u8fd4\u56de T[lv][l] \u3002\u3002 \uff09<\/p>\n
\n\uff08\u5f52\u5e76\u6811\u601d\u7ef4\u590d\u6742\u5ea6\u867d\u7136\u8981\u4f4e\u4e8e\u5212\u5206\u6811\u3002\u3002\u4f46\u662f\u7a0b\u5e8f\u8981\u96be\u5199\u591a\u4e86\u3002\u3002\uff09<\/p>\n
\n\u4e0b\u9762\u4ecb\u7ecd xiaodai \u5b66\u957f\u6559\u6211\u7684 O(nlog^2n) \u7b97\u6cd5\u3002\u3002\u3002\u5bf9 A \u6570\u7ec4\u7684\u503c\u57df\uff0c\u5efa\u7acb\u7ebf\u6bb5\u6811\u3002\u3002\uff08\u6240\u4ee5\u5148\u8981\u6392\u5e8f\u79bb\u6563\u5316\u3002\u3002\u3002
\n\u7ebf\u6bb5\u6811\u7684\u6bcf\u4e2a\u7ed3\u70b9\uff0c\u4fdd\u5b58\u4e00\u4e2a\u6709\u5e8f\u6570\u7ec4\uff0c\u5b58\u50a8 A \u6570\u7ec4\u4e2d\uff0c\u6240\u6709\u5728\u8fd9\u4e2a\u503c\u57df\u7684\u6570\u7684\u4e0b\u6807\u3002\u3002<\/p>\n
\n\u51b3\u5b9a\u5411\u5de6\u5b50\u6811\u9012\u5f52\u8fd8\u662f\u5411\u53f3\u5b50\u6811\u9012\u5f52\u3002\u3002\u3002\u3002
\n\uff08\u8fd9\u4e00\u6b65\u8981\u4e8c\u5206\u67e5\u627e\uff0c\u5212\u5206\u6811\u91cc\u8fd9\u4e00\u6b65\u662f\u901a\u8fc7\u5728\u8f85\u52a9\u6570\u7ec4\u4e0a\u76f4\u63a5\u505a\u5dee\u5f97\u5230\u7684\u3002\u3002<\/p>\n\r\n[1 2 3 4 5 6 7 8] [1 7 2 5 8 3 4 6] root\r\n[1 3 6 7][2 4 5 8] [1 2 3 4][7 5 8 6]\r\n[1 3][6 7][4 8][2 5] [1 2][3 4][5 6][7 8]\r\n[1][3][6][7][4][8][2][5] [1][2][3][4][5][6][7][8] leaf\r\n \u503c\u57df\u7ebf\u6bb5\u6811\t \u5212\u5206\u6811\t\r\n<\/pre>\n
\n\u56e0\u800c\u4e5f\u53ef\u4ee5\u5411\u5212\u5206\u6811\u4e2d\u90a3\u6837\uff0c\u5efa\u7acb Auxiliary Tree\uff0c\u5f97\u5230 O(logn) \u56de\u7b54\u8be2\u95ee\u7684\u65b9\u6cd5\uff0c\u5176\u5b9e\u5b8c\u5168\u662f\u4e00\u4e2a\u4e1c\u897f\u3002<\/p>\n
\n\uff08\u53ef\u89c1\u5f52\u5e76\u6811\u4e0e\u5212\u5206\u6811\u4e4b\u95f4\u7684\u79cd\u79cd\u8054\u7cfb\u3002\u3002\u540c\u65f6\u4e5f\u518d\u6b21\u8ba9\u6211\u4eec\u770b\u5230\u4e86\u5212\u5206\u6811\u4e2d\uff0c\u7528\u8f85\u52a9\u6570\u7ec4\u51b3\u5b9a\u9012\u5f52\u65b9\u5411\u7684\u540c\u65f6\u7f29\u5c0f\u8be2\u95ee\u533a\u95f4\u7684\u601d\u60f3\u662f\u591a\u4e48\u7cbe\u9ad3\u554a\uff01\u3002\u3002\u3002<\/p>\nExternal link: <\/h3>\n
\nhttp:\/\/www.notonlysuccess.com\/index.php\/divide-tree\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"