DS 做题记录

QOJ#971. Binary Search Tree

考察了换维处理的熟练度，一开始没有想到什么好的换维方向，看了一篇网络题解后有所启发，想到笛卡尔树上贡献的充要，即 \((a_i,p_i)\) 表示偏序值和堆值的二元组，询问 \(x\) 时能访问到的充要是 \(\max_{a_i \le a_j \le x} w_j = w_i\) （假设 \(a_i \le x\)，vice versa）。

于是想到按 \(a\) 排序后贡献，将询问和修改混到一起排，\(a\) 相同的先询问后修改，那么遇到询问时将其所代表的位置清空且初始化为询问时间（线段树以 \(a\) 为下标维护操作时间的前缀 \(\min\)），修改相当于是对有影响的询问做取 \(\min\)，取 \(\min\) 成功的加上 \(w\) 的权，最后取线段树中每个点的权即可。

注意 segment beats checkmin 时维护的是 max 和 second max，不要搞混了。

时间复杂度 1log。

题解给的是兔队线段树 2log 做法，感觉这个优化形如UOJ#515. 【UR #19】前进四。