一個好用的工具——析合樹

oi-wiki

例題

CF526F

題意：
給出一個1~$n$的排列，問有多少個區間的值域是連續的。

題解：
線段樹+單調棧做法
分治做法
析合樹做法
圖論做法

CF997E

題意：
給出一個1~$n$的排列，有$q$次詢問，每次問$[l,r]$內，有多少個區間的值域是連續的?

題解：
單調棧+線段樹的掃描線做法
析合樹離線做法
析合樹在線做法

LuoguP4747

題意：
給出一個1~$n$的排列，有$q$次詢問，每次問包含位置區間$[l,r]$的連續段的最短長度是多少，連續段的定義為排序后值域連續，可以證明解存在且唯一。

題解：
掃描線做法
析合樹做法
圖論做法：題解1 題解2

XSY3344

emm，這題原題好像是2018EC Final B.Mysterious … Host
這里有簡要題解

題意：

題解：
所有$n$階排列形成的等價類個數 等于 有$n$個葉子的不同形態的析合樹棵樹。

析合樹有以下性質：

• 合點的兒子個數$\ge 2$（葉子節點除外）
• 析點的兒子個數$\ge 4$

設$f_i$為所有$i$階排列形成的等價類個數（即有$i$個葉子的不同形態的析合樹棵樹）。
顯然可以$O(n^2)$DP得到$f_n$。

多項式優化：
記$F(x)={\sum }_{i\ge 0}{f}_i{x}^i$，那么有
$$F(x)=(F^2(x)+F^3(X)+F^4(x)+...)+(F^4(x)+F^5(X)+F^6(x)+...)+x$$
$$F(x)=(F^2(x)+F^4(x))(1+F(x)+F^2(X)+F^3(x)+...)+x$$
$$F(x)=\frac{F^2(x)+F^4(x)}{1?F(x)}+x$$

參考——兩個學長的$Blog$：
https://www.cnblogs.com/ywwyww/p/10193748.html
https://blog.csdn.net/Mys_C_K/article/details/85385019

附：析合樹形態計數 dp

LuoguP6795

總結

以上是生活随笔為你收集整理的连续段问题小结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。