模擬賽亂寫（你猜我欠了多少。

1. 嘉然登場

   確實是好玩的題。

   考慮先將其分成兩組，一組 \(<\frac k2\)，一組 \(\ge\frac k2\)

   考慮使一個數在填的時候使所以剩余數都可以填它旁邊，或都不可以。

   可以將每個 \(<\frac k2\) 的數對應其最小可以放的 \(\ge\frac k2\) 的數，然后從大往小放 \(\ge\frac k2\) 的數，每次放完后將所有與它對應的數都一塊放了。

2. Clannad

   考慮其本質是求虛樹大小。

   考慮一個點在虛樹內有兩個限制：

   1. \(u\) 子樹內存在至少一個屬于序列區間的點。

   2. 除 \(u\) 子樹外其他點和 \(u\) 構成的子樹內至少存在一個屬于序列區間的點。

   發現滿足第一個限制但不滿足第二個限制是好求的，直接求區間 \(lca\) 即可。

   考慮用滿足 \(1\) 的減掉滿足 \(1\) 且不滿足 \(2\) 的點。

   對于滿足 \(1\) 的點，考慮離線，掃描線可以維護右端點。新加一個點，就對其到根的路徑染上當前顏色，最后統計顏色在 \([l,r]\) 之間的點個數即可。

   染色可以珂朵莉，統計用樹狀數組就行。

3. 修水管

   這是逆天狀態的 \(dp\) 和逆天讀題

   考慮求 \(r\) 輪中第 \(i\) 段被修復的概率。

   考慮轉移，發現其之和有幾次水流到過有關，所以設 \(dp_{i,j}\) 表示前 \(i\) 個位置，在 \(r\) 輪中修復了 \(j\) 次的期望。

   \(dp\) 枚舉當前是否修過轉移，然后就都可以直接推了。

4. 小孩召開法 3

   trick 貓樹分治。

   考慮類似貓樹，每次對分割點左右進行處理，查詢可以直接合并。

   發現空間不太夠，可以將其離線，對在哪一層排序，只維護一層信息即可。

5. 橋橋

   記一下 Kaguya 發現的將 \(\log\) 換成 \(\alpha\) 的做法。

   首先對詢問分塊，每塊先將這塊之前的修改改掉，對于塊內的修改，每次查詢時暴力跑一遍，在撤銷即可。

   用可撤銷并查集維護，可以干到 \(n\sqrt n \log n\) 。

   考慮前綴的時間排序，可以直接歸并，將 \(\log n\) 乘在 \(n\) 上，調整塊長可以做到 \(n\sqrt{n \log n}\)

   考慮整一下并查集，發現可以路徑壓縮，對于塊內的詢問，最多一次完全展開是 \(\sqrt n\) 最多 \(n\) 次，不會有復雜度問題。而加邊查詢的 \(\log\) 就變成了 \(\alpha\)，復雜度 \(n\sqrt{n \alpha(n)}\)。

   但因為常數問題，其實很難跑過帶 \(\log\) 做法。

6. 春色春戀春熙風

   樹上啟發式合并板子。

   考慮每次數組維護重兒子信息，輕兒子跑暴力即可。

   線段樹合并在 CF 上也能過，學校 OJ 跑不過去。

7. 雪色雪花雪余痕

   發現其就是維護凸殼。

   考慮凸殼性質，其差分序列不降，可以直接跑 \(dp\)。

   設 \(dp_{i,j}\) 表示用 \(i\) 個正數，和為 \(j\)，因為差分不降，所以最少是 \(\sum\limits_{k=1}^i k=j\)，\(i\) 是 \(\sqrt m\) 級的。

   因為有非負限制，考慮枚舉最小值的最左邊位置，欽定最小值為 \(0\)，最后在平移。

   左邊長度是定值，右邊是一個 \(\le k\) 的限制，用前綴和做掉，平移也可以用前綴和。

   時空都帶根號，用撤銷空間可以省掉根號。

沒有鮮花可以不寫，不要寫這種東西臟了我的眼