賽時

看T1，然后想不到優化，一直卡在T1，然后腦子不轉

想了一會想了一個優化，然后2h過去了，不確定正確性，寫了一個拍

賽場上第一次寫拍，感覺還是很好寫的

后來證明掛了，原因是沒有判前導0的情況，我賽場上真沒想到這一點，然后掛了

修改完后，然后還是掛，找了好久沒有找出問題，拍了好久，后來核彈直接指出問題，輸入時沒開long long直接爆斃

加上一個判無解優化，就是判斷是否需要兩個0，即 n%B^2==0就過了

然后看T2，發現是期望，想不出來，直接退了，還是dp不太行，膽怯了

T3太復雜了，沒細想

T4發現可以直接用上次的掃描線思想拿到60分

打完比賽結束了

就是狀態不太好，應當好好調整一下

賽后

T2非常簡單

考慮樹上，我們只需要轉化為子樹問題即可，考慮期望就是考慮當前的根節點，會不會產生1的貢獻

它能產生1的貢獻當且僅當在子樹中第一個選的數為根，概率是 \(1/siz_u\) 的

然后就做完了

或者考慮dp，考慮當前點被選的期望+兒子的期望，本質相同

因為子樹是獨立的，并且我們現在只考慮一個點在1時間的概率就能做

關鍵就是定下來時間和點，把問題簡化

T3我們考慮問題就是需要把一些連續段按照一種方式排列使得上一個的最大值大于這一個的最小值

然后考慮到一種調整方式，使得他們首尾相接，然后就能證明，只要不存在值域上的斷點，就能合法

因為集合是無序的，并且添加的是排列，所以一些集合添加一個i添加到哪里是不會算重的

只要知道枚舉到了哪個數，開始了幾個集合，結束了幾個集合，就能描述一種不同的狀態

把上面3個存到dp里，轉移即可

T4，60分做法，考慮枚舉本質不同的 \((a,b)\) ，然后統計 \((c,d)\) 答案

因為兩個集合的問題只能枚舉一個然后更新另一個，所以沒法在算法本質上做到更優

但可以在統計答案時做到更優

考慮拆貢獻，其實我在寫的時就已經能發現了，實際上比a大的a對應的c和比b大的對應的c是獨立的，可預處理取交集的

貢獻即為 \(a_i+b_j+max(ac_i,bc_j)+max(ad_i,bd_j)\)

然后發現 \(j\) 是可以上線段樹上維護的，然后又發現 \(ac_i,bc_j\) 是單調的，也就是在掃描線 i 的過程中，所對應的j是單調的

做一下區間推平維護即可

pjy做法：發現由于 \(ac_i,bc_j\) 是單調的，所以在i固定時，一段j的 \(max(ac_i，bc_j)\) 后綴是固定的，然后再把 \(i,j\) 反轉，再跑一邊

發現所形成的連續段形成2n個連續段，正好能拼成一個大矩形，可以進行線段樹的維護

本質上就是兩個單調的序列，本質不同的max只有2n個