题解：AT_abc467_g [ABC467G] Many Sweets Problem

· · 题解

考虑，如果这个查询是静态的，那么我们可以在线段树上套 vector，存储每个节点代表的区间里面的所有数，然后二分最小值。

但是这题带修，于是我们可以树套树，具体地，在外层的权值线段树上套内层的树，内层维护表达在某一个范围的数在哪些位置出现，以及它们贡献的区间和，查询直接在外层的线段树上二分糖的最小值即可，可以顺便统计吃了多少糖。

修改和查询均是 \mathcal{O}(\log ^ 2 n) 的。