题解：AT_abc389_f [ABC389F] Rated Range
CuFeO4
·
·
题解
和首切差了 6 分钟，没有抢上，悲。提供一个不用脑子的平衡树做法。
对于每个询问，我们将其插入一颗平衡树中，记录其在平衡树上的节点编号。
然后从左往右做扫描线，对于每个形如 [l,r] 的更改，将平衡树上值域在 [l,r] 中的分裂出来进行区间加，最后在平衡树上遍历，统一查询答案即可。
由于每次只是加 1，可以做到 O(n\log q) 的复杂度，比官方题解的 (n+q)\log V 优，尽管跑得并不快罢了。
AC Link。