析合樹建樹——2025.7.10 鮮花
析合樹建樹
大笑江湖
我手拿流星彎月刀
喊著響亮的口號
前方何人報上名兒
有能耐你別跑
我一生戎馬刀上飄
見過英雄彎下小蠻腰
飛檐走壁能飛多高
我坐船練習水上漂
啊 林子大有好多的鳥
啊 做好事不讓人知道
啊 是是非非惹人惱
啊 啊
江和湖波浪滔滔
看我浪跡多逍遙
誰最難受誰知道
天下第二也挺好
風和雨來的剛好
誰比我的武功高
大笑一聲地動山搖
江湖危險快點跑
我騎著小毛驢
身后背著彎月刀
降龍十八掌
只練會了第一招
打得過就打
打不過我就跑
武林爭斗是是非非
恩恩怨怨怨何時了
咱輩分比較小
昨天剛報名上道
各路英雄好漢
沒事你就別和我瞎鬧
如果你認輸
我就回家睡大覺
俺娘說輸贏不重要
開心才重要
我手拿流星彎月刀
喊著響亮的口號
前方何人報上名兒
有能耐你別跑
我一生戎馬刀上飄
見過英雄彎下小蠻腰
飛檐走壁能飛多高
我坐船練習水上漂
啊 林子大有好多的鳥
啊 做好事不讓人知道
啊 是是非非惹人惱
啊 啊
江和湖波浪滔滔
看我浪跡多逍遙
誰最難受誰知道
天下第二也挺好
風和雨來的剛好
誰比我的武功高
大笑一聲地動山搖
江湖危險快點跑
江和湖波浪滔滔
看我浪跡多逍遙
誰最難受誰知道
天下第二也挺好
風和雨來的剛好
誰比我的武功高
大笑一聲地動山搖
江湖危險快點跑
江和湖波浪滔滔
看我浪跡多逍遙
誰最難受誰知道
天下第二也挺好
風和雨來的剛好
誰比我的武功高
大笑一聲地動山搖
江湖危險快點跑
江湖危險快點跑

之前寫了 樸素析合樹計數,其中沒寫怎么建樹,結果模擬賽考了(雖然不需要建就是了),場上推了兩個小時無果,破防了,半報復性的寫一篇。
省流:只要你知道析合樹是什么且不和我一樣傻到不會建一個 ST 表判斷是否連續就會建。
給出增量法的流程,這里我們認為葉子是析點:
考慮依次插入,用棧維護當前建好的析合樹森林的根節點,考慮如何插入一個點。
我們先找到和其能組成連續段的最靠左的點,記為 \(L\)。
考慮重復執行以下操作合并一段后綴,直到合并到 \(L\) 之前:
若最后一個點是合點且和當前點結合以后依然是合點,則將其并到其兒子里,判斷結合以后是否是合點可以維護其最靠右的兒子的左端點,判斷是否能和新點組成一個連續段即可。
若最后一個點和當前點能組成連續段,則新建一個點并將這兩個點視為其兒子,這個點一定是合點。
否則考慮找到最靠后的合法連續段,容易發現一定能找到,合并成一個析點(這個點一定是析點)。
復雜度顯然是均攤的,難點在于找 \(L\)。
其實也不難,我們發現連續段滿足 \(\max - \min = r - l\),而 \(\max - min \ge r - l\)。所以我們維護 \(\max - \min - l\) 的最靠左的最小值即可。
代碼寫了,但是沒存,就這樣吧,看不懂可以看 oi-wiki。
P
垃圾鮮花別浪費我圖!





本文來自博客園,作者:xrlong,轉載請注明原文鏈接:http://www.rzrgm.cn/xrlong/p/18977695
版權聲明:本作品采用 「署名-非商業性使用-相同方式共享 4.0 國際」許可協議(CC BY-NC-SA 4.0) 進行許可。

浙公網安備 33010602011771號