下次一定要认真认真认真算算动态空间了 /ll
第一次知道 set 不能指针相减 /jk
链接：link
题解：link 的题解部分
时间：3h20min (2025.11.06 18:40~22:00)
题目数：4
难度：
| A | B | C | D |
|---|---|---|---|
| \(\color{#FFC116} 黄\) | \(\color{#FFC116} 黄\) | ||
| *1400 | *1500 |
估分：[50,100] + 100 + 20 + 35 = [205,255]
得分：90 + 100 + 52 + 30 = 272
Rank：1/6
场祭
读题。
A 是 Boruvka？好像不会维护，看看能不能找点性质只保留少量的边。根据人类智慧，边权 \(>n\) 的边几乎不可能出现在最终的 MST 中，所以只保留边权 \(\le n\) 的边即可，保险起见开到 \(2n\)。用的是一个根号复杂度的枚举，大样例跑了 700ms，因为学校机子性能很差所以应该稳过了。
开 B，哦打表找规律题，切了。
此时只过了 1h。
开 C，不怎么会，但是发现 D 似乎可以莫队，于是去思考莫队了，但是发现不会维护，不过倒是想到了个 \(O(nq \log n)\) 的主席树做法。
就是先转化为 \(b_r > a_l > \max _{i=l+1} ^{r-1} \{a_i\}\)，发现 \(a\) 的限制可以笛卡尔树预处理出来，令 \(a_i\) 能延伸到的最右端点为 \(rx_i\)。
好像挺有前途的？似乎还真可以用这个 \(O(q \sqrt n \log n)\) 莫队做，左端点就是主席树的查询，右端点就是维护一个 set 表示 \([L,R]\) 内 \(rx_i > R\) 的 \(a_i\)，写写写，怎么 CE！
原来 set 不能指针相减吗 /jk
寄！
没时间了打了个暴力走人了。
补题
天依宝宝可爱！