特化析合樹計數相關

これでいいなのだ　好好好
好きの需要と供給の寒暖差　また風邪っぴきさん
忍ぶ修行は効率が肝心だとか　わかってるもん
でも簡単じゃない　ねえ簡単じゃないの
心の乙女があれこれ言っちゃうの
くぅ問題が大　ねえ頑張ってドクター　感情が爆散
頭あちちな　好好好のラブ連単
きみとしたいことがいっぱい
いつも「足んないな」ってなる問題
欲張り星人のせいなんです
もう　嫌い　大嫌いとか思ってみたい
でも好好好のラブ連単　“愛したほうが勝ち”なんだって
これでいいなのだ　好好好
ところがローな脳がお目覚めだ
BAD駄々っ子　ぱーりない
もうだめだ　誰にでも嫉妬しちゃって胸が取れそう
最高セット　こっちむいて
最低セット　あっちむいて
感情は日替わり　へい、テンションチャンプルー
また押すっきゃない　ねえ押すっきゃないの
あたしが重すぎて揺れない戀シーソー
くぅ問題が大　ねえ頑張ってドクター　殘念が爆誕
頭あちちな　好好好のラブ連単
気持ち抑え込んで一旦
きみが「足んないな」ってなるような
大人バランスがいいんだって
忙しいだなんて　うっそー
ごめん寢てたなんて　うっそー
迷走しちゃうあたし　安らかに死ねばいいのに
好好好のラブ連単　これでいいのかな
頭あちちな　好好好のラブ連単
きみのしたいこともちょうだい
刺激バッキュンビーム撃ち放題
欲張り星人になっちゃえよ
大嫌い　超嫌いとか思っちゃうの？
やだ　好好好のラブ連単　愛されちゃうの欲しがっています
へっちゃらピーポー　イタさも逆におっけー
はっちゃけピーポー　ダサさも逆におっけー
ぶっちゃけピーポー　ウザさも逆におっけー
言ったらいいじゃん　せーので好好好
へっちゃらピーポー　イタさも逆におっけー
はっちゃけピーポー　ダサさも逆におっけー
ぶっちゃけピーポー　ウザさも逆におっけー
言ったらいいじゃん　せーので好好好
これでいいなのだ　好好好
	
這樣就好啦 好好好
喜歡的需求和供應的溫度差 又要開始感冒啦
忍者修行最重要的是效率什么的 我當然知道啦
但是一點都不簡單 一點都不簡單的啦
內心的乙女又要有一堆話啦
ku~ 問題一大堆 吶加油吧醫生 感情在爆炸
令人頭疼的 好好好的愛的連勝
有很多想和你一起做的事
總是“不夠”的問題
都是貪婪星人的錯
夠啦 討厭 最討厭什么的試一下嘛
可是好好好的愛的連勝 “愛上了就是勝利”的說嘛
這樣就好啦 好好好
可是低迷的腦子清醒了
壞脾氣的孩子無法開派對
忍不下去了 對誰都感到嫉妒仿佛心臟要跳出來
最高配置 看向這邊
最低配置 看向遠方
感情是日更的 情感大雜燴
還是只有繼續推 吶只能繼續推的好嘛
戀愛的蹺蹺板因我太重而紋絲不動
ku~ 問題一大堆 吶加油吧醫生 可惜在爆炸
令人頭疼的 好好好的愛的連勝
先抑制一下自己的感情
果然就會覺得你“不夠”
大人的平衡是好的一說
現在很忙啦什么的 騙你的啦
抱歉剛才在睡覺什么的 騙你的啦
開始迷路的我 安靜地死掉就好啦
好好好的愛的連勝 這樣就好了嗎？
令人頭疼的 好好好的愛的連勝
把你想做的也交給我吧
刺激暴擊光束隨便放
變成貪婪星人吧
最討厭 超級討厭什么的會這么覺得嗎？
不要嘛 好好好的愛的連勝 就是想要被你愛上的好嘛
簡單的說 中二什么的也可以哦
放開的說 出丑什么的也可以哦
大概的說 煩人什么的也可以哦
說出來就好啦 大家一起好好好
簡單的說 中二什么的也可以哦放開的說
出丑什么的也可以哦大概的說
煩人什么的也可以哦
說出來就好啦 大家一起好好好
這樣就好啦 好好好

可以先看：link，應該不算是前置，不看對理解也沒有阻礙，只是這里是對照著說的。

這里依然只講析合樹的計數相關部分（雖然我還沒找到用這種析合樹建樹做的題）。

注意和樸素析合樹的定義區分一下。

設排列是 \(P\)。

定義連續段是 \([l, r] \text{ s.t.} \max_{i\in [l, r]} P_i = r \land \min_{i\in [l, r]} P_i = l\)。

容易發現連續段不可能嚴格相交（即不算包含），但這里一個點不一定是連續段。

依然建出樹形結構，這里的若一個葉子不是連續段則稱其是非法葉子（注意非法葉子事實上是合法存在的葉子）。

依然定義合點是一個點滿足其任意一個非平凡連續兒子（即長度不為 \(1\) 且不是全部）都是連續段。

定義析點是不是合點的點。

這里為了性質敘述的方便，我們定義只有兩個兒子且不存在非法葉子的點是合點，但存在非法葉子的點和葉子節點是析點。

類似的性質依然成立：析點滿足其任意一個非平凡連續兒子（即長度不為 \(1\) 且不是全部）都不是連續段。

證明類似，考慮到其若有非平凡連續兒子形成連續段則可以將這些兒子縮成一個合點。

我們這里沒定義兒子序列，因為我們有更好的性質刻畫。

合點有性質：其所有兒子都是析點。

證明：若其有兒子是合點，則其合點兒子的一段兒子前綴或后綴一定可以和其他點組成新的連續段，這樣就相交了。

析點有性質：其兒子可以是析點或合點，但其任意兩個非非法葉子兒子之間都一定有一個非法葉子，且開頭結尾一定是非法葉子。

證明：若其有兩個非非法葉子兒子之間沒有一個非法葉子，則其可以合并，若開頭不是非法葉子，則其除了開頭節點以外的點可以合并。

以上證明有一些邊界情況的分討，但根據定義可以直接推出，讀者自證不難。

依然考慮計數（以下部分涉嫌口胡，我沒找到題目能驗證其正確性）：

考慮求一個長為 \(l\) 的合點方案數：

這個很簡單，我們直接枚舉第一個兒子，用類似樸素析合樹的做法，即枚舉其第一個兒子的長度 \(k\)，于是我們要找一個長為 \(k\) 的排列且其任意前綴都不是連續段，設其數量是 \(g_k\)，顯然有單步容斥遞推式：

可以 \(n\log n\) 甚至 \(\frac {n\log^2 n}{\log\log n}\) 甚至 \(n \log^2 n\) 甚至 \(n ^ 2\) 求出。

所以最后答案是 \(\sum_{i = 1}^{n - 1}g_i(n - i)!\) 這里就沒有乘 \(2\) 這一說了。

考慮求長為 \(l\) 的析點方案數，我們依然可以容斥一下，直接用總的減去合點，但這里我們給出一個更易擴展的做法：

我們發現合法葉子可以代替兒子序列天然分割，于是我們設 \(f_{i, c}\) 表示長為 \(i\)，有 \(c\) 個合法葉子的方案數。

直接轉移是不難的：\(f_{i, c} = \sum_{k < i} f_{k, c - 1}\)，難點在求合法葉子的方案數，即求一個長為 \(k\) 排列滿足其沒有任意一個非平凡連續段的方案數 \(a_k\)。

雖然連續段的定義看似更嚴了，但這個事實上有十分優雅的做法：

我們依然是考慮析合樹，考慮依次插入每個點，考慮插入地 \(n\) 個點的方案數。

首先可以證明插入前一定是一個析點且至多有一個合法點：

• 若沒有合法點：此時其是一個長為 \(n - 1\)，此時我們可以將新點插入任意一個置換環中，方案數是 \((n - 1)a_{n - 1}\)。

• 若其有合法點：我們枚舉其合法點長度 \(l\)，考慮其最靠左能取到 \([2, l + 1]\)，最靠右則是 \([n - l - 1, n - 2]\)，共計 \(n - l - 2\) 種取法。要求插入后沒有連續段，也就是插入后 \(n\) 前的連續段都超過 \(n\)，在逆排列上考慮，其相當于是求長 \(l + 1\) 且只有 \([1, l + 1]\) 是連續段的方案數，是 \(a_{l + 1}\)，剩下的 \(n - 1 - l\) 有 \(a_{n - 1 - l}\) 種填法。

簡單化簡一下，總方案數是：

于是怎么做都行了，可以 \(n\log n\) 甚至 \(\frac {n\log^2 n}{\log\log n}\) 甚至 \(n \log^2 n\) 甚至 \(n ^ 2\)（甚至比樸素的好求）。

其實這是經典問題：SIF 排列計數，可以直接看論文（雖然寫的好像很迷惑）。

可以做一下：Jellyfish and OEIS。