P11622 [Ynoi Easy Round 2025] TEST_176 是很经典的例题，这种 trick 叫做插入标记回收。
我们扫描线，当 \(i = l\) 时插入 \(x\) 到一棵平衡树中，\(i = r\) 时询问当时记录下来的结点的值即可。
那么现在问题变成，当平衡树移动到 \(i\)，如何利用 \(a_i\) 来实时更新。实际上，这相当于对 \(\frac{a_i}{2}\) 进行一些分裂，再打上一个 \(\times -1\) 和 \(+ a_i\) 的标记，再将两棵平衡树合并起来。
现在难点就在平衡树合并这一步，实际上，可以采用原本的方式，随机按照 \(key\) 交换两个树的根，然后将第二棵树按照第一棵树的值域分裂开来分别与其左子树和右子树合并，注意需要及时合并值一样的结点，这样复杂度才是正确的。
接下来让我们将目光放到 PKUSC 2024 D2T2，将我斩于马下的题目，看看当时 chifan 是如何给出一个 2log 做法的。
还是一样的方法，不过这下更简单了，分裂出三棵树，将中间那棵整体 \(+ 1\)，再合并起来，这样看就简单多了，当然，有一个根据单调性用线段树简单维护的 1log 做法。
不难发现，只要是基于单次修改有关值域区间的题目都可以这么做到 2log，听说有一种科技可以将上述过程优化到 1log 合并。