orz flyfree 太强了，提供一个历史和线段树的做法。首先离散化，则得到了数轴上的若干线段。

将 $[l_i,r_i]$ 称为区间，$[A,B]$ 称为询问。扫描区间的下标。

设当前扫到了 $R$，则当前数组 $v_i$ 表示 $[i,R]$ 的美丽度。则当 $R=B$ 时查询 $[A,B]$ 就是询问所有 $i\in [A,B],v_i$ 的历史和。

考虑如何维护扫描过程中 $[L,R]$ 的美丽度，设 $1\sim R$ 的所有区间中最后一个覆盖线段 $i$ 个编号是 $p_i$，则当前线段 $i$ 会对 $v_{1\sim p_i}$ 做贡献。

每次扫描线的右端点移动，新加入一个区间，会改变一些 $p_i$，设原来 $p_i=x$，后来 $p_i=y$，则这次移动会对 $v_{x+1\sim y}$ 新产生贡献。

每次都是覆盖一段区间，可以用珂朵莉树维护，改变一个颜色段的 $p_i$ 可以用一次区间加完成，而这样的区间加只有 $O(n)$ 次。

然后选择心怡的维护历史和的方法即可，例如维护当前完成的操作数 $T$，当前数组 $A$，设历史和数组为 $B$，再维护一个 $C_i=B_i-A_iT$，则只维护 $A,C$ 即可维护 $B$。

时间复杂度为 $O(n\log n)$。https://qoj.ac/submission/2191575