又是一道資料結構組合題，起碼不是套娃題（指樹套樹套...）
首先，詢問一個串中多個串的出現次數之類，肯定是 ACAM，詢問就是求所有詢問串的末尾節點的子樹包含的匹配串節點的最大值，
發現有 \(\sum |S|\) 限制，純純的根號分治，
\(|S|>B\)，\(O(n)\) 算一遍各串在詢問串里的出現次數，線段樹維護，
只用考慮 \(|S|\leq B\)，
Solution 1
插入詢問串時，在 dfn 序上把它的子樹都分進它這一組，如果詢問串末尾節點本來就屬于一組了，就不標記子樹，回答詢問時就是把匹配串上的點拿出來，根據之前的分組把點扔到桶里，最后對每個桶取 max，
第二部分修改 \(n\log{n}\) 次，詢問 \(n \sqrt{n}\) 次，
實在不行搞點抽象多重分塊，分三層可以搞成修改 \(O(n^{0.25})\)，
Solution 2
把匹配串點拉出來建虛樹，我們對按照子樹內的匹配串點數量對所有子樹排序，從多到少列舉子樹，判斷從子樹根到原樹根的路徑上是否有詢問串，單點加鏈查詢轉化成區間加單點查詢，發現區間加可以只用區間覆寫代替，賦 1 表示有覆寫就行了，用 bitset 維護除個 w，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/524970.html
標籤：其他
上一篇：yii2、百度地圖、bootstrap沖突的處理程序
下一篇：資料結構與演算法概述