這是曾來過咱們學(xué)校集訓(xùn)的一位大神出的~

T1

題目大意

給出一棵帶邊權(quán)的無根樹，求樹上前$k$大的路徑的長度。

$1 \leq n \leq 200000$

題解

想了一上午點(diǎn)分治，卻發(fā)現(xiàn)只會(huì)$O(nlog^3n)$的......

正解是二分第$k$大的權(quán)值，用點(diǎn)分治判斷，統(tǒng)計(jì)路徑時(shí)用兩個(gè)指針掃一下權(quán)值序列就行了......

這里記錄一種巧妙的，常數(shù)更小的方法。

考慮序列求前$k$大路徑的經(jīng)典操作:

維護(hù)一個(gè)大根堆，初始將每個(gè)左端點(diǎn)和它所能到達(dá)的最遠(yuǎn)右端點(diǎn)以及距離構(gòu)成的三元組壓入堆中，按照距離排序。

每次從堆頂彈出一個(gè)區(qū)間，就把當(dāng)前左端點(diǎn)的所有右端點(diǎn)中，與當(dāng)前彈出右端點(diǎn)最接近但是更劣的一個(gè)右端點(diǎn)作為該三元組的新右端點(diǎn)，重新計(jì)算距離并將三元組壓回堆內(nèi)，重復(fù)$k$次即可取得前$k$大路徑。

現(xiàn)在考慮如何在樹上運(yùn)用這種操作:

還是考慮點(diǎn)分治，對(duì)于每次點(diǎn)分治，找出分治子樹中的每個(gè)節(jié)點(diǎn)所屬的子樹，及這個(gè)點(diǎn)到分治重心的距離，打包成二元組存下來。

可以發(fā)現(xiàn)，只有子樹不同的兩個(gè)節(jié)點(diǎn)構(gòu)成的路徑才是有效的。因此，對(duì)于每個(gè)分治重心，將打包好的二元組按距離從大到小排序成一個(gè)序列，從后往前預(yù)處理出每個(gè)二元組向后第一個(gè)所屬子樹與當(dāng)前二元組不同的位置。

將每個(gè)二元組與其向后第一個(gè)所屬子樹與當(dāng)前二元組不同的位置處的二元組打包后壓入一個(gè)全局堆里，作為一條路徑。

這個(gè)堆的功能類似序列版本時(shí)的堆，每次彈出堆頂元素后，將這個(gè)元素左端點(diǎn)在對(duì)應(yīng)分治重心的序列中，下一個(gè)與當(dāng)前左端點(diǎn)所在子樹不同的二元組作為新的右端點(diǎn)，壓回堆中。

可以發(fā)現(xiàn)，對(duì)于每個(gè)分治重心的每個(gè)二元組，最多只有一個(gè)對(duì)應(yīng)的二元組在全局堆中，空間復(fù)雜度$O(nlogn)$。同時(shí)，對(duì)于維護(hù)最外層的堆，和對(duì)二元組序列的排序兩部的復(fù)雜度均為$O(nlog^2n)$，因此時(shí)間復(fù)雜度為$O(nlog^2n)$。

T2

題目大意

維護(hù)一個(gè)序列，要求支持區(qū)間最大值、區(qū)間并上一個(gè)數(shù)、區(qū)間或上一個(gè)數(shù)三種操作。

題解

出于各種原因十天前剛考過原題大家都$A$了這題~

考慮線段樹。

考慮在暴力遞歸到底以修改每個(gè)線段樹節(jié)點(diǎn)的基礎(chǔ)上添加優(yōu)化，那么顯然有一個(gè)結(jié)論:

若一個(gè)區(qū)間某一位的值全部相同，那么對(duì)于這一位來說，接下來進(jìn)行任何的修改操作，都只需要區(qū)間打$tag$，而不用暴力遞歸到底。

具體實(shí)現(xiàn)時(shí)，只需要維護(hù)一下區(qū)間或和和區(qū)間并和，并判斷一下是否全為$0$或$1$即可。

然后，考慮位運(yùn)算的結(jié)合律:

$(A&B|C)&D=(A&(B&D))|(C&D)$

$(A&B|C)|D=(A&B)|(C|D)$

于是維護(hù)區(qū)間或標(biāo)記和區(qū)間并標(biāo)記，下傳時(shí)強(qiáng)制先做并再做或。

此時(shí)，只要在區(qū)間或時(shí)，判斷一下修改的值有$1$的位置在當(dāng)前區(qū)間上是否全為$0$或$1$，如果為真則打標(biāo)記停止遞歸。區(qū)間并同理。

復(fù)雜度可通過勢(shì)能分析證得是$O(nklogn)$。

T3

這是個(gè)暫時(shí)不會(huì)待填的坑~

轉(zhuǎn)載于:https://www.cnblogs.com/zltttt/p/8577253.html

總結(jié)

以上是生活随笔為你收集整理的2018.3.15校内互测总结-点分治-线段树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。