第k元素log(n)算法–划分树
2010-11-02 08:53:29 来源：WEB开发网 闂傚倸鍊搁崐鎼佸磹閹间礁纾归柟闂寸绾惧綊鏌熼梻瀵割槮缁炬儳缍婇弻鐔兼⒒鐎靛壊妲紒鐐劤缂嶅﹪寮婚悢鍏尖拻閻庨潧澹婂Σ顔剧磼閹冣挃闁硅櫕鎹囬垾鏃堝礃椤忎礁浜鹃柨婵嗙凹缁ㄧ粯銇勯幒瀣仾闁靛洤瀚伴獮鍥敍濮ｆ寧鎹囬弻鐔哥瑹閸喖顬堝銈庡亝缁挸鐣烽崡鐐嶆棃鍩€椤掑嫮宓佸┑鐘插绾句粙鏌涚仦鎹愬闁逞屽墰閹虫捇锝炲┑瀣╅柍杞拌兌閻ゅ懐绱撴担鍓插剱妞ゆ垶鐟╁畷銉р偓锝庡枟閻撴洘銇勯幇闈涗簼缂佽埖姘ㄧ槐鎾诲礃閳哄倻顦板┑顔硷工椤嘲鐣烽幒鎴旀瀻闁规惌鍘借ⅵ濠电姷鏁告慨顓㈠磻閹剧粯鈷戞い鎺嗗亾缂佸鏁婚獮鍡涙倷閸濆嫮顔愬┑鐑囩秵閸撴瑦淇婇懖鈺冪＜闁归偊鍙庡▓婊堟煛鐏炵硶鍋撻幇浣告倯闁硅偐琛ラ埀顒冨皺閺佹牕鈹戦悙鏉戠仸闁圭ǹ鎽滅划鏃堟偨缁嬭锕傛煕閺囥劌鐏犻柛鎰ㄥ亾婵＄偑鍊栭崝锕€顭块埀顒佺箾瀹€濠侀偗婵﹨娅ｇ槐鎺懳熺拠鑼舵暱闂備胶枪濞寸兘寮拠宸殨濠电姵纰嶉弲鎻掝熆鐠虹尨宸ョ€规挸妫濆铏圭磼濡搫顫嶇紓浣风劍閹稿啿鐣烽幋锕€绠婚悹鍥у级瀹撳秴顪冮妶鍡樺鞍缂佸鍨剁粋宥夋倷椤掍礁寮垮┑鈽嗗灣閸樠勭妤ｅ啯鍊垫慨妯煎亾鐎氾拷
闂傚倸鍊搁崐鎼佸磹閹间礁纾归柟闂寸绾惧綊鏌熼梻瀵割槮缁炬儳缍婇弻鐔兼⒒鐎靛壊妲紒鐐劤缂嶅﹪寮婚悢鍏尖拻閻庨潧澹婂Σ顔剧磼閹冣挃闁硅櫕鎹囬垾鏃堝礃椤忎礁浜鹃柨婵嗙凹缁ㄥジ鏌熼惂鍝ョМ闁哄矉缍侀、姗€鎮欓幖顓燁棧闂備線娼уΛ娆戞暜閹烘缍栨繝闈涱儐閺呮煡鏌涘☉鍗炲妞ゃ儲鑹鹃埞鎴炲箠闁稿﹥顨嗛幈銊╂倻閽樺锛涘┑鐐村灍閹崇偤宕堕浣镐缓缂備礁顑嗙€笛囨倵椤掑嫭鈷戦柣鐔告緲閳锋梻绱掗鍛仸鐎规洘鍨块獮鍥偋閸垹骞嶇紓鍌氬€烽悞锕傛晪缂備焦銇嗛崶銊у帗閻熸粍绮撳畷婊堟晝閸屾氨鐓戦梺鍛婂姦閻撳牆岣块弽顓熺厱婵犻潧妫楅悵鏃傛喐閺傝法鏆﹂柟顖炲亰濡茬偓绻涚€电ǹ孝闁靛牏枪椤繘鎼圭憴鍕彴闂佽偐鈷堥崜娑㈩敊婢舵劖鈷戦柣鎾虫捣缁夎櫣绱掗悩宕囧⒌妤犵偛鍟妶锝夊礃閳轰讲鍋撴繝姘參婵☆垯璀﹀Σ濂告煙閼恒儲绀嬫慨濠冩そ濡啫鈽夋潏顭戔偓鍡樼節绾版ǚ鍋撻搹顐㈡灎閻庤娲忛崹浠嬪箖娴犲宸濆┑鐐靛亾鐎氬ジ姊洪懡銈呮瀾闁荤喆鍎抽埀顒佹皑閸忔ê鐣烽婵堢杸婵炴垶鐟ч崢閬嶆⒑缂佹◤顏嗗椤撶喐娅犻柣銏犳啞閻撳繘鏌涢埄鍐炬當闁逞屽墮濠€杈╃磽閹惧顩烽悗锝庝簻缁愭稒绻濋悽闈浶㈤悗姘煎墴閻涱噣宕奸妷锔规嫼缂佺虎鍘奸幊搴ㄋ夊澶嬬厵婵炶尪顔婄花鑺ヤ繆閸欏濮嶇€殿喗鎸抽幃銏ゅ传閸曘劌褰忛梻鍌氬€搁崐鎼佸磹妞嬪孩顐芥慨姗嗗厳缂傛氨鎲稿鍥у疾闂備線娼ч悧鍡椕洪悩璇茬；闁圭偓鍓氬ḿ鈺傘亜閹扳晛鐏╃紒渚囧櫍濮婅櫣绱掑Ο鍦箒闂侀潻缍囩紞渚€鎮伴鈧獮鎺楀箠閾忣偅顥堥柛鈹惧亾濡炪倖甯掗崐缁樼▔瀹ュ鐓ユ繝闈涙椤ョ姷绱掗埦鈧崑鎾绘⒒閸屾艾鈧悂鎮ф繝鍕煓闁硅揪绠戝Ч鍙夌箾閸℃璐╅柣鐔稿閸亪鏌涢鐘茬伄闁哄棭鍋婂娲传閸曨厾鍔圭紓鍌氱С閻掞箓骞堥妸鈺佺劦妞ゆ帒瀚悡鍐煙椤栨粌顣肩痪顓犲亾缁绘繈鍩€椤掍焦缍囬柕濞у懎楠勯梻浣告惈濞层劑宕伴幘璺哄К闁逞屽墮閳规垿顢欓弬銈勭返闂佸憡锕㈢粻鏍х暦閵忋倖鍋ㄩ柛娑樑堥幏铏圭磽閸屾瑧鍔嶉柨姘攽椤曞棛鐣甸柡灞剧洴楠炴﹢寮堕幋婵囨嚈闂備浇顕栭崰妤勬懌濠电偟鍘х换妯讳繆閹间礁围闁搞儮鏅濋弳浼存⒒閸屾瑧顦︽繝鈧潏鈺佸灊妞ゆ牗绮嶉弳婊堟煟閹邦剛鎽犳繛鍛У缁绘盯骞嬮悙瀵告缂佺偓宕橀崑鎰閹惧瓨濯撮悹鎰靛灣缁辨澘鈹戦悙鏉戠祷妞ゆ洦鍙冮崺鈧い鎺戝枤濞兼劖绻涢崣澶屽ⅹ闁伙絿鍏橀、妤呭礃椤忓啰鑳洪梻鍌氬€风粈渚€骞夐敓鐘茬闁哄洢鍨归悿顕€鏌ｅΟ娆惧殭缂佲偓閸喓绡€闂傚牊绋撴晶娑氣偓瑙勬礀瀵墎鎹㈠☉銏犵闁绘劑鍔庣槐浼存⒑閸濆嫭顥滄俊顐ｎ殜閸╃偤骞嬮敂钘変汗闁哄鐗滈崑鍕储閿熺姵鈷戦弶鐐村閸斿秹鏌ｅΔ浣虹煂婵″弶鍔欓獮妯尖偓娑櫭鎾寸箾鐎电ǹ孝妞ゆ垵鎳橀獮妤呮偨閸涘ň鎷洪梺闈╁瘜閸樹粙宕甸埀顒€鈹戦悙鑼勾闁稿﹥绻堥獮鍐┿偅閸愨晛鈧鏌﹀Ο渚Ш妞ゆ柨锕铏规喆閸曨剙鍓归梺鍛娒肩划娆忕暦閹剧粯鍋ㄩ柛娑樑堥幏娲⒑閼姐倕鏋戞繝銏★耿楠炲啯绗熼埀顒勫蓟閿濆绠抽柣鎰暩閺嗐倝姊虹拠鈥虫灍妞ゃ劌锕悰顕€寮介妸锕€顎撻梺绋跨箰椤︽壆鈧俺妫勯埞鎴︽倷閼搁潧娑х紓浣瑰絻濞尖€崇暦閺囥垹围濠㈣泛锕ら幆鐐烘⒑闁偛鑻晶瀛樻叏婵犲啯銇濇鐐寸墵閹瑥霉鐎ｎ亙澹曢梺鍝勭▉閸樹粙宕戠€ｎ喗鐓熸俊顖氱仢閸氬湱鈧鎸风欢姘舵偂椤愶箑鐐婇柕濞р偓婵洭姊洪崫鍕櫤闁诡喖鍊垮濠氬Ω閳哄倸浜為梺绋挎湰缁嬫垿顢旈敓锟�
婵犵數濮烽弫鍛婃叏閻戣棄鏋侀柛娑橈攻閸欏繘鏌ｉ幋锝嗩棄闁哄绶氶弻娑樷槈濮楀牊鏁鹃梺鍛婄懃缁绘﹢寮婚敐澶婄闁挎繂妫Λ鍕⒑閸濆嫷鍎庣紒鑸靛哺瀵鈽夊Ο閿嬵潔濠殿喗顨呴悧濠囧极妤ｅ啯鈷戦柛娑橈功閹冲啰绱掔紒妯虹伌濠碉紕鏁诲畷鐔碱敍濮橀硸鍟嬮梻浣告啞椤ㄥ牓宕戦悢鍝ヮ浄闁兼祴鏅濈壕钘壝归敐鍛儓妞ゅ骸鐭傞弻娑㈠Ω閵壯冪厽閻庢鍠涢褔鍩ユ径鎰潊闁绘ḿ鏁搁弶鎼佹⒒閸屾艾鈧悂鎮ф繝鍕煓闁圭儤顨嗛崐鍫曟煕椤愮姴鍔滈柛濠勬暬閺岋綁鎮㈤崫鍕垫毉闂佸摜鍠撻崑鐔烘閹烘梹瀚氶柟缁樺笚濞堢粯绻濈喊澶岀？闁轰浇顕ч悾鐑芥偄绾拌鲸鏅┑顔斤耿绾悂宕€ｎ喗鈷戦悹鍥ㄧ叀閸欏嫭绻涙担鍐叉搐缁犵儤绻濇繝鍌滃闁稿鏅涢埞鎴﹀磼濮橆厼鏆堥梺鎶芥敱閸ㄥ綊鎯€椤忓牜鏁囬柣鎰綑椤庢稑鈹戦悙鎻掓倯闁告梹鐗滈幑銏犫槈閵忊€虫濡炪倖宸婚崑鎾绘煛鐎ｎ亜顒㈤柕鍥у椤㈡洟濮€閵忋埄鍞虹紓鍌欐祰妞村摜鏁幒鏇犱航闂備礁鍚嬬粊鎾疾濠婂牆鍚圭€光偓閸曨兘鎷绘繛鎾村焹閸嬫捇鏌嶈閸撴盯宕戝☉銏″殣妞ゆ牗绋掑▍鐘炽亜閺冨洤浜归柡鍡楁閺屻劌鈹戦崱娆忣暫闂佸憡鏌ㄩ悘姘跺Φ閸曨垱鏅滈柣锝呰嫰瀵劑姊虹拠鈥虫珯缂佺粯绻冩穱濠囨嚋闂堟稓绐為柣搴秵閸撴瑧鏁ィ鍐┾拻濞达絿枪椤ュ繘鏌涚€ｎ亝鍣介柟骞垮灲瀹曟﹢顢欓懖鈺嬬幢婵＄偑鍊曠换鎰板箠閹邦喚涓嶉柛鎾椻偓閸嬫捇鎮烽弶娆炬闂佸摜濮靛ú婊堟嚍鏉堛劎绡€婵﹩鍓涢悾楣冩⒑缂佹ɑ鐓ラ柛姘儔閸╂盯骞嬮敂钘夆偓鐢告煕閿旇骞栭弽锟犳⒑闂堟稒顥滈柛鐔告尦瀵濡舵径濠勵槰闂佽偐鈷堥崜娆撴偂閻斿吋鍊甸悷娆忓缁€鍐磼鐠囪尙澧︾€殿噮鍋婂畷姗€顢欓懖鈺佸Е婵＄偑鍊栫敮鎺斺偓姘€鍥х劦妞ゆ帊鐒﹂ˉ鍫⑩偓瑙勬礃閿曘垽銆佸▎鎾冲簥濠㈣鍨板ú锕傛偂閺囥垺鐓冮柍杞扮閺嬨倖绻涢崼鐕傝€块柡宀嬬秮閹垻绮欓崹顕呮綒婵犳鍠栭敃銉ヮ渻娴犲绠栭柍鈺佸暞閸庣喖鏌嶉埡浣告殲闁伙讣缍佸缁樻媴閾忕懓绗￠梺缁橆殕濞茬喐淇婇崜浣虹煓閻犳亽鍔嶅▓楣冩⒑缂佹ê鐏﹀畝锝堟硶瀵囧焵椤掑嫭鈷戦柟鑲╁仜閸斺偓闂佸憡鍔戦崝搴ㄥΧ椤曗偓濮婂宕掑▎鎴犵崲濠电偘鍖犻崟鍨啍闂婎偄娲﹀ú姗€锝為弴銏＄厸闁搞儯鍎遍悘鈺呮煕鐏炶濡介柕鍥у缁犳盯骞樼捄渚澑闂備焦濞婇弨閬嶅垂閸ф钃熼柣鏂垮悑閸ゅ啴鏌嶆潪鐗堫樂缂侇喖鐖煎娲川婵犲啠鎷瑰銈冨妼閿曨亜顕ｆ繝姘櫢闁绘ɑ褰冪粣娑橆渻閵堝棙顥堥柡渚囧枟閹便劑宕堕埡鍐紳婵炶揪绲挎灙闁逞屽墮濠€閬嶅极椤曗偓閹垺淇婇幘铏窛闁逞屽墴濞佳囧箺濠婂懎顥氬┑鍌溓圭痪褔鏌涢锝団槈濠德ゅ亹缁辨帒螖娴ｄ警鏆＄紓浣虹帛閻╊垶骞冮埄鍐╁劅闁挎繂娴傞崯瀣⒒娴ｈ櫣銆婇柡鍌欑窔瀹曟粌鈹戠€ｎ亞顔嗛梺鍛婄☉閻°劑鎮￠妷鈺傚€甸柨婵嗘噽娴犳稓绱撳鍡╂疁婵﹤顭峰畷鎺戭潩椤戣棄浜剧€瑰嫭鍣磋ぐ鎺戠倞鐟滄粌霉閺嶎厽鐓忓┑鐐靛亾濞呭棝鏌涙繝鍌涘仴闁哄被鍔戝鎾倷濞村浜鹃柛婵勫劤娑撳秹鏌＄仦璇插姕闁绘挻娲熼弻鏇熷緞濡儤鐏堟繝鈷€灞芥珝闁哄矉绱曢埀顒婄岛閺呮繄绮ｉ弮鍫熺厸鐎光偓閳ь剟宕伴弽褏鏆︽繝濠傛－濡查箖鏌ｉ姀鈺佺仭闁烩晩鍨跺濠氭晸閻樻彃绐涘銈嗘濡嫰鍩€椤掍礁濮嶉柡宀嬬磿娴狅妇鎷犻幓鎺濇綆闂備浇顕栭崰鎾诲磹濠靛棛鏆﹂柟鐑樺灍濡插牊鎱ㄥΔ鈧Λ鏃傛閿燂拷闂傚倸鍊搁崐鎼佸磹閹间礁纾归柟闂寸绾惧綊鏌熼梻瀵割槮缁炬儳缍婇弻鐔兼⒒鐎靛壊妲紒鐐劤缂嶅﹪寮婚悢鍏尖拻閻庨潧澹婂Σ顔剧磼閹冣挃闁硅櫕鎹囬垾鏃堝礃椤忎礁浜鹃柨婵嗙凹缁ㄧ粯銇勯幒瀣仾闁靛洤瀚伴獮鍥敍濮ｆ寧鎹囬弻鐔哥瑹閸喖顬堝銈庡亝缁挸鐣烽崡鐐嶆棃鍩€椤掑嫮宓佸┑鐘插绾句粙鏌涚仦鎹愬闁逞屽墰閹虫捇锝炲┑瀣╅柍杞拌兌閻ゅ懐绱撴担鍓插剱妞ゆ垶鐟╁畷銉р偓锝庡枟閻撴洘銇勯幇闈涗簼缂佽埖姘ㄧ槐鎾诲礃閳哄倻顦板┑顔硷工椤嘲鐣烽幒鎴旀瀻闁规惌鍘借ⅵ濠电姷鏁告慨顓㈠磻閹剧粯鈷戞い鎺嗗亾缂佸鏁婚獮鍡涙倷閸濆嫮顔愬┑鐑囩秵閸撴瑦淇婇懖鈺冪＜闁归偊鍙庡▓婊堟煛鐏炵硶鍋撻幇浣告倯闁硅偐琛ラ埀顒冨皺閺佹牕鈹戦悙鏉戠仸闁圭ǹ鎽滅划鏃堟偨缁嬭锕傛煕閺囥劌鐏犻柛鎰ㄥ亾婵＄偑鍊栭崝锕€顭块埀顒佺箾瀹€濠侀偗婵﹨娅ｇ槐鎺懳熺拠鑼舵暱闂備胶枪濞寸兘寮拠宸殨濠电姵纰嶉弲鎻掝熆鐠虹尨宸ョ€规挸妫濆铏圭磼濡搫顫嶇紓浣风劍閹稿啿鐣烽幋锕€绠婚悹鍥у级瀹撳秴顪冮妶鍡樺鞍缂佸鍨剁粋宥夋倷椤掍礁寮垮┑鈽嗗灣閸樠勭妤ｅ啯鍊垫慨妯煎亾鐎氾拷 闂傚倸鍊搁崐鎼佸磹閹间礁纾归柟闂寸绾惧綊鏌熼梻瀵割槮缁炬儳缍婇弻鐔兼⒒鐎靛壊妲紒鐐劤缂嶅﹪寮婚悢鍏尖拻閻庨潧澹婂Σ顔剧磼閻愵剙鍔ょ紓宥咃躬瀵鏁愭径濠勵吅闂佹寧绻傞幉娑㈠箻缂佹ḿ鍘遍梺闈涚墕閹冲酣顢旈銏＄厸閻忕偠顕ч埀顒佺箓閻ｇ兘顢曢敃鈧敮闂佹寧妫佹慨銈夋儊鎼粹檧鏀介柣鎰▕閸ょ喎鈹戦鈧ḿ褔锝炲┑瀣╃憸搴綖閺囥垺鐓欓柟瑙勫姦閸ゆ瑧鐥幆褍鎮戠紒缁樼洴瀹曞崬螣閾忓湱鎳嗛梻浣告啞閿曨偆妲愰弴鐘愁潟闁规儳顕悷褰掓煕閵夋垵瀚ぐ顖炴⒒娴ｈ鍋犻柛鏂跨焸閹儵宕楅梻瀵哥畾闂佸湱铏庨崰鏍矆閸愨斂浜滈柡鍐ㄥ€哥敮鍓佺磼閹邦厾娲存慨濠冩そ瀹曨偊宕熼崹顐嵮囨⒑閹肩偛濡肩紓宥咃工閻ｇ兘濮€閻樺棙妞介、鏃堝川椤撴稑浜鹃柛顭戝亽濞堜粙鏌ｉ幇顖氱毢濞寸姰鍨介弻娑㈠籍閳ь剛鍠婂澶娢﹂柛鏇ㄥ灡閺呮粓鎮归崶顏勭毢濞寸姵鎮傞幃妤冩喆閸曨剛鈹涚紓浣虹帛缁诲牓鎮伴鑺ュ劅闁靛⿵绠戝▓鐔兼⒑闂堟冻绱￠柛鎰╁妼椤╊剟姊婚崒姘偓鎼併偑閹绢喖纾婚柛鏇ㄥ€嬪ú顏呮櫇闁逞屽墰閸欏懘姊洪崫鍕犻柛鏂垮閺呭爼鏁撻悩鏂ユ嫽闂佺ǹ鏈悷锔剧矈閻楀牄浜滈柡鍥ф閹冲宕戦幘璇插瀭妞ゆ劑鍨虹拠鐐烘倵鐟欏嫭绀冪紒顔芥崌楠炲啴濮€閿涘嫰妾繝銏ｆ硾椤戝洨绮欐笟鈧缁樻媴閻熸澘濮㈢紓浣虹帛閸旀洟鏁冮姀鈩冪秶闁宠桨绶″Λ婊堟⒑缁嬭法绠绘俊顐ユ硶閹广垽宕卞Ο闀愮盎闂佸搫绉查崝搴ㄣ€傞弻銉︾厵妞ゆ牗姘ㄦ晶娑㈡煏閸パ冾伃妞ゃ垺娲熸慨鈧柍鎯帮骏閸ㄦ椽濡甸崟顖ｆ晜闁告洦鍋呭▓缁樼節绾版ǚ鍋撳畷鍥х厽閻庤娲栧畷顒冪亙闂侀€炲苯澧撮柨婵堝仦閹棃濡搁敂瑙勫闂備礁鎲＄粙鎴︺偑閹绢喗鍊垮┑鍌氭啞閻撴洟鏌曟径瀣仴闁瑰啿楠搁锝夊Ω閵夈垺鏂€闂佺粯锕╅崰鏍倶鏉堛劎绠惧璺侯儑椤ジ鏌ｈ閻倸顫忛搹鍦＜婵☆垵宕甸崣鍡涙⒑閸涘﹨澹樻い鎴濐樀楠炲啴鏁撻悩鍙傘劑鏌嶉崫鍕偓鎼佸焵椤掑倹鏆柡灞诲妼閳规垿宕卞☉鎵佸亾濡ゅ懏鐓曟俊顖滅帛鐏忥箓鏌＄仦鍓с€掗柍褜鍓ㄧ紞鍡涘磻閸涱垯鐒婇柟娈垮枤绾捐偐绱撴担璐細缂佺姵鎸婚妵鍕敃閿濆洨鐤勫銈冨灪閿氶柍钘夘槸閳诲氦绠涢敐鍕そ闂傚倸鍊峰ù鍥х暦閻㈢ǹ绐楅柟閭﹀枛閸ㄦ繈骞栧ǎ顒€鐏繛鍛У娣囧﹪濡堕崨顓熸闂佸搫妫欑划鎾诲蓟閻斿吋鍊绘俊顖濐嚙閺嗘顪冮妶鍌涙珕鐟滄澘鍟村﹢渚€姊虹紒妯诲碍婵炲鍏橀獮妤呮偐缂佹ḿ鍘介梺瑙勫劤閻°劎绮堢€ｎ喗鐓涚€光偓閳ь剟宕伴弽顓犲祦闁糕剝鍑瑰銊╂⒑閹肩偛鈧宕伴弽顓炶摕鐎广儱顦扮€电姴顭块懜鐬垿鍩㈤崼銉︹拺闁告繂瀚€氭壆绱掓径濠傤暢婵″弶鍔欓獮鎺楀箠瀹曞洤鏋涢柟绛圭節婵″爼宕ㄩ鐔荤发濠电姷顣槐鏇㈠磻閹达箑纾归柕鍫濐槸绾惧鏌涘☉鍗炵仭鐎规洘鐓￠弻娑㈩敃閻樻彃濮庣紓浣哄Х婵數鎹㈠┑鍥╃瘈闁稿本绋戝▍锝夋⒑閸濆嫷鍎忛柣妤€锕ョ粚杈ㄧ節閸ヨ埖鏅┑鐘茬仛閸旀洖鈻撻鐑嗘富闁靛牆鎳愮粻鎵磽瀹ュ拑宸ユい顐㈢箲缁绘繂顫濋鍌︾床婵犵數鍋涘Λ娆撳春閸惊锝夘敋閳ь剙顫忛搹瑙勫厹闁告粈绀佸▓婵堢磽娴ｄ粙鍝烘繛鍙夌矒瀹曟岸骞掗幋鏃€鐎婚梺瑙勫劤绾绢參顢樺ú顏呪拺闁圭ǹ瀛╅悡銉╂煙绾板崬浜濈紒鍌氱У缁轰粙宕ㄦ繛鐐闂備礁鎲＄换鍌溾偓姘槻鍗辩憸鐗堝笚閻撴洟鏌曟繛褍鍟悘鍫ユ倵濞堝灝鏋熼柟顔煎€搁锝夘敋閳ь剙鐣锋總鍛婂亜闁告繂瀚粻浼存⒒閸屾瑧顦﹂柟璇х節瀹曟繆顦寸€垫澘锕幊鐐哄Ψ瑜滃ú鎼佹⒑閸涘﹥瀵欓柛娑卞灲缁卞啿鈹戦悙鑸靛涧缂傚秮鍋撳┑鐐叉嫅缁插潡寮灏栨婵ǹ浜敍婊堟煟鎼搭垳绉甸柛瀣噽娴滄悂骞嶉鍓э紲闂佺ǹ鏈粙鎴澝归鈧弻鈩冩媴缁嬫寧娈婚悗瑙勬礃鐢帡锝炲┑瀣疅閻庯綆鍓欑花銉︾節閻㈤潧校妞ゆ梹鐗犲畷鏉课旈崨顔芥珖闂佸啿鎼幊搴ｇ矆閸儲鐓ラ柡鍥╁仜閳ь剙缍婂畷鎰版偨閸涘﹦鍘甸梺璇″灡濠㈡ǹ顣块梻浣瑰▕閺€杈╂暜閹烘绠掗梻浣瑰缁诲倿骞婅箛娑樼疅闁归棿鐒﹂悡銉︾箾閹寸偍缂氶懖鏍磽娴ｄ粙鍝洪悽顖ょ節閵嗕礁顫濈捄鍝勭獩濡炪倖鎸炬慨鍐差浖閹剧繝绻嗛柕鍫濇搐鍟搁梺绋款儑閸嬨倕鐣疯ぐ鎺戝瀭妞ゆ梻鍋撳▓楣冩⒑閸撴彃浜濇繛璇х畵瀵偊宕卞☉娆戝幈闁诲繒鍋熼崑鎾绘儍閹达附鐓忛柛顐墰閻ｅ灚鎱ㄦ繝鍛仩闁归濞€楠炴捇骞掗幋鐐垫И缂傚倸鍊搁崐鍝ョ矓閺夋嚦娑樷枎閹寸姷鐒块悗骞垮劚椤︻垶宕橀埀顒€顪冮妶鍡樺暗闁稿鍠栧畷顐⑽旀担铏诡啎闁诲海鏁告灙鐎涙繂顪冮妶鍡楃仴婵☆偅绻堥獮鍐灳閺傘儲鐎婚梺鐟板⒔鐞涖儵骞忛崫鍕垫富闁靛牆妫欑亸顏堟煕閺傚潡鍙勯柟顕€绠栧畷锟犳倻閸℃瑥鏁搁柣鐔哥矋缁挸鐣疯ぐ鎺撶劶鐎广儱鎲橀敃鍌涚厱闁哄洢鍔岄悘鐘充繆椤愶綇鑰块柡灞剧洴閳ワ箓骞嬪┑鍥╀簮闂備胶枪椤戝棝骞愭ィ鍐ㄧ疅闁圭虎鍠栫粈瀣亜閹惧鈯曢柡渚€娼ч埞鎴︽偐閸偅姣勬繝娈垮枟濞兼瑧鍙呴梺鎸庢礀閸婂摜澹曡ぐ鎺撯拺闁割煈鍣崕宥吤瑰⿰鍕煉闁绘搩鍋婂畷鍫曞Ω閿曗偓绾板秴顪冮妶鍛疄闁稿﹥绻堝璇测槈濮橈絽浜鹃柨婵嗛娴滄繄鈧娲栭惉濂稿焵椤掍緡鍟忛柛鐘崇墵閸┾偓妞ゆ帒鍊稿▍蹇斾繆娣囧崬濡奸柍瑙勫灴閹瑩骞撻幒鎾斥偓顖炴⒑缂佹﹩娈曟繛鑼枛瀹曟椽鎮欓崫鍕吅闂佹寧妫佸Λ鍕瑜版帗鐓熼幖绮瑰墲鐠愨€斥攽椤旇姤灏﹂挊鐔哥節闂堟侗鍎愰柍閿嬪灩缁辨帞鈧綆鍘奸崝鍨亜椤愵剛鐣甸柡灞剧洴瀵剟宕稿Δ鈧鏉课旈悩闈涗粶妞わ富鍨堕敐鐐哄閻樺灚娈曢梺閫炲苯澧撮柟顔兼健閸┾偓妞ゆ巻鍋撻柍瑙勫灴閹瑩寮堕幋鐘辨閻庡厜鍋撻柨婵嗘噺閸嬨儵鏌熼鍏煎仴鐎规洏鍔庨埀顒佺⊕鑿ら柟閿嬫そ濮婃椽妫冮埡浣烘В闂佸憡鐟㈤崑鎾斥攽閿涘嫬浜鹃柟顔煎€垮璇测槈閵忊€充汗闂佸綊顣﹂悞锕傛偪娓氣偓閹鈻撻崹顔界亶闂佺粯鎼换婵嬫偘椤曗偓瀵粙濡搁敃鈧鎾绘⒑闂堚晛鐦滈柛妯煎帶椤曪綁骞庨懞銉㈡嫽婵炶揪缍€濞咃絿鏁☉娆戠闁告瑥顦辨晶鐢碘偓瑙勬礃閸旀瑥鐣烽悜绛嬫晣婵炴垶眉婢规洖鈹戦缁撶細闁稿鎸鹃埀顒佺啲閹凤拷
核心提示：#include<iostream>#include<cstdio>using namespace std;struct node{ int x,y; };node a[20000]; int d[20][100000],s[20][100000],n,m,x,
#include<iostream>
#include<cstdio>
using namespace std;
struct node{
int x,y;
};
node a[20000];
int d[20][100000],s[20][100000],n,m,x,y,z;
bool cmp(const node a,const node b)
{
return a.x<b.x;
}
void buildtree(int h,int l ,int r)
{
if (l==r) return;
int mid=(l+r)>>1,p=0;
for (int i=l;i<=r;++i)
{
if (d[h][i]<=mid)
{
d[h+1][l+p]=d[h][i];
++p;s[h][i]=p;
} else
{
d[h+1][mid+1+i-l-p]=d[h][i];
s[h][i]=p;
}
}
buildtree(h+1,l,mid);
buildtree(h+1,mid+1,r);
}
int find(int h,int l,int r,int ll,int rr,int k)
{
if (ll==rr) return (d[h][ll]);
int ls=0,rs=0;
if (ll>l) ls=s[h][ll-1];rs=s[h][rr];
if (rs-ls>=k) return find(h+1,l,(l+r)>>1,l+ls,l+rs-1,k);
else return find(h+1,((l+r)>>1)+1,r,((l+r)>>1)+1+ll-l-ls,((l+r)>>1)+rr-l+1-rs,k-(rs-ls));
}
int main()
{
freopen("350.in","r",stdin);
freopen("350.out","w",stdout);
cin>>n>>m;
for (int i=1;i<=n;++i)
{
cin>>a[i].x;a[i].y=i;
}
sort(a+1,a+n+1,cmp);
for (int i=1;i<=n;++i) d[0][a[i].y]=i;
buildtree(0,1,n);
for (int i=1;i<=m;++i)
{
cin>>x>>y>>z;
cout<<a[find(0,1,n,x,y,z)].x<<endl;
}
return 0;
}
http://tech.cncms.com/sheji/js/66384.html
中查找“第k元素log(n)算法–划分树”更多相关内容
中查找“第k元素log(n)算法–划分树”更多相关内容更多精彩
赞助商链接
