伸展樹總結(jié)

最近做的1些Splay題及思路

BZOJ 1588 就是求1個(gè)數(shù)的先驅(qū)和后繼，用Splay很簡單

POJ 3468  很經(jīng)典的線段樹題目，用Splay做練習(xí)怠惰標(biāo)記

HDU 1890  觸及區(qū)間翻轉(zhuǎn)，注意直接以數(shù)列下標(biāo)建樹，對原數(shù)列排序后，直接查找，找到后刪除。

HDU 3436  很好的1道題，首先離散化，Splay 樹中每一個(gè)節(jié)點(diǎn)表示的是1段區(qū)間，

TOP:首先刪除這個(gè)元素，再將其插入到隊(duì)首

RANK：即尋覓第K大，經(jīng)典操作

QUERY：將該元素Splay 到根部，size[ch[root][0]]+1即是排名

HDU 3487 多了1個(gè)操作切割，常規(guī)操作

BZOJ 1269  SPLAY的1些常規(guī)操作，沒甚么特殊的

BZOJ 1500 多了1個(gè)最大序列和，處理類似于線段樹中的區(qū)間合并，其它是常規(guī)操作；此題需要回收內(nèi)存?？战泓c(diǎn)的值要設(shè)為-inf才正確。中間TLE 了很屢次

POJ 3580  REVOLVE 操作可以看成1次刪除和1次插入，例如[a,b]向右移動(dòng)T步等價(jià)于[a,b-t],[b-t+1,b];先刪除[a,b-t],再將其插入到a+t后面；中間TLE 了很屢次

生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)