zhangxyhp

摘要： 前言 本來早就該學(xué)笛卡爾樹了，但暑假打模擬賽就一直沒學(xué)成。于是就打算先不學(xué)了，結(jié)果又發(fā)現(xiàn)后面有個(gè)笛卡爾樹專題，只好來學(xué)學(xué)。 定義 笛卡爾樹是一棵二叉樹，每個(gè)點(diǎn)有一個(gè)鍵和一個(gè)值，鍵滿足堆的性質(zhì)，值滿足二叉搜索樹的性質(zhì)。沒錯(cuò)當(dāng)鍵隨機(jī)時(shí)，這就是個(gè) Treap。 建樹 如果值單調(diào)遞增，那么就可以線性建樹。具 閱讀全文