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】前进四。
UPD：其实发现就是前进四，segment beats chkmin 成功后加点权是可维护的。
P6109 [Ynoi2009] rprmq1
喵喵题。
首先想个询问行左端点固定的 case，然后发现可以用支持区间加，区间历史最值查询的线段树做，这样可以做到 \(O((n+q) \log n)\)。
发现行右端点固定也是类似的，只不过要注意先加负数否则会出问题。
然后发现上类似猫树分治的东西即可解决，原理大概是矩形 max 拆成在一个线段树区间上拆成两个，拥有了固定的一个端点，可以对很多矩形快速计算。