以下假设 $n,m$ 同阶。
很好的题目！
第一个重要的观察就是，这个操作的顺序显然是不影响这个答案的。
我们想到我们不能直接去进行这个操作，因为他涉及到 $O(n)$ 个点，就算再怎么维护，都是困难的，我们要把他压缩一波。
我们要把这个信息最好是压到 $O(1)$，但在没有预处理的情况下有些困难。
我们先不考虑查询，我们直接考虑给一堆修改，你怎么小空间地干这个事情。
首先明显的想法是，这个前缀加有点太蠢了，考虑差分一下，变成单点加，后缀最大值。
然后你发现你可以把调换两维啊。既然你这个单点加的顺序没有关系，那我们就直接从后往前考虑，刚好算得就是后缀最大值。
然后你就变成了，把这些操作呢按照以 $x$ 为第一关键字从大到小，以 $y$ 为第二关键字从小到大排序，依次考虑，于是你发现你根本不需要考虑 $x$ 的问题，你直接把排完序后的 $y$ 求一个前缀最大值就可以了。
这个时候你发现前缀最小值这个东西是好东西！他可以看作是一个半裙元素，可以简单地拼接，且信息量为 $O(1)$。只需记录内部前缀最大值，以及总和，即可方便地合并。
然后我们到了这个序列上呢，你发现你还是要把区间排序，这个事情难做的，因为你至少要根号 log 的复杂度。然后考虑你干脆先排好序，然后在排好序的序列上找 $i\in[l,r]$，把这个子序列拿出来即可。
然后就出现了一个 KDT 的做法，你考虑类似整体二分一样，把所有询问一起做，从后往前扫一遍，考虑每个点对每个询问的贡献，画在二维平面上，就是矩形加上一个半裙元素，使用 KDT 做到 $O(n\sqrt n)$。
但是呢，KDT 常数太大了，于是我们考虑其他做法。
我们考虑分块对吧，然后呢我们想想对什么分块，对扫描的东西？还是原本的下标？
原本的下标的话，你发现仍旧是退化成了一个你要往里面加东西，而这个你加一个至少要 $O(\log n)$，不可取。
我们对扫描的东西分块，我们就发现我们直接在每个块里面算即可，合并块之间是好合并的，你对每个询问来讲，你如果知道了每个块内部的东西，那合并起来，直接把所有的信息加在一起即可。
我们考虑如何计算一个块内所有下标在 $[l,r]$ 内的答案。
我们突然发现这个块内的元素只有 $O(\sqrt n)$ 个啊！那你不是总共只有 $O(n)$ 种可能的本质不同询问，那你直接把所有的算出来就可以了，至于把原询问映射到小询问上，这个是简单的，直接离散化。
我们问题转化为了，给定长为 $n$ 的序列 $a$ 和半裙元素序列 $b$，要求在 $O(n^2)$ 的时间复杂度内求出对于每个 $[l,r]$，满足 $a_i \in [l,r]$ 的 $i$ 的子序列的 $b$ 的和是多少。
我们一招鲜吃遍天。既然我们都搞的是本质不同询问，那你再搞一次，用 TB5？
我们想想对什么分治，你如果对下标分治是困难的，你对序列分治，然后你惊奇的发现，你知道了左边的本质不同，右边的本质不同，然后你把他左右拼起来，比如你要找 $[l,r]$，你直接找他在左边的和他在右边的，然后加起来就可以了。
$$ T(n)=2T\left(\cfrac{n}{2}\right) + O(n^2)\ T(n)=O(n^2) $$
这是 $O(n^2)$ 的。
于是这个题就做完了。但还有一些有趣的小性质。
一个想法是你觉得这个太唐了，你为啥要先分块再分治呢？你直接分治呢。
你别说还真行，你直接对整个扫描线分治，然后只做那些询问有的本质不同询问，你考虑合并的复杂度，比如我们现在分治长度为 $x$。首先他不会超过 $n$ 吧，你总共就 $n$ 个询问，其次你不超过 $x^2$ 对吧。然后你就是：
$$ T(x)=2T\left(\cfrac{x}{2}\right) + \min(x^2, n)\ T(n)=O(n\sqrt n) $$
这个证明过程看 Deepseek 的证明：
要求解递归式 $T(x) = 2T(x/2) + \min(x^2, n)$ 的时间复杂度 $O(T(n))$。这里 $n$ 是固定的外部参数（原问题规模），而 $x$ 是递归变量，初始调用为 $x = n$。
分析：
递归项 $\min(x^2, n)$ 会随 $x$ 的变化而改变形式：
- 当 $x^2 \ge n$，即 $x \ge \sqrt{n}$ 时，$\min(x^2, n) = n$；
- 当 $x^2 < n$，即 $x < \sqrt{n}$ 时，$\min(x^2, n) = x^2$。
因此递归过程可分为两个阶段。
设 $n$ 是 2 的幂方便计算：$n = 2^m$，则 $\sqrt{n} = 2^{m/2}$。
第 $i$ 层递归的规模为 $x_i = n / 2^i$，节点数为 $2^i$。阶段 1： $i \le m/2$（即 $x_i \ge \sqrt{n}$）
每层单个节点的代价为 $n$，该层总代价为： $$ 2^i \cdot n $$ 这部分求和为： $$ S_1 = \sum_{i=0}^{m/2} 2^i n = n \cdot (2^{m/2 + 1} - 1) \approx 2n \sqrt{n} = \Theta(n^{1.5}) $$阶段 2： $i > m/2$（即 $x_i < \sqrt{n}$）
每层单个节点的代价为 $x_i^2 = (n/2^i)^2 = n^2 / 4^i$，该层总代价为： $$ 2^i \cdot \frac{n^2}{4^i} = \frac{n^2}{2^i} $$ 这部分求和为： $$ S_2 = \sum_{i = m/2 + 1}^{m} \frac{n^2}{2^i} $$ 令 $j = i - (m/2 + 1)$，则 $2^i = 2^{m/2 + 1} \cdot 2^j = 2\sqrt{n} \cdot 2^j$，每一项为： $$ \frac{n^2}{2\sqrt{n} \cdot 2^j} = \frac{n^{1.5}}{2^{j+1}} $$ 这是一个递减的几何级数，其总和由最大项（$j=0$ 时）决定，量级为： $$ \Theta(n^{1.5}) $$叶子节点： 递归到规模为 1 时停止，叶子数为 $2^m = n$，每个叶子代价为常数，总和为 $\Theta(n)$，属于低阶项。
综合以上，总时间复杂度为： $$ T(n) = \Theta(n^{1.5}) = \Theta(n\sqrt{n}) $$ 因此 $O(T(n)) = O(n^{3/2})$。
然后你发现其实直接分治的复杂度是一样的，这是一个蛮好的地方。
然后我们总结一下，其实对于这种，我们使用 KDT 来做扫描线的情况，我们都可以使用 TB5 来大大削减常数以及代码难度。这是一个深刻的点。