拜謝良心出題人。拜謝良心出題人。拜謝良心出題人。拜謝良心出題人。

25noip二十連測day9

鏈接：link
題解：題目內(nèi)

時(shí)間：4h (2025.10.27 14:00~18:00)
題目數(shù)：4
難度：

估分：100 + 100 + 40 + 5 = 245
得分：100 + 100 + 40 + 10 = 250
Rank：67/130

場祭

下發(fā)文件 80MB？這么多大樣例 /jy，拜謝良心出題人。

讀題。

A 簽。

B 好像并不困難，考慮冰茶姬維護(hù)，想了想發(fā)現(xiàn)可以給每個(gè)點(diǎn)染色，然后操作二就是同連通塊內(nèi)全部置為同一顏色，然后發(fā)現(xiàn)這個(gè)東西可以再開個(gè)冰茶姬維護(hù)，于是就做完了，只不過用了兩只不同的冰茶姬有點(diǎn)神秘（？

開 C，思考半天不會(huì)，想去打暴力的時(shí)候忽然發(fā)現(xiàn)可以從編號(hào)連續(xù)入手，記 \(a_i,b_i\) 分別為 \(i\) 從出邊指向的最大 / 最小編號(hào)，問題就可以轉(zhuǎn)化成求滿足 \(\max _{i=l} ^r a_i \le r \land \min _{i=l} ^r b_i \ge l\) 的區(qū)間 \([l,r]\) 方案數(shù)，似乎是線段樹維護(hù)？但是發(fā)現(xiàn)左端點(diǎn)不會(huì)處理，右端點(diǎn)也不會(huì)處理！

不會(huì)了，寫了 \(x<y\) 的性質(zhì)跑路了。

D 太困難了，推了半天才推出 \(n=2\) 的正解和 \(n=3\) 的錯(cuò)解。

然后一提交發(fā)現(xiàn) \(n=3\) 的錯(cuò)解再?zèng)]過樣例的情況下過了那個(gè)點(diǎn)？？

補(bǔ)題

補(bǔ) C，哦原來真是分治！賽時(shí)被我 1s 否定掉了來著（

考慮當(dāng)前分治區(qū)間 \([L,R]\)，把限制拆到 \([L,mid]\) 和 \((mid,R]\) 兩個(gè)區(qū)間上，則 \([l,r]\)? 合法需要滿足：

1. \(\max _{i=l} ^{mid} a_i \le r\)。
2. \(\min _{i=l} ^{mid} b_i \ge l\)。
3. \(\max _{i=mid+1} ^r a_i \le r\)。
4. \(\min _{i=mid+1} ^r b_i \ge l\)。

注意到限制 \(2,3\) 只與一個(gè)區(qū)間端點(diǎn)有關(guān)，所以可以先掃一遍判掉，直接不考慮不滿足這些條件的區(qū)間。

然后限制 \(1,4\) 是類似的，所以只考慮限制 \(1\) 怎么做。發(fā)現(xiàn)這個(gè)是容易的，因?yàn)樵谝粋€(gè)端點(diǎn)（即 \(mid\) 或 \(mid+1\)）確定的時(shí)候，另一個(gè)端點(diǎn)在逐漸向外擴(kuò)展的時(shí)候得到的 \(\max a_i\) 是單調(diào)不減的，\(\min b_i\) 是單調(diào)不增的，所以可以枚舉 \(l\)，然后雙指針找出 \(l\) 可以對(duì)應(yīng)的 \(r\) 的區(qū)間，就好了。

天依寶寶可愛！